Kinds of Sorting Algorithms

Selection Sort

Process:
- First, find the smallest value in the array
- Next, swap the the values where the smallest value is located w/ the 1st index value of the array
- Then, Find the next smallest value in the array and swap the values where the next smallest is located w/  the 2nd index value of the array.

Advantages:
     Selection Sorting is efficient in sorting records because it only moves one record at a time.

Disadvantages:
    If the array is already sorted, the function " if " is still executed, at that moment, time is wasted.

Implementation:

int min, temp;
int numArr [] = {2,5,1,3,4};

for(int x = 0 ; x < sizeOfArray-1 ; x++){
     min = x;
         for(int y = x+1 ; y < sizeOfArray ; y++){
             if(numArr[y] < numArr[min]){
                  min = y;
             }
         }
     temp = numArr[x];
     numArr[x] = numArr[min];
     numArr[min] = temp;
}

Insertion Sort
    Insertion sort is an elementary sorting algorithm. It has a time complexity of Θ(n²), thus being slower than heap sort, merge sort and also shell sort. Insertion sort is well suited for sorting small data sets or for the insertion of new elements into a sorted sequence.^[1]

Process:

    Let a₀, ..., a_n-1 be the sequence to be sorted. At the beginning and after each iteration of the algorithm the sequence consists of two parts: the first part a₀, ..., a_i-1 is already sorted, the second part a_i, ..., a_n-1 is still unsorted (i  0, ..., n).
     In order to insert element a_i into the sorted part, it is compared with a_i-1, a_i-2 etc. When an element a_j with a_ja_i is found, a_i is inserted behind it. If no such element is found, then a_i is inserted at the beginning of the sequence.
    After inserting element a_i the length of the sorted part has increased by one. In the next iteration, a_i+1 is inserted into the sorted part etc. While at the beginning the sorted part consists of element a₀ only, at the end it consists of all elements a₀, ..., a_n-1.^[1]

Advantages:


Disadvantages:
    Moving the elements to the right in order to make room for the element to be inserted takes linear time anyway.^[1]
Implementation:

int temp;
int arrNum[] = {2,3,5,4,1};

for(int x = 0 ; x < sizeOfArray ; x++){
    int y = x;
    temp = arrNum[x];
    while(y > 0 && a[y-1] > temp){
        arrNum[y] = arrNum[y-1];
        y--;
    }
    arrNum[y] = temp;
}

Bubble Sort
    Sort by comparing each adjacent pair of items in a list in turn, swapping the items if necessary, and repeating the pass through the list until no swaps are done.^[2]

Process:
- Compare each pair of adjacent elements from the beginning of an array and, if they are in reversed order, swap them.
- If at least one swap has been done, repeat step 1.


Advantages:
     Bubble sort is stable and adaptive.^[2]
Disadvantages:
    Bubble sort is inefficient when sorting large data files because it has the running time of O(n²).

Implementation:

bool swapped = false;

int j = 0;
int temp;
    while(){
        swapped = false;
        j++;
        for(int x = 0; x < sizeOfArray-j ; x++){
            if(arrNum[x] > arrNum[x+1]){
                temp  = arrNum[x];
                arrNum[x] = arrNum[x+1];
                arrNum[x+1] = temp;
             swapped = true;
            }
        }
    }

     
Shell Sort

    Shellsort is one of the oldest sorting algorithms, named after its inventor D.L. Shell (1959) [She 59]. It is fast, easy to understand and easy to implement. However, its complexity analysis is a little more sophisticated.^[3]

Process:
- Arrange the data sequence in a two-dimensional array.
- Sort the columns of the array.^[3]



Disadvantages:
   It is inefficient in terms of processing speed, because it uses other sorting algorithm to perform its own sorting algorithm.
 
Implementation:

void shellsort (int[] a, int n)
{
    int i, j, k, h, v;
    int[] cols = {1391376, 463792, 198768, 86961, 33936, 13776, 4592,
                    1968, 861, 336, 112, 48, 21, 7, 3, 1}
    for (k=0; k<16; k++)
    {
        h=cols[k];
        for (i=h; i<n; i++)
        {
            v=a[i];
            j=i;
            while (j>=h && a[j-h]>v)
            {
                a[j]=a[j-h];
                j=j-h;
            }
            a[j]=v;
        }
    }
}[3]

References:
[1] Insertion Sort
    http://www.inf.fh-flensburg.de/lang/algorithmen/sortieren/insert/insertionen.htm
[2] Bubble Sort
    http://www.algolist.net/Algorithms/Sorting/Bubble_sort
[3] Shell Sort
    http://www.inf.fh-flensburg.de/lang/algorithmen/sortieren/shell/shellen.htm