C Sorting

Last Updated Nov 20, 2015, 07:00:14 PM





This tutorial covers the sorting concepts in C programming and also covers the basic sorting algorithms in C

What is is sorting?

Sorting is an algorithm that is used to sort the elements in a particular order by moving the wrong elements away from the queue. This technique sorts the adjacent elements and keeps them in the right order.

There are different types of sorting algorithms which are used to perform different sorting methods. The most popular sorting algorithms are Selection Sort, Merge Sort, Quick Sort

How Sorting Works?

Sorting algorithms work by moving elements to their final position, one at a time. You sort an array of size N, put 1 item in place, and continue sorting an array of size N – 1

Let us say there are N elements which are not in order. To sort those elements we need to perform N-1 iterations. At each iteration the largest elements will be moved to the last position and the smallest element will be moved to the first position.

Before Sorting After Sorting Example Output
Enter 5 random numbers
5
7
8
2
400
After the numbers sorted and arranged in ascending order are
2
5
7
8
400
List of Sorting Algorithms
  • Selecttion
  • Mergesort
  • Bubble
  • Quick
  • Heap
  • Radix
  • Bucket sort
  • Counting Sort

Selection Sort in C

Selection sort finds the smallest element by scanning all the items. When the selection sort finds a smallest element it will simply swap and repeats the process on all the remaining N-1 items

This sorting method first checks the entire array elements to find the smallest element first, when it finds a smallest item it will swap it the first element in the array. And then it will look for the next smallest element in the remaning array and this process will go on until it sort the array

Algorithm

The best case/worst-case runtime complexity is O(n2)

Example Output
Enter the size of the list: 6
Enter the elements in list:
4
6
7
8
4
3
The sorted list in ascending order is
3 4 4 6 7 8

Merge Sort in C

Merge-sort is very easy algorithm, it is purely based one theory that is divide-and-conquer.

Well, how merge-sort works? Take an array and divide it into two seperate parts or two subarrays, then sort each subarrays, after all just merge them into one array.

merge sort in c

How Merge Sort Works?

First it divides the input array into two seperate halves, and then divdes the the two seperate subarrays into other halves and then it merges back the two subarrays. You can use the The merge() function to merge two subarrays

Implementation of Merge Sort Let us say, we have an arrray called myarray[], where left,right are the left and right elements in the array Example