quicksort.c File Reference

Quicksort using Lomuto partition. More...

#include "sorts.h"
#include <string.h>

Go to the source code of this file.

Functions
static long	lomuto_partition_int (int *arr, long lo, long hi)
static long	lomuto_partition_str (char **arr, long lo, long hi)
static void	quicksort_int_recursive (int *arr, long lo, long hi)
void	quicksort_ints (int *arr, size_t n)
static void	quicksort_str_recursive (char **arr, long lo, long hi)
void	quicksort_strings (char **arr, size_t n)
static void	swap_int (int *a, int *b)
static void	swap_str (char **a, char **b)

Detailed Description

Quicksort using Lomuto partition.

Average O(n log n), worst O(n²) on already-sorted input. Tail-recursion on the smaller partition would bound the stack depth at O(log n) — kept straightforward here for readability.

Definition in file quicksort.c.

Function Documentation

lomuto_partition_int()

static long lomuto_partition_int ( int *  arr, long  lo, long  hi  )

static

Definition at line 55 of file quicksort.c.

References swap_int().

Referenced by quicksort_int_recursive().

lomuto_partition_str()

static long lomuto_partition_str ( char **  arr, long  lo, long  hi  )

static

Definition at line 21 of file quicksort.c.

References swap_str().

Referenced by quicksort_str_recursive().

quicksort_int_recursive()

static void quicksort_int_recursive ( int *  arr, long  lo, long  hi  )

static

Definition at line 68 of file quicksort.c.

References lomuto_partition_int(), and quicksort_int_recursive().

Referenced by quicksort_int_recursive(), and quicksort_ints().

quicksort_ints()

void quicksort_ints	(	int *	arr,
		size_t	n
	)

Definition at line 76 of file quicksort.c.

References quicksort_int_recursive().

quicksort_str_recursive()

static void quicksort_str_recursive ( char **  arr, long  lo, long  hi  )

static

Definition at line 34 of file quicksort.c.

References lomuto_partition_str(), and quicksort_str_recursive().

Referenced by quicksort_str_recursive(), and quicksort_strings().

quicksort_strings()

void quicksort_strings	(	char **	arr,
		size_t	n
	)

Definition at line 42 of file quicksort.c.

References quicksort_str_recursive().

Referenced by algo_from_name().

swap_int()

static void swap_int ( int *  a, int *  b  )

static

Definition at line 49 of file quicksort.c.

Referenced by lomuto_partition_int().

swap_str()

static void swap_str ( char **  a, char **  b  )

static

Definition at line 15 of file quicksort.c.

Referenced by lomuto_partition_str().