heap_sort_2.c File Reference

Heap Sort implementation More...

#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <inttypes.h>

Include dependency graph for heap_sort_2.c:

Functions
void	swap (int8_t *first, int8_t *second)
	for assert
void	heapifyDown (int8_t *arr, const uint8_t size)
	heapifyDown Adjusts new root to the correct position in the heap This heapify procedure can be thought of as building a heap from the top down by successively shifting downward to establish the heap property.
void	heapifyUp (int8_t *arr, uint8_t i)
	heapifyUp Adjusts arr[i] to the correct position in the heap This heapify procedure can be thought of as building a heap from the bottom up by successively shifting upward to establish the heap property.
void	heapSort (int8_t *arr, const uint8_t size)
	Heap Sort algorithm.
static void	test ()
	Self-test implementations.
int	main ()
	Main function.

Detailed Description

Heap Sort implementation

Author

Dhruv Pasricha

Heap-sort is a comparison-based sorting algorithm. Heap-sort can be thought of as an improved selection sort: like selection sort, heap sort divides its input into a sorted and an unsorted region, and it iteratively shrinks the unsorted region by extracting the largest element from it and inserting it into the sorted region.

Unlike selection sort, heap sort does not waste time with a linear-time scan of the unsorted region; rather, heap sort maintains the unsorted region in a heap data structure to more quickly find the largest element in each step. Time Complexity : O(Nlog(N))

Function Documentation

heapifyDown()

void heapifyDown	(	int8_t *	arr,
		const uint8_t	size
	)

heapifyDown Adjusts new root to the correct position in the heap This heapify procedure can be thought of as building a heap from the top down by successively shifting downward to establish the heap property.

Parameters

arr	array to be sorted
size	size of array

Returns

void

{
    uint8_t i = 0;
 
    while (2 * i + 1 < size)
    {
        uint8_t maxChild = 2 * i + 1;
 
        if (2 * i + 2 < size && arr[2 * i + 2] > arr[maxChild])
        {
            maxChild = 2 * i + 2;
        }
 
        if (arr[maxChild] > arr[i])
        {
            swap(&arr[i], &arr[maxChild]);
            i = maxChild;
        }
        else
        {
            break;
        }
    }
}

heapifyUp()

void heapifyUp	(	int8_t *	arr,
		uint8_t	i
	)

heapifyUp Adjusts arr[i] to the correct position in the heap This heapify procedure can be thought of as building a heap from the bottom up by successively shifting upward to establish the heap property.

Parameters

arr	array to be sorted
i	index of the pushed element

Returns

void

{
    while (i > 0 && arr[(i - 1) / 2] < arr[i])
    {
        swap(&arr[(i - 1) / 2], &arr[i]);
        i = (i - 1) / 2;
    }
}

heapSort()

void heapSort	(	int8_t *	arr,
		const uint8_t	size
	)

Heap Sort algorithm.

Parameters

arr	array to be sorted
size	size of the array

Returns

void

{
    if (size <= 1)
    {
        return;
    }
 
    for (uint8_t i = 0; i < size; i++)
    {
        // Pushing `arr[i]` to the heap
 
        /*heapifyUp Adjusts arr[i] to the correct position in the heap*/
        heapifyUp(arr, i);
    }
 
    for (uint8_t i = size - 1; i >= 1; i--)
    {
        // Moving current root to the end
        swap(&arr[0], &arr[i]);
 
        // `heapifyDown` adjusts new root to the correct position in the heap
        heapifyDown(arr, i);
 
    }
}

Here is the call graph for this function:

main()

int main

(

void

)

Main function.

Returns

0 on exit

{
    // Intializes random number generator
    srand(time(NULL));
 
    test(); // run self-test implementations
    return 0;
}

Here is the call graph for this function:

swap()

void swap	(	int8_t *	first,
		int8_t *	second
	)

for assert

for IO operations for dynamic memory allocation for random numbers generation for uint8_t, int8_t

Swapped two numbers using pointer

Parameters

first	pointer of first number
second	pointer of second number

{
    int8_t temp = *first;
    *first = *second;
    *second = temp;
}

test()

static void test ( void  )

static

Self-test implementations.

Returns

void

{
    const uint8_t size = 10;
    int8_t *arr = (int8_t *)calloc(size, sizeof(int8_t));
 
    /* generate size random numbers from 0 to 100 */
    for (uint8_t i = 0; i < size; i++)
    {
        arr[i] = rand() % 100;
    }
    heapSort(arr, size);
    for (uint8_t i = 0; i < size - 1; ++i)
    {
        assert(arr[i] <= arr[i + 1]);
    }
    free(arr);
}

Here is the call graph for this function: