My notes on Sorting in C

Bubble Sort:

Simplest sorting algorithm

Repeatedly comparing pair of  adjacent element and swapping if they are not in order

Not suited for large datasets, as its worst-case complexity is O(n2) where n is the number of elements because the entire array needs to be iterated for every element.

E.g.

15, 32, 26, 34, 11

First Pass:

(15, 32, 26, 34, 11) -> (15, 32, 26, 34, 11)  No swapping as the elements are in order

(15, 32, 26, 34, 11) -> (15, 26, 32, 34, 11) Swapped as 32 > 26

(15, 26, 32, 34, 11)  -> (15, 26, 32, 34, 11) No Swapping as the elements are in order

(15, 26, 32, 34, 11) -> (15, 26, 32, 11, 34) Swapped as 34 > 11

Second Pass:

(15, 26, 32, 11, 34) -> (15, 26, 32, 11, 34) No swapping as the elements are in order

(15, 26, 32, 11, 34) -> (15, 26, 32, 11, 34) No swapping as the elements are in order

(15, 26, 32, 11, 34) -> (15, 26, 11, 32, 34) Swapped as 32 > 11

 (15, 26, 11, 32, 34) -> (15, 26, 11, 32, 34) No swapping as the elements are in order

Third Pass:

(15, 26, 11, 32, 34) -> (15, 26, 11, 32, 34) No swapping as the elements are in order

 (15, 26, 11, 32, 34) ->  (15, 11, 26, 32, 34) Swapped as 26 > 11

 (15, 11, 26, 32, 34) ->  (15, 11, 26, 32, 34) No swapping as the elements are in order

 (15, 11, 26, 32, 34) ->  (15, 11, 26, 32, 34) No swapping as the elements are in order

Fourth Pass:

 (15, 11, 26, 32, 34) ->  (11, 15, 26, 32, 34) Swapped as 15 > 11

(11, 15, 26, 32, 34) -> (11, 15, 26, 32, 34) No swapping as the elements are in order

(11, 15, 26, 32, 34) -> (11, 15, 26, 32, 34) No swapping as the elements are in order

(11, 15, 26, 32, 34) -> (11, 15, 26, 32, 34) No swapping as the elements are in order

Now you can see the list is sorted

Code:

void bubbleSort(int arr[], int n)
{
   int i, j;
   for (i = 0; i < n-1; i++)     
 
       // Last i elements are already in place   
       for (j = 0; j < n-i-1; j++) 
           if (arr[j] > arr[j+1])
              swap(&arr[j], &arr[j+1]);

}

The above function runs even if the array is sorted, this can be optimized by stopping the algorithm if the inner loop didn't cause any loop.


Selection Sort:

The algorithm maintains two subarrays in a given array:
1. Subarray which is already sorted.
2. Remaining subarray which is unsorted.

Algorithm is based on the idea of finding the minimum element in an unsorted array and placing it in the correct position of sorted array.

E.g. arr[] = {15, 32, 26, 34, 11};

First Pass: 11, 32, 36, 34, 15
Second Pass: 11, 15, 36, 34, 32
Third Pass: 11, 15, 32, 34, 36
Fourth Pass: 11, 15, 32, 34, 36

Complexity: O(n2).

Selection sort performs a smaller number of swaps compared to bubble sort. therefore even though both sorting methods are of O(n2), selection sort is faster and performs more efficiently.

Code:

void selection_sort (int A[ ], int n) {

        // temporary variable to store the position of minimum element

        int minimum;        

        // reduces the effective size of the array by one in  each iteration.

        for(int i = 0; i < n-1 ; i++)  {

           // assuming the first element to be the minimum of the unsorted array .

             minimum = i ;

          // gives the effective size of the unsorted  array .

            for(int j = i+1; j < n ; j++ ) {

                if(A[ j ] < A[ minimum ])  {                //finds the minimum element

                minimum = j ;

                }

             }

          // putting minimum element on its proper position.

          swap ( A[ minimum ], A[ i ]) ; 

        }

   }

Insertion Sort: