ft_qsort.c File Reference

Generic quicksort implementation with fallback to insertion sort. More...

#include "libft.h"

Include dependency graph for ft_qsort.c:

Functions
int	double_cmp (const void *a, const void *b)
	Comparison function for two doubles.
void	ft_qsort (void *base, size_t nmemb, size_t size, int(*cmp)(const void *, const void *))
	Sorts an array using quicksort and insertion sort fallback.
static void *	get_elem (void *base, size_t i, size_t size)
	Returns a pointer to the i-th element in a base array.
static void	insertion_sort (void *base, size_t start, size_t end, size_t size, int(*cmp)(const void *, const void *))
	Sorts a subarray using insertion sort.
int	int_cmp (const void *a, const void *b)
	Comparison function for two integers.
static size_t	median_of_three (void *base, size_t start, size_t end, size_t size, int(*cmp)(const void *, const void *))
	Chooses a pivot using the median-of-three rule.
static size_t	partition (void *base, size_t start, size_t end, size_t size, int(*cmp)(const void *, const void *))
	Partitions the array using Lomuto scheme.
static void	quicksort (void *base, size_t start, size_t end, size_t size, int(*cmp)(const void *, const void *))
	Recursive quicksort with insertion sort fallback and tail-call optimization.

Detailed Description

Generic quicksort implementation with fallback to insertion sort.

Author

Toonsa

Date

2025/04/05

This file provides a general-purpose sorting utility based on the quicksort algorithm. It includes a threshold-based fallback to insertion sort for small segments and provides standard comparator functions for integers and doubles.

Function Documentation

get_elem()

static void * get_elem ( void *  base, size_t  i, size_t  size  )

static

Returns a pointer to the i-th element in a base array.

Parameters

base	Base pointer to the array.
i	Index of the desired element.
size	Size (in bytes) of each element.

Returns

Pointer to the i-th element.

insertion_sort()

static void insertion_sort ( void *  base, size_t  start, size_t  end, size_t  size, int(*)(const void *, const void *)  cmp  )

static

Sorts a subarray using insertion sort.

This function is used by quicksort for short segments. It sorts the subarray from start to end in-place.

Parameters

base	Base pointer to the array.
start	Starting index of the subarray.
end	Ending index of the subarray.
size	Size (in bytes) of each element.
cmp	Comparator function.

median_of_three()

static size_t median_of_three ( void *  base, size_t  start, size_t  end, size_t  size, int(*)(const void *, const void *)  cmp  )

static

Chooses a pivot using the median-of-three rule.

Selects the pivot as the median of the first, middle, and last elements and swaps it into the end position.

Parameters

base	Base pointer to the array.
start	Start index.
end	End index.
size	Size (in bytes) of each element.
cmp	Comparator function.

Returns

Index of the pivot (which will be at end).

partition()

static size_t partition ( void *  base, size_t  start, size_t  end, size_t  size, int(*)(const void *, const void *)  cmp  )

static

Partitions the array using Lomuto scheme.

Rearranges the array so that elements less than the pivot come before, and those greater come after. Pivot is chosen with median-of-three.

Parameters

base	Base pointer to the array.
start	Start index.
end	End index (pivot location).
size	Size of each element in bytes.
cmp	Comparator function.

Returns

Final pivot index after partitioning.

quicksort()

static void quicksort ( void *  base, size_t  start, size_t  end, size_t  size, int(*)(const void *, const void *)  cmp  )

static

Recursive quicksort with insertion sort fallback and tail-call optimization.

Sorts elements between start and end using quicksort. If the range is below QSORT_THRESHOLD, switches to insertion sort.

Parameters

base	Pointer to base of the array.
start	Start index.
end	End index.
size	Element size in bytes.
cmp	Comparator function.