Category Archives: Sorting

C++ STL Algorithms – Sort- Part-1

Sorting is one of the most widely used algorithmic primitive in programming. 
C++ Standard Template Library (STL) provides an efficient implementation of the sort algorithm. It is always better to use this algorithm instead of writing our own implementation because of the following benefits.
  • It’s performance would surely be better than your own implementation. It’s implementation conforms to the C++ standard bench marks and tested by a lot of people. The library version takes advantage of the combination of multiple sorting algorithms to achieve the maximum performance.
  • Writing our own version is error prone and bugs can easily be overlooked.

Here is a simple program which demonstrates the use of library sort() routine to sort an array as well as a vector. 

The sort() method at the minimum requires two parameters; the start of the list and the end of the list. Note that the end should always point to one element beyond the last element. It sorts the element ranging between [begin, end) i.e starting from the first element till the end excluding the last.


For arrays, we know that the array name indicates the address of the first element. If we add the size of the array to the starting address, we get the address of next to last element.

For vectors, there are built-in methods begin() and end() to indicate the starting and ending elements.


    #include <iostream>
    #include <algorithm> //included for using sort
    #include <vector>
    #include <string>
    using namespace std;

    int main()
    {
    int arr[5] = {9, 6, 36, 24, 42};
    int arrSize = sizeof(arr)/sizeof(arr[0]);

    sort(arr, arr+arrSize); //sorts the given numbers in ascending order

    for( int i=0; i < arrSize; i++ )
    {
    cout << arr[i] << " ";
    }
    cout << endl;

    vector<string> names;
    names.push_back("Himalayas");
    names.push_back("Alphs");
    names.push_back("Vindhya");
    names.push_back("Aravali");

    sort( names.begin(), names.end());//sorts the names in alphabetical order

    for( int i = 0; i < names.size(); i++ )
    {
    cout << names[i] << " ";
    }

    cout << endl;

    return 0;

    }

    Merging two sorted arrays

    Given two sorted arrays A, B of lengths m, n respectively. How to merge them into a single sorted array?. Let us assume that A has sufficient space (m+n) for result array.
    For example let A = [1, 3, 5, 7, 9], and B = [2, 4, 6, 8, 10]. The function should return A = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] as a result.

    Since the array A has sufficient space for the merged array, we can start from the end of the array A and start filling the result elements.

    We compare the elements at i and j indices. We move the bigger element to the end pointed by res and decrement the corresponding index. We do this until we reach the beginning of any array. Finally we check if there any left over elements in the second array. If there are, we have to move them to the first array.

    Finding the number of pairs in array with given difference

    Given an array of N distinct values, how to find the number of pairs with a difference of K?
    For example, given an array [3, 1, 4, 2, 5] and K= 2, there are 3 pairs with a difference of 2. Namely {1,3}, {2,4}, {3,5}. 

    One obvious solution could be to examine each possible pair and count the number of pairs with the given difference. (This is similar to my previous post). But this algorithm runs in O(n2) time. If you are solving it in a competition, you most probably get a Time Limit Exceeded (TLE) error.

    Let us look at more efficient solutions.

    Solution 1:

    Sort the array first using any algorithm like Quick sort or Merge sort or Heap sort. This takes O( n log n ) time. The algorithm is as follows.

    1. Take two indices and point them to first and second elements.
    2. Repeat the following steps until any index reaches the end of the array
      1. If the difference matches, increment count and increment both the indices
      2. If the difference is less than required value,  increment second index
      3. Otherwise increment first index.

    The algorithm takes O(n) time. The overall time complexity is O(n log n). It does not take any extra space.

    Solution 2:

    Using additional data structure like a set or a map. 

    1. Store all the array elements into a set.
    2. For each element in the array do the following.
      1. If the set contains array[i]+diff or array[i]-diff, increment the diff count. 
      2. Remove array[i] from the set.
    This approach runs in O(n) time but takes O(n) additional space for the set.

    Inserting an element into sorted linked list

    Given a sorted linked list write a program to insert data into it’s correct position. 
    For example consider the following linked list

    1 -> 3 -> 4 -> 5 

    Inserting 2 should change the list to

    1 -> 2 -> 3 -> 4 -> 5
    Inserting 0 should change it to
    0 -> 1 -> 2 -> 3 -> 4 ->5
    Inserting 6 should change it to
    0 -> 1 -> 2 -> 3 -> 4 -> 5 -> 6. 
    The three examples indicate three different cases to be considered while inserting into a sorted linked list.
    Case 1: List can be empty or new element is added as the first element
    Case 2: New element can be inserted anywhere in the middle of the linked list
    Case 3: New element is added as the last element.

    The following diagram illustrates the insert process.



    In the following C++ program case 1 is handled in one block and case 2 and 3 are handled in the last block.


    Merging k sorted lists

    Given K sorted lists, how to merge them into a single sorted list?
    Let total number of elements in K sorted lists is N. We have to form a single sorted list of length N.

    For example let us consider the following input lists
    {4, 19, 27}
    {1, 6, 50, 73}
    {9, 45, 59, 67}

    The output should be {1, 4, 6, 9, 19, 27, 45, 50, 59, 67, 73}.


    In this post, we discuss an efficient approach by using priority queues (heaps). This problem is one of the nice examples of using priority queues.

    Here is how the algorithm works.
    1. Add the first elements from all the lists into a priority queue along with their list indices.
    2. Until the priority queue is empty, do the following
      1. Remove the minimum element from the priority queue and add it to the result list. Let this minimum element belongs to min_list.
      2. Add the next element from min_list to the priority queue if there exists at least one element.

    Here is the Java implementation of the above algorithm.

    Time complexity of this algorithm is O(N log K) as we have N elements in total, and insert and remove-min operation of the priority queue takes O(log k) time.

    Sorting a linked list using bubble sort

    How do we sort a linked list? 
    In this post, we see one such method using bubble sort algorithm.

    We have discussed the Bubble sort algorithm on arrays in my previous post. The same algorithm is also applicable to singly linked lists as well.

    We first find the length of the linked list (len). The outer loop iterates for (len-1) times and the inner loop iterates for (len-1-i) times.

    Since we cannot access the linked list elements by their indices, we use two pointers to keep track of the current node and the next node which will be compared and swapped in each iteration.

    Here is the Object Oriented C++ implementation. 
     

    How does a counting sort work?

    Counting sort as its name indicates sort a list of integers by counting the occurrence each number appearing in the list. This is possible when the range of integers (particularly small) is given.

    Unlike comparison based sorting algorithms which run in O( n log n) time in the worst case, Counting sort runs O(n) time.

    For example let us assume the range of numbers is 0-4. and we have an input array as follows.


    3
    0
    3
    2
    4
    0
    2
    1
    2
    4

    This is basically integer sorting algorithm where in 
    1. The first iteration it counts the frequency of each number appearing the list. These counts are stored in an array indexed by the numbers itself. 
    2. In the second iteration, it counts the prefix sum array by counting how many numbers that are less than or equal to that number.
    3. The third iteration places the numbers in the correct place based on their frequency.
    Count array


    Index
    0
    1
    2
    3
    4
    Counts
    2
    1
    3
    2
    2
    Prefix Sum
    2
    3
    6
    8
    10

      

     You can take a look at this animation for understanding counting sort better.

    The following Java program implements the above approach.

    /**
    * Created with IntelliJ IDEA.
    * User: Ravi
    * Date: 10/10/13
    * Time: 5:29 AM
    * To change this template use File | Settings | File Templates.
    */
    public class CountingSortDemo {
    public static void main(String[] args)
    {
    int[] numArray = {3,0,5,9,6,2,4,5,4,1};
    int[] sortedArray = countingSort( numArray );
    for( int i = 0; i < sortedArray.length; i++ )
    {
    System.out.print( sortedArray[i] + " ");
    }
    }
    //Counting sort method
    public static int[] countingSort(int [] array )
    {
    int[] sortedArray = new int[array.length];
    int[] countArray = new int[10]; //For simplicity Assume the range 0-9
    int i;
    for( i = 0; i < array.length; i++ )
    {
    countArray[ array[i] ]++;
    }
    //calculate the prefix sums
    for( i = 1; i < countArray.length; i++ )
    {
    countArray[i] += countArray[i-1];
    }
    //place the elements in the sorted array
    for( i = 0; i < array.length; i++ )
    { 
                //Get the index to place into sorted array 
                int cIndex = countArray[ array[i] ];

    sortedArray[cIndex-1] = array[i];
    //decrement the frequency so that the same number is placed next
                //to previous entry 
    countArray[ array[i] ]--;
    }
    return sortedArray;
    }

    }

    This code is generic to sort any array objects with integer keys. If we just want to sort the array, we can combine the last two loops where we can fill the array with count of each number in order. You can do this by the following loop. 

    int resIndex = 0;
    for( i = 0; i < countArray.length; i++ )
    {
    for( int j = 0; j < countArray[i]; j++)
    sortedArray[resIndex++] = i;
    }

    Sorting the array of 0,1,2’s

    We have an array that contains only 0, 1 and 2. We have to write a program to sort this array.

    For example if the input array is [2,0,1,2,1,0,0,2], the output should be
    [0,0,0,1,1,2,2,2].

    As the first thought, we can very well use well known sorting algorithms like Quick sort, or Merge sort or Heap sort. But that would be an overkill to solve this problem. We can utilize the property that the array contains just 0,1, and 2.

    Method#1: Bucket sort approach – Simple
    Just take three counters to count 0,1 and 2. Update these while iterating through the array. This is an example of bucket sort with three buckets. Every time we see a 0, we put that in 0th bucket. If we see a 1 we put that into a 1st bucket and so on…

    In the second iteration, Fill the array with respective counts of 0,1, and 2 in that order. The following is the Java implementation.

    public static void sort012(int[] array)
    {
    int count0 = 0;
    int count1 = 0;
    int count2 = 0;

    int i;
    //Count 0's, 1's and 2's
    for( i = 0; i < array.length; i++ )
    {
    switch( array[i] )
    {
    case 0:
    count0++;
    break;
    case 1:
    count1++;
    break;
    case 2:
    count2++;
    break;
    }
    }

    //Fill the array with respective counts
    int resInd = 0;

    for( i = 0; i < count0; i++ )
    {
    array[resInd++] = 0;
    }
    for( i = 0; i < count1; i++ )
    {
    array[resInd++] = 1;
    }
    for( i = 0; i < count2; i++ )
    {
    array[resInd++] = 2;
    }
    }

     
    Method#2: Dutch National Flag algorithm (Tricky)

    This algorithm is based on Dutch national flag problem proposed by famous computer scientist Dijkstra.

    In this method the array is divided into three partitions each partition is tracked by three indices. The first part stores 0s, the second part stores 1s and the third part stores 2s.

    ind0 , ind1 starts from the beginning of the array, and ind2 starts from the ending of the array.
    In each iteration we increment ind1 and examine the element at array[ind1]

    1. If it is 0 we have to push that left part and increment ind0, and ind1
    2. If it is 1 we simply increment ind1.
    3. If it is 2 we push it to the end and decrement ind2.
    4. Repeat the above 3 steps until ind1 and ind2 meet each other.

    This algorithm scans the array only once.

    Here is the snapshot of the array in each iteration.

    2
    0
    1
    2
    1
    0
    0
    2
    Ind0, Ind1
    Ind2

    2
    0
    1
    2
    1
    0
    0
    2
    Ind0, Ind1
    Ind2
    0
    0
    1
    2
    1
    0
    2
    2
    Ind0, Ind1
    Ind2
    0
    0
    1
    2
    1
    0
    2
    2
    Ind0, Ind1
    Ind2
    0
    0
    1
    2
    1
    0
    2
    2
    Ind0, Ind1
    Ind2
    0
    0
    1
    2
    1
    0
    2
    2
    Ind0
    Ind1
    Ind2
    0
    0
    1
    0
    1
    2
    2
    2
    Ind0
    Ind1
    Ind2
    0
    0
    0
    1
    1
    2
    2
    2
    Ind0,
    Ind1, Ind2

     

    public static void sort012(int[] array)
    {
    int ind0 = 0;
    int ind1 = 0;
    int ind2 = array.length-1;

    while( ind1 <= ind2 )
    {
    if( array[ind1] == 0 )
    {
                    //swap ind0, ind1 elements 
    int temp = array[ind0];
    array[ind0] = array[ind1];
    array[ind1] = temp;

    ind0++;
    ind1++;
    }
    else if( array[ind1] == 1 )
    {
    ind1++;
    }
    else if( array[ind1] == 2 )
    {
                    //swap ind1, ind2 elements 
    int temp = array[ind1];
    array[ind1] = array[ind2];
    array[ind2] = temp;
    ind2--;
    }
    }
    }


    Sorting binary array

    Given an array of 0s and 1s, how do we sort them? After sorting all the 0s appear before all the 1s.

    For example the array [0,1,0,1,1,0,0,0,1,1] becomes [0,0,0,0,0,1,1,1,1,1]

    Let us look at two approaches to solve this problem. The first one is based on bucket sort and the second is more intelligent.

    Method#1:

    We can take two counts to keep track of the number of 0s and 1s. We iterate through the array two times.  In the first iteration we calculate the counts. In the second iteration we fill the array with respective counts. C++ code is given below.

    void sort01(int array[], int n)
    {
    int count0 = 0;
    int count1 = 0;
    int i;
    for( i = 0; i < n; i++ )
    {
    if( array[i] == 0 )
    count0++;
    else if( array[i] == 1 )
    count1++;
    }

    int resInd = 0;

    for( i = 0; i < count0; i++ )
    {
    array[resInd++] = 0;
    }

    for( i = 0; i < count1; i++ )
    {
    array[resInd++] = 1;
    }
    }


    Method#2:
    We start with two indices one pointing to the beginning, another pointing to the end of the array. We increment the begin index until we find a 1. We decrement the end index until we find a 0. We swap these two values so that all 0s move to beginning and all 1s move to the ending.

    We repeat these steps until both indices meet. This algorithm goes through the array only once. Look at the following steps in action for the example input.

    [0   1   0   1   1   0   0   0   1   1]
     L–>                             <–R

    [0   1   0   1   1   0   0   0   1   1]  – Swap A[L], A[R]
         L                       R 

    [0   0   0   1   1   0   0   1   1   1]  – “
                 L           R

    [0   0   0   0   1   0   1   1   1   1]  – “
                     L   R

    [0   0   0   0   0   L   1   1   1   1]  – “
     

    void sort01(int array[], int n)
    {
    int low = 0,high = n-1;
    while ( low < high )
    {
    while( low < high && array[low] == 0 )
    low++;

    while( low < high && array[high] == 1 )
    high--;

    if( low < high)
    swap( array[low], array[high] );
    }
    }


    Even though both algorithms run in O(n) time, the first algorithm traverse through the array two times and the second algorithm traverse through the array only once.

    How does Quicksort work?

    Quick sort is a comparison based sorting algorithm. Like Merge sort, this also follows divide and conquer algorithmic pattern.

    Quick sort works as follows. 

    A random element from the array is chosen as a pivot element. A pivot element is a special element which divides the array into left part and right part. All the elements to the left of pivot ( left part) must be less than or equal to pivot, and all the elements to the right of pivot( right part) must be greater than pivot.

    At this point it is easy to understand that the pivot element is in it’s position and only left, and right parts needs to be sorted. We use recursive call to sort these parts.

    Here partition process is the key to sorting. 

    Consider the following example to understand the partitioning process.

    Initial array: 4 is chosen as pivot for simplicity


    4
    7
    3
    6
    9
    2
    8
    5
    1


    After partitioning:


    2
    1
    3
    4
    9
    6
    8
    5
    7

     
    You can get a good understanding of the whole procedure if we look at the following animation (Image courtesy: Wikipedia).

    Here is the C++ code for quick sort.This procedure runs in O(n log n) time in average case. But in the worst case, It can take up to O(n^2) time.

     
    #include <iostream>

    using namespace std;

    void quick_sort(int[], int, int);

    int main()
    {
    int array[] = {4,7,3,6,9,2,8,5,1};
    quick_sort(array,0,8);
    for( int i = 0; i < 9; i++ )
    {
    cout<<array[i]<<" ";
    }

    return 0;
    }

    void quick_sort(int array[], int l, int h)
    {
    if( l < h)
    {
    int left = l; //starting index of the array
    int right = h;// ending index of the array
    int pivot = array[left];//take left most element as pivot

    while ( left < right)
    {
    //decrement right pointer as long as the element
    //at this index is greater than pivot
    while ( array[right] > pivot )
    right--;
    //increment left pointer as long as the element
    //at this index is less than or eqal to pivot
    while ( array[left] <= pivot )
    left++;

    //swap the elements if left and right do not overlap
    if( left < right)
    {
    swap( array[left], array[right] );
    }
    }

    //right is the correct position for pivot,
    //so swap the first element(chosen as pivot) with 'right'
    swap(array[l],array[right]);

    //recursively call quick sort for left and right parts
    quick_sort(array, l, right-1);
    quick_sort( array, right+1,h);

    }
    }