C Programming Examples on Searching and Sorting

This section covers C programming examples on Searching and Sorting. Every example program includes the description of the program, C code as well as output of the program. All examples are compiled and tested on a Linux system. These examples can be simple C programs or advanced C programs. So, they are suitable for any user (dummies, beginners or advanced users).

Here is the listing of C programming examples on Searching and Sorting.

The C programs in this section demonstrate the Sort function. The Sort function sorts the elements in the range in a particular order. The different types of sorting methods are Bubble Sort, Selection Sort, Merge Sort and Quick Sort. Bubble Sort repeatedly sorts the adjacent elements if they are in wrong order. The Selection Sort finds the smallest element in the array and exchanges it with the element in the first position, it then finds the second smallest element and exchanges it with the element in the second position and continues this process until the entire list is sorted. The Merge Sort follows the Divide and Conquer rule where in it divides the input array into two halves, sorts the two halves and merges the two sorted halves. The Quick Sort selects an element as a pivot and partitions the given array around the pivot. The following C programs show the implementation of all the sorting methods mentioned above.

The C programs in this section demonstrate Searching Algorithm. The Searching Algorithm searches for the specified element in the given list. Binary Search and Linear Search are the commonly used searching algorithms. Linear Search Algorithm is used to find an item in the list. It starts searching for the item from the beginning of the list and continues till the end of the list until the item is found. The Binary Search Algorithm follows the Divide and Conquer strategy where in it finds the item from the sorted list of items. The following programs demonstrate Linear Search and Binary Search Algorithms and also searches for an element just by reading an array using recursion and without using recursion.

The C programs in this section illustrate other special Sorting Algorithms. These include Insertion Sort, Postman Sort, LSDRadix Sort, Heap Sort and Gnome Sort. Insertion Sort sorts the array by shifting the elements one by one. Postman Sort is a type of Bucket Sort in which the elements of an array are divided into buckets and then each bucket is sorted individually. LSDRadix Algorithm is used to sort the keys in integer representation order. Heap Sort is based on binary heap data structure and sorts elements similar to selection sort where the maximum element is placed at the end of the list. Gnome sort method sorts the items by comparing the current item with the previous item. If they are in order, move to the next item; If they are out of order, swap them and move to the previous item. If there is no previous item, move to the next item.

The C programs in this section demonstrates other special sorting algorithms. qSort is a function which performs quick sort. Pigeonhole Sort is a sorting technique that is used when the given range of keys is relatively small. An array of pigeonholes (buckets, chunks of memory) is reserved for each key value. The records from the unsorted list are scanned and copied into their respective pigeonholes based on their key values. Then, the contents of the pigeonholes are copied in sequence to the final destination. Cycle sort is an in-place, unstable sorting algorithm, a comparison sort that is optimal in view of the total number of writes to the original array. Odd-even sort is used for sorting on two-dimensional processor arrays. In Cocktail Sort, values “bubble” both directions through the array, because on each iteration the cocktail sort bubble sorts once forwards and once backwards. Bitonic sort is a comparison-based sorting algorithm that focuses on converting a random sequence of numbers into a bitonic sequence, one that monotonically increases, then decreases. Comb Sort is an in-place sort algorithm that repeatedly reorders different pairs of items. On each pass swaps pairs of items separated by the increment or gap, if needed, and reduce the gap. Stooge Sort is a recursive sorting algorithm.

The C programs in this section illustrate Pancake Sort, BogoSort and Shell Sort algorithms. In Pancake Sort, instead of individual elements being sorted, the only operation allowed is to “flip” one end of the list. Bogo Sort shuffles a list of values as long as they are not sorted. Shell sort is a generalization of insertion sort that allows the exchange of items that are far apart.