Spread the love

Sorting Algorithms in C programming is vast topic and often used in most common interview questions to check the logic building aptitude. Sorting in general refers to ordering things based on criteria like numerical, chronological, alphabetical, hierarchical etc.

For example :- Keeping business records and want to sort them by ID number or last name of client? Then you’ll need a sorting algorithm.

There are many articles on internet about the different sorting algorithms but i have discussed here some of them  basics and inefficient. To understand the more complex and efficient sorting algorithms, it’s important to first understand the simpler and slower algorithms.

Fact – It is estimated that around 25% of all CPU cycles are used to sort data.

Selection Sort

 selection-sort-animationAlgo – Repeatedly finding the minimum element and swapping.

It basically determines the minimum (or maximum) of the list and swaps it with the element at the index where its supposed to be. The process is repeated such that the nth minimum (or maximum) element is swapped with the element at the n-1th index of the list. The below is an implementation of the algorithm in C.

void SelectionSort(int A[], int size)
{
	for(int i=0; i<size-1; i++)
	{
		int Imin = i;
		for(int j=i+1; j<size; j++)
		{
			if( A[j] < A[Imin] )
			{
				Imin = j;
			}
		}
		int temp = A[Imin];
		A[Imin] = A[i];
		A[i] = temp;
	}
}

 

Bubble Sort

Algo – Swapping the adjacent elements

bubble-sort-animationBubble Sort works by comparing each element of the list with the element next to it and swapping them if required. With each pass, the largest of the list is “bubbled” to the end of the list whereas the smaller values sink to the bottom. It is similar to selection sort although not as straight forward. Instead of “selecting” maximum values, they are bubbled to a part of the list. An implementation in C.

void BubbleSort(int A[], int size)
{
	for(int i=0; i<size; i++)
	{
		for(int j=0; j<size-1; j++)
		{
			if( A[j] > A[j+1] )
			{
				int temp = A[j];
				A[j] = A[j+1];
				A[j+1] = temp;
			}
		}
	}
}

 

Insertion sort

Algo – Shift elements one by one

insertion-sort-animation Try recalling how you sort a deck of cards. You start from the beginning, traverse through the cards and as you find cards misplaced by precedence you remove them(like making space/here we call it hole/) and insert them back into the right position. Eventually what you have is a sorted deck of cards. The same idea is applied in the Insertion Sort algorithm. The following is an implementation in C.

void InsertionSort(int A[], int size)
{
	for(int i=1; i<size; i++)
	{
		int value = A[i];
		int hole = i;
		while( hole>0 && A[hole-1]>value)
		{
			A[hole] = A[hole-1];
			hole--;
		}
		A[hole] = value ;
	}
}

 

Merge Sort

Algo – Divide and Conquer algorithm or Merge two array

merge-sort-animationMerge sort is a recursive algorithm that continually splits a array in equal two halves. If the array is empty or has one item, it is sorted by definition (the base case). If the array has more than one item, we split array and recursively invoke a merge sort on both halves. Once the two halves are sorted, the fundamental operation, called a merge, is performed. Merging is the process of taking two smaller sorted array and combining them together into a single, sorted, new array.

void Merge(int A[], int L[], int R[], int L_len, int R_len)
{
	int i=0,j=0,k=0;
	
	while( i<L_len && j<R_len )
	{
		if( L[i] <= R[j] )
		{
			A[k] = L[i];
			i++;
		}
		else
		{
			A[k] = R[j];
			j++;
		}
		k++;
	}
	while( i<L_len)
	{
		A[k] = L[i];
		i++;k++;
	}
	while( j<R_len )
	{
		A[k] = R[j];
		j++;k++;
	}
}

void MergeSort(int A[],int size)
{
	if(size<2)return;
	int L_len = size/2;
	int R_len = size - L_len;
	
	int L[L_len],R[R_len];
	
	for(int i=0;i<L_len;i++)
	{
		L[i] = A[i];
	}
	for(int j=0;j<R_len;j++)
	{
		R[j] = A[j+L_len];
	}
	
	MergeSort(L,L_len);
	MergeSort(R,R_len);
	Merge(A,L,R,L_len,R_len);
}

 

 

Quick Sort

Algo – Divide and Conquer algorithm or Partitioning array

sorting_quicksort_animation1.) Choose any element as pivot(here i chose last) element from the array list.

2.) Partitioning the array so that all the elements with value less than the pivot will come before the pivot and the element with value greater will come after the pivot with in the same array, which make pivot element in the sorted position.(If the reverse the order we are reversing the sorting order that is descending).

3.) Apply recursively the 3rd step to the sub array of the element with smaller values and separate the sub array of the elements with the greater values until partition of array containing 2 elements.

#include <stdio.h>

void swap(int *x, int *y);
int Partition(int A[], int start, int end);
void QuickSort(int A[], int start, int end);

int main()
{
	int A[] = {3,2,1,5,6,4};
	
	QuickSort(A,0,5);
	
	for(int i=0;i<6;i++)
		printf(" %d",A[i]);

	return 0;
}
 
void swap(int *x, int *y)
{
	int temp = *x;
	*x = *y;
	*y = temp;
}

int Partition(int A[], int start, int end)
{
	int pivot = A[end];
	int pIndex = start;
	
	for(int i=start; i<end; i++)
	{
		if( A[i] <= pivot )
		{
			swap(&A[i],&A[pIndex]);
			pIndex++;
		}
	}
	swap(&A[end],&A[pIndex]);
	return pIndex;
}

void QuickSort(int A[], int start, int end)
{
	if(start<end)
	{
		int pIndex = Partition(A,start,end);
		QuickSort(A,start,pIndex-1);
		QuickSort(A,pIndex+1,end);
	}
}

 

Suggested Reading