2.3 Sorting Algorithms

Now that We know about the ways we look for a number in a sorted/unsorted array. Lets move on to the way we sort/put in order an array.

Let’s consider a situation whereby we have an array which we want to arrange in Ascending/Descending Order,

Let the array be:

65      89      63      36      51       25     68      94     12      32     6        7       14

One way of sorting the array(in this example we would be doing it in Ascending Order, but the same could be 

done more Descending with minor changes!) would be the following:

1. Run a loop through the array

2. For every iteration of the loop, have another loop which checks through all the elements which have appeared before that particular element and are greater than that number in the array.

3. Whenever we find such a number as described in 2, We simply move that number to the right and place that particular number we are considering in the first loop in its position.

A video/animation demonstrating the same is here:

This is known as Insertion Sort.

In Code(C), We may have it as:

#include <stdio.h>

#include <math.h>

/* Function to sort an array using insertion sort*/

void insertionSort(int arr[], int n)

{

   int i, key, j;

   for (i = 1; i < n; i++)

   {

       key = arr[i];

       j = i-1;

       /* Move elements of arr[0..i-1], that are

          greater than key, to one position ahead

          of their current position */

       while (j >= 0 && arr[j] > key)

       {

           arr[j+1] = arr[j];

           j = j-1;

       }

       arr[j+1] = key;

   }

}

// A utility function ot print an array of size n

void printArray(int arr[], int n)

{

   int i;

   for (i=0; i < n; i++)

       printf("%d ", arr[i]);

   printf("\n");

}

/* Driver program to test insertion sort */

int main()

{

    int arr[] = {12, 11, 13, 5, 6};

    int n = sizeof(arr)/sizeof(arr[0]);

    insertionSort(arr, n);

    printArray(arr, n);

    return 0;

}

Now, What would be the Efficiency Measure here?

Note that in the InsertionSort Function we have two loops iterating over ‘n’ digits, and therefore, for every iteration of the first loop we have another ‘n’ iteration which makes the total Efficiency to be nxn or n², that is O(n²).

NOTE: The Efficiency measure of a program is also known as its Complexity or its Running time, now onwards we would use these words interchangeably.

As it turns out there are many algorithms for Sorting, each with different technicalities, here’s a comparison between many of them as to which is how fast in sorting a few million integers.:

But the Fastest one of all is Merge Sort, which we shall discuss now:

In Merge Sort, We do this:

1. Goto the Middle of the array

2. Sort the Left Half of the array (Using merge sort!)

3. Sort the Right half of the array (Using Merge Sort!)

4. Merge the Sorted halves

Merge sort could be seen in animation in the following video:

Here’s what it looks like in C code:

#include <stdio.h>

#define max 10

int a[11] = { 10, 14, 19, 26, 27, 31, 33, 35, 42, 44, 0 };

int b[10];

void merging(int low, int mid, int high) {

   int l1, l2, i;

   for(l1 = low, l2 = mid + 1, i = low; l1 <= mid && l2 <= high; i++) {

      if(a[l1] <= a[l2])

         b[i] = a[l1++];

      else

         b[i] = a[l2++];

   }

  

   while(l1 <= mid)   

      b[i++] = a[l1++];

   while(l2 <= high)  

      b[i++] = a[l2++];

   for(i = low; i <= high; i++)

      a[i] = b[i];

}

void sort(int low, int high) {

   int mid;

  

   if(low < high) {

      mid = (low + high) / 2;

      sort(low, mid);

      sort(mid+1, high);

      merging(low, mid, high);

   } else {

      return;

   }  

}

int main() {

   int i;

   printf("List before sorting\n");

  

   for(i = 0; i <= max; i++)

      printf("%d ", a[i]);

   sort(0, max);

   printf("\nList after sorting\n");

  

   for(i = 0; i <= max; i++)

      printf("%d ", a[i]);

}

NOTE: In C++, There’s a rather easier way to sort an array (though you could go for defining the Sorting in function like we did above as well), but an easier way is to use the sort() function available in the <algorithm> library in C++. The sort function takes just two inputs: 1) The starting point of an array as an iterator/pointer and 2) The end of an array as an iterator/pointer.

Look at the following example to get a better insight;

#include <iostream>

#include <algorithm>

using namespace std;

int main(){

            int n;

            cin>>n;

int arr[n];

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

                        cin>>arr[i];

            }

            sort(arr,arr+n);

            cout<<”Here’s the sorted array:”<<endl;

            for(int j = 0;j<n;j++){

                        cout<<arr[j]<<’ ’;

            }

cout<<endl;

}

When you’ll execute this code, you’ll find that the array is sorted!