C Program to Implement Selection Sort Recursively

In this Searching and Sorting in C, we will have a look at how to write a C Program to implement selection sort recursively in C Programming Language.

Selection sort is an algorithm for sorting, specifically in-place comparison. It has a time complexity of O(n2), making it inefficient on large lists, and generally performs worse than the similar type of insertion. Selection sort is noted for its simplicity, and in some situations, especially where auxiliary memory is limited, it has performance advantages over more complicated algorithms.

The algorithm divides the list of inputs into two parts: the sublist of items already sorted, which is built up from left to right at the front (left) of the list, and the sublist of items to be sorted which occupies the rest of the list. The sorted sublist is initially empty, and the unsorted sublist is the full input list. The algorithm continues by locating the smallest (or largest) element in the unsorted sublist, replacing it (swapping) with the leftmost unsorted element (sorting it in order), and moving one element to the right of the sublist boundaries.

Selection sort time efficiency is quadratic, so there are a number of sorting techniques that have a better time complexity than sorting selection. One thing that differentiates selection sort from other sorting algorithms is that, in the worst case, it makes the minimum number of swaps possible, n − 1.

For example:

arr[] = 64 25 12 22 11

// Find the minimum element in arr[0...4]
// and place it at beginning
11 25 12 22 64

// Find the minimum element in arr[1...4]
// and place it at beginning of arr[1...4]
11 12 25 22 64

// Find the minimum element in arr[2...4]
// and place it at beginning of arr[2...4]
11 12 22 25 64

// Find the minimum element in arr[3...4]
// and place it at beginning of arr[3...4]
11 12 22 25 64

C Program to Implement Selection Sort Recursively

#include <stdio.h> 
void swap(int *xp, int *yp) 
{ 
int temp = *xp; 
*xp = *yp; 
*yp = temp; 
} 
void selectionSort(int arr[], int n) 
{ 
int i, j, min_idx; 
// One by one move boundary of unsorted subarray 
for (i = 0; i < n-1; i++) 
{ 
// Find the minimum element in unsorted array 
min_idx = i; 
for (j = i+1; j < n; j++) 
if (arr[j] < arr[min_idx]) 
min_idx = j; 
// Swap the found minimum element with the first element 
swap(&arr[min_idx], &arr[i]); 
} 
} 
/* Function to print an array */
void printArray(int arr[], int size) 
{ 
int i; 
for (i=0; i < size; i++) 
printf("%d ", arr[i]); 
printf("\n"); 
} 
// Driver program to test above functions 
int main() 

{ 
int arr[] = {64, 25, 12, 22, 11}; 
int n = sizeof(arr)/sizeof(arr[0]); 
selectionSort(arr, n); 
printf("Sorted array: \n"); 
printArray(arr, n); 
return 0; 
}

Leave a Comment

Your email address will not be published. Required fields are marked *