selection_sort_recursive.c File Reference

Selection Sort implementation using recursion. More...

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

Include dependency graph for selection_sort_recursive.c:

Functions
void	swap (int8_t *first, int8_t *second)
	for assert
uint8_t	findIndex (const int8_t *arr, const uint8_t size)
	Returns the index having minimum value using recursion.
void	selectionSort (int8_t *arr, const uint8_t size)
	Selection Sort algorithm implemented using recursion.
static void	test ()
	Self-test implementations.
int	main ()
	Main function.

Detailed Description

Selection Sort implementation using recursion.

Author

Dhruv Pasricha

Function Documentation

findIndex()

uint8_t findIndex	(	const int8_t *	arr,
		const uint8_t	size
	)

Returns the index having minimum value using recursion.

Parameters

arr	array to be sorted
size	size of array

Returns

min_index index of an element having a minimum value

{
    if (size == 1)
    {
        return 0;
    }
 
    // marking recursive call to reach starting element
    uint8_t min_index = findIndex(arr, size - 1);
 
    if (arr[size - 1] < arr[min_index])
    {
        min_index = size - 1;
    }
 
    return min_index;
}

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:

selectionSort()

void selectionSort	(	int8_t *	arr,
		const uint8_t	size
	)

Selection Sort algorithm implemented using recursion.

Parameters

arr	array to be sorted
size	size of the array

Returns

void

{
    if (size <= 1)
    {
        return;
    }
 
    /* findIndex(arr, size) returned the index having min value*/
    uint8_t min_index = findIndex(arr, size);
    /* arr[min_index] is the minimum value in the array*/
 
    if (min_index != 0)
    {
        swap(&arr[0], &arr[min_index]);
    }
 
    /*sorted the remaining array recursively*/
    selectionSort(arr + 1, size - 1);
}

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;
    }
    selectionSort(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: