Sorting

What is a sorting algorithm ?

A sorting algorithm is an algorithm that sorts the data into some order, say from ascending to descending.


The sorting problem
Input: Array of numbers , unsorted. Eg.

Output : Same numbers sorted in some order, say increasing order. Eg.

Classification of sorting algorithms
Sorting algorithm can be classified in various ways.

Comparison sorts vs non comparison sorts


Various sorts

• Bubble sorting
• Selection sorting
• Insertion sort 
• Binary Sort implementation in C
• Quick sort in c
• Merge sort in c
• Radix sort in c
• Shell sort in c
• Sorting binary array

Read More

Insertion sort

The sorting problem
Input: Array of numbers , unsorted. Eg.

Output : Same numbers sorted in some order, say increasing order. Eg.

Insertion sort:
An efficient elementary sort method which places each element in it's proper place among the elements which are already placed

Pseudocode for selection sort

• Starts by considering the first two elements of the array data, if out of order, swap them 
• Consider the third element, insert it into the proper position among the first three elements. 
• Consider the forth element, insert it into the proper

Example
Consider the following array:

We have to sort the array in increasing order. So, first we take first 2 elements i.e. 28 and 18 and swap them as they are out of order.

2nd pass - Now, we consider first 3 elements. As, 7 is smallest element, we bring it in 0th index, and shift the rest of the elements from there on, as they are already sorted. So, the idea is to exchange the element selected in this pass (here 7) to swap with all elements in the left which are higher than that element.

Likewise, the algorithm goes on.

Pseudocode

public static void sort(int[] array)
{
    int N = array.length;
    for(int i=0;i < N;i++)
        for(int j=0;j>0;j--)
            if(a[j] < a[j-1])
                swap(a[j],a[j-1]);
            else
                break;
}

Implementation in cpp

Implementation in cpp using templates

#include <iostream>
#include <string.h>

template <typename T>
class InsertionSort
{
    public:
        InsertionSort();
        ~InsertionSort();

        void sort(T arr[], int size);
    private:
        void compareExchange(T arr[], int l, int r);
        bool greater(T left, T right);
};

//Constructor
template <typename T>
InsertionSort<T>::InsertionSort(){}

//Destructor
template <typename T>
InsertionSort<T>::~InsertionSort(){}

template <typename T>
void InsertionSort<T>::sort(T arr[], int size)
{
    for(int i = 1; i < size; ++i)
    {
        for(int j = i; j > 0; --j)
        {
            compareExchange(arr, j-1, j);
        }
    }
}

template <typename T>
void InsertionSort<T>::compareExchange(T arr[], int l, int r)
{
    if(greater(arr[l], arr[r]))
    {
        T temp = arr[l];
        arr[l] = arr[r];
        arr[r] = temp;
    }
}

template <typename T>
bool InsertionSort<T>::greater(T left, T right)
{
    return left > right;
}

template <>
bool InsertionSort<const char*>::greater(const char *left, const char *right)
{
    return strcmp(left, right) > 0;
}

template <typename T>
void print(T arr[], int size)
{
    for(int i = 0; i < size; ++i)
        std::cout << arr[i] << " ";
    std::cout << std::endl;
}

template <>
void print(std::string arr[], int size)
{
    for(int i = 0; i < size; ++i)
        std::cout << arr[i].c_str() << " ";
    std::cout << std::endl;
}

template <>
void print(const char *ptrArray, int size)
{
    for(int i = 0; i < size; ++i)
        std::cout << ptrArray[i] << " ";
    std::cout << std::endl;
}

int main()
{
    int arr[] = { 10, 65, 35, 25, 15, 75, 85, 45, 65 };
    InsertionSort<int> isInt;
    isInt.sort(arr, 9);
    print(arr, 9);

    std::string strArr[] = { "pankaj", "paresh", "hello", "world", "ankit", "aditya", "sankalp", "aladdin" };
    InsertionSort<std::string> isString;
    isString.sort(strArr, 8);
    print(strArr, 8);

    const char* ptrArray[] = { "pankaj", "paresh", "hello", "world", "ankit", "aditya", "sankalp", "aladdin", "george"};
    InsertionSort<const char*> isPtr;
    isPtr.sort(ptrArray, 9);
    print(ptrArray, 9);

    return 0;
}

