Sorting Technique

Bubble Sort in Sorting Techniques

Bubble Sort is a simple sorting technique here we take two data at a time & we will swap them if they are not in order (ascending or descending).  We will do this until the list ends. So the average time complexity of the Bubble Sorting technique is n².

The following code implements the Bubble Sort using c#. We will be using for loop to iterate over the array, we use the temporary variable to hold the value when we swap the data. For example, in the first iteration of the outer for loop, we will start with i=0, inner for loop runs from j=0 till size-1. Similarly in the next iteration, i become 1 and this process continues.

public static void BubbleSort(int size, int[] array)
{
    for (int i = 0; i < size - 1; i++)
    {
        for (int j = 0; j < size - 1 - i; j++)
        {
            if (array[j] > array[j + 1])
            {
                int temp = array[j];
                array[j] = array[j + 1];
                array[j + 1] = temp;
            }
        }

    }
}

Below is the visualization when i=0 & j=0 through j=7 ( Example: Array size is 8)

Selection Sort in Sorting Techniques

In the Selection Sorting technique we re using two lists one is a sorted list & the other is an unsorted list. We are iterating over the unsorted list & finding the minimum/maximum then pushing this to the sorted list. If we repeat this for each we will end up with a sorted list. Instead of creating two separate lists, we can use an array & logically divide the array into a sorted array and unsorted array. The average time complexity of this algorithm is n².

 public static void SelectionSort(int[] array, int size)
 {
     int minimum_index;
     for (int i = 0; i < size - 1; i++)
     {
         //asuming that element is at postion i is minimum
         minimum_index = i;

         //looping through unsorted list checking for minimum
         for (int j = i + 1; j <= size - 1; j++)
         {

             //if a minimum found then change the current minimum.
             if (array[j] < array[minimum_index])
             {
                 minimum_index = j;
             }
         }

         //push the minimum to sorted list
         int temp = array[i];
         array[i] = array[minimum_index];
         array[minimum_index] = temp;

     }
 }

Insertion Sort in Sorting Techniques

This algorithm similar to Selection Sort Algorithms. We will be logically dividing the array into Sorted Array & Unsorted array, By taking the elements one by one from the Unsorted array & comparing it with the sorted array and Inserting the value at the correct location by shifting elements. The  average time complexity of this algorithm is n².

public static void InsertionSort(int[] array, int size)
{
    int hole, value;
    for (int i = 1; i < size; i++)
    {
        hole = i;
        value = array[hole];

        while (hole > 0 && array[hole - 1] > value)
        {
            array[hole] = array[hole - 1];
            hole = hole - 1;
        }
        array[hole] = value;


    }
}

Merge Sort in Sorting Techniques

Merge Sort is a sorting technique that allows us to sort the array in nlogn time complexity. It is not an in-place sorting technique. It needs auxiliary space. Merge Sort is used to solve many computer science problems.

The merge sort technique is based on the Divide & Conquer method. We divide the array into two halves & thereby making two small problems. Dividing the array into two halves continues till each sub-array left with a single element  (Array with a single element is always sorted). Once both the halves sorted we merge the array by comparing two sub-arrays.Once the two sub-arrays sorted & merged we copy the array elements to the original array.

Below is the code for Merge Sort using C#. MergeSort method divides the input array to left & right sub-arrays & calls the merge sort method recursively. The merge method merges once we get two sorted sub-arrays.

Below is the drive code for the above implementation of the Merge Sort.

public static void Merge(int[] array, int start, int mid, int end)
        {
            int tempSize = end - start + 1;
            int[] temp = new int[tempSize];
            int i = start;
            int j = mid + 1;
            int k = 0;

            while (i <= mid && j <= end)
            {
                if (array[i] < array[j])
                {
                    temp[k++] = array[i++];
                }
                else
                {
                    temp[k++] = array[j++];
                }
            }

            while (i <= mid)
            {
                temp[k++] = array[i++];
            }

            while (j <= end)
            {
                temp[k++] = array[j++];
            }

            k = 0;
            for (i = start; i <= end; i++)
            {
                array[i] = temp[k++];
            }

            return;
        }
        public static void MergeSort(int[] array, int start, int end)
        {
            if (start >= end)
                return;

            int mid = (start + end) / 2;

            MergeSort(array, start, mid);
            MergeSort(array, mid + 1, end);
            Merge(array, start, mid, end);



        }

The main function looks like this

static void Main(string[] args)
{
    int[] array = {10,1,2,9,8,7,6,5,4,3};
    MergeSort(array, 0, 9);

    for (int i = 0; i <= 9; i++)
    {
        Console.WriteLine(array[i]);
    }

}

Quick Sort in Sorting Techniques

Quicksort is an in-place sorting algorithm. Quick Sort has got the Average Case complexity of O(nlogn). It is used in many places, in fact, many sorting functions have internally implemented Quick Sort.

In Quick Sort We will choose an element from the array called Pivot, We need to keep all the other elements from the array which are greater than the Pivot towards the right side of the Pivot& all the elements which are less than Pivot towards left side of the array. We call this Partitioning.

Once We get Pivot element after Partitioning , We call the Quick Sort method recursively for left & right halves of that particular Pivot element.

Once all done we get our array sorted. Since we don’t use any auxiliary space during this process this is called in-place sorting algorithm.

The Below code shows the implementation using C#.

public static void Swap(int[] array, int index1, int index2)
{
    int temp = array[index1];
    array[index1] = array[index2];
    array[index2] = temp;

}
public static int Partiton(int[] array, int start, int end)
{
    int Pivot = array[start];
    int PivotIndex = -1;
    int countLessthanPivot = 0;
    int i = 0;
    int j = 0;
    for (i = start + 1; i <= end; i++)
    {
        if (array[i] <= Pivot)
        {
            countLessthanPivot++;
        }

    }
    PivotIndex = countLessthanPivot + start;
    Swap(array, start, PivotIndex);

    i = start;
    j = end;
    while (i < PivotIndex && j > PivotIndex)
    {
        if (array[i] <= Pivot)
        {
            i++;
        }
        else if (array[j] > Pivot)
        {
            j--;
        }
        else
        {
            Swap(array, i, j);
            i++; j--;
        }
    }

    return PivotIndex;

}

public static void QuickSort(int[] array, int start, int end)
{
    if (start >= end)
        return;

    int pivotIndex = Partiton(array, start, end);
    QuickSort(array, start, pivotIndex - 1);
    QuickSort(array, pivotIndex + 1, end);


}

The main function looks like this.

static void Main(string[] args)
{
    int[] array = { 10, 9, 8, 7, 6, 5, 4, 3, 2, 1 };
    QuickSort(array, 0, 9);

    for (int i = 0; i <= 9; i++)
    {
        Console.WriteLine(array[i]);
    }

}

We have discussed different sorting techniques in previous section, these differs by time and space complexity.We have seen Average case time complexity for each of them. If you want to have detailed time complexity analysis this page helps.

Time Complexity Analysis