heap_sort.c File Reference

In-place heap sort. O(n log n) worst case, O(1) auxiliary memory. More...

#include "../../data_structures/heap/heap.h"
#include "sorts.h"
#include <string.h>

Go to the source code of this file.

Functions
void	heap_sort_ints (int *arr, size_t n)
void	heap_sort_strings (char **arr, size_t n)
static void	sift_down_max_str (char **arr, size_t i, size_t n)

Detailed Description

In-place heap sort. O(n log n) worst case, O(1) auxiliary memory.

Step 1: build a max-heap in place from the input (linear time via Floyd's bottom-up sift-down). Step 2: repeatedly swap arr[0] (max) with arr[end] and sift-down the shrinking heap; the sorted suffix grows from the right.

Re-uses heap_sift_down_max from data_structures/heap.

Definition in file heap_sort.c.

Function Documentation

heap_sort_ints()

void heap_sort_ints	(	int *	arr,
		size_t	n
	)

Definition at line 16 of file heap_sort.c.

References heap_sift_down_max().

heap_sort_strings()

void heap_sort_strings	(	char **	arr,
		size_t	n
	)

Definition at line 48 of file heap_sort.c.

References sift_down_max_str().

Referenced by algo_from_name().

sift_down_max_str()

static void sift_down_max_str ( char **  arr, size_t  i, size_t  n  )

static

Definition at line 35 of file heap_sort.c.

Referenced by heap_sort_strings().