Implementation in java using generics

 import org.junit.Assert;
 import org.junit.Test;
 
 class GenericInsertionSorter
 {
     public <T extends Comparable<T>> void sort(T[] elems) {
         int size = elems.length;
 
         for (int outerLoopIdx = 1; outerLoopIdx < size; ++outerLoopIdx) {
             for (int innerLoopIdx = outerLoopIdx; innerLoopIdx > 0; --innerLoopIdx) {
                 if (elems[innerLoopIdx - 1].compareTo(elems[innerLoopIdx]) > 0) {
                     T temp = elems[innerLoopIdx - 1];
                     elems[innerLoopIdx - 1] = elems[innerLoopIdx];
                     elems[innerLoopIdx] = temp;
                 }
             }
         }
     }
 }
 
 public class InsertionSortTester
 {
     private String[] unsortedNames = new String[] {
             "Pankaj",
             "Paresh",
             "Ankit",
             "Sankalp",
             "Aditya",
             "Prem",
             "Rocket",
             "Singh",
             "Alabama",
             "Alaska",
             "Animal" };
 
     private String[] sortedNames = new String[] {
             "Aditya",
             "Alabama",
             "Alaska",
             "Animal",
             "Ankit",
             "Pankaj",
             "Paresh",
             "Prem",
             "Rocket",
             "Sankalp",
             "Singh" };
 
     @Test
     public void testStringSort() {
         GenericInsertionSorter ss = new GenericInsertionSorter();
         ss.sort(unsortedNames);
         Assert.assertArrayEquals(unsortedNames, sortedNames);
     }
 }

Read More

Selection Sort

The sorting problem
Input: Array of numbers , unsorted. Eg.

Output : Same numbers sorted in some order, say increasing order. Eg.

Selection Sort is a sorting algorithm that sorts data items into ascending or descending order, which comes under the category of in-place comparison sort.

Pseudocode of selection sort

1. Get the smallest element and put it in the first position
2. Get the next smallest element and put it in the 2nd position
3. ....

Sorting takes place by stepping through all the data items one-by-one while looking for either largest or smallest data item and making only one swap after finding either largest or smallest data item. Hence, this sorting algorithm is referred to as the selection sort because on each pass this algorithm selects either largest or smallest of the remaining unsorted data items and places them in the right order.

For example, consider the following array:

Now we select the first smallest element, i.e. 4 and put it in first location.

And so on with 7,10 and 18.

Finally we have a sorted array:

Implementation in c
Will come soon - comment if you need early
 
Implementation in cpp

 #include <iostream>
 
 class SelectionSort
 {
     public:
         SelectionSort();
         ~SelectionSort();
 
         void sort(int arr[], int size);
 
     private:
         void exchange(int &x, int &y);
 };
 
 //Constructor
 SelectionSort::SelectionSort() {}
 
 //Destructor
 SelectionSort::~SelectionSort() {}
 
 void SelectionSort::sort(int arr[], int size)
 {
     for(int outerLoopIdx = 0; outerLoopIdx < size - 1; ++outerLoopIdx)
     {
         int min = outerLoopIdx;
         for(int innerLoopIdx = outerLoopIdx + 1; innerLoopIdx < size; ++innerLoopIdx)
         {
             if(arr[min] > arr[innerLoopIdx])
             {
                 min = innerLoopIdx;
             }
         }
         exchange(arr[outerLoopIdx], arr[min]);
     }
 }
 
 void SelectionSort::exchange(int &x, int &y)
 {
     int t = x;
     x = y;
     y = t;
 }
 
 void print(int arr[], int size)
 {
     for(int i = 0; i < size; ++i)
         std::cout << arr[i] << " ";
 }
 
 int main()
 {
     int arr[] = { 10, 65, 35, 25, 15, 75, 85, 45, 65 };
     SelectionSort ss;
     ss.sort(arr, 9);
     print(arr, 9);
 }

Selection sort in java
 To come soon - comment if you need early

Selection sort in java using generics

 import org.junit.Assert;
 import org.junit.Test;
 
 class GenericSelectionSorter
 {
     public <T extends Comparable<T>> void sort(T[] elems) {
         int size = elems.length;
 
         for (int outerLoopIdx = 0; outerLoopIdx < size - 1; ++outerLoopIdx) {
             int min = outerLoopIdx;
             for (int innerLoopIdx = outerLoopIdx; innerLoopIdx < size; ++innerLoopIdx) {
                 if (elems[min].compareTo(elems[innerLoopIdx]) > 0) {
                     min = innerLoopIdx;
                 }
             }
 
             // exchange elements at outerIndexLoop and min positions
             T temp = elems[min];
             elems[min] = elems[outerLoopIdx];
             elems[outerLoopIdx] = temp;
         }
     }
 }
 
 public class SelectionSortTester
 {
     private String[] unsortedNames = new String[] {
             "Pankaj",
             "Paresh",
             "Ankit",
             "Sankalp",
             "Aditya",
             "Prem",
             "Rocket",
             "Singh",
             "Alabama",
             "Alaska",
             "Animal" };
 
     private String[] sortedNames = new String[] {
             "Aditya",
             "Alabama",
             "Alaska",
             "Animal",
             "Ankit",
             "Pankaj",
             "Paresh",
             "Prem",
             "Rocket",
             "Sankalp",
             "Singh" };
 
     @Test
     public void testStringSort() {
         GenericSelectionSorter ss = new GenericSelectionSorter();
         ss.sort(unsortedNames);
         Assert.assertArrayEquals(unsortedNames, sortedNames);
     }
 }

Thanks

Read More