Sorting

Selection Sort

• Selection sort is a simple algorithm, but inefficient.

• First, find the smallest element using a linear scan and move it to the front (swap). Then, find the second smallest and move it, again doing a linear scan. Continue doing this until all the elements are in place.

Selection Sort

C#

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

void SelectionSort(int[] array){
    var n = array.Length - 1;
    for(int i = 0; i <= n; i++){
        var minIdx = i;
        for(int j = i + 1; j <= n; j++){
            if(array[j] < array[minIdx]){
                minIdx = j;
            }
        }
        Swap(array, minIdx, i);
    }
}

Time Complexity: O(n^2)

Space Complexity: O(1)

Bubble Sort

• In this algorithm, we start at the beginning of the array and swap the first two elements if the first is greater than the second. Then, we go to the next pair, and so on, continuously making sweeps of the array until it is sorted.

C#

void BubbleSort(int[] array){
    var n = array.Length;
    for(int i = 0; i < n - 1; i++){
        for(int j = 0; j < n - i - 1; j++){
            if(array[j] > array[j + 1]){
                int temp = array[j];
                array[j] = array[j + 1];
                array[j + 1] = temp;
            }
        }
    } 
}

Time Complexity: O(n^2)

Space Complexity: O(1)

Insertion Sort

C#

void InsertionSort(int[] array){
    var n = array.Length - 1;
    for(int i = 1; i <= n; i++){
        var unsortedItem = array[i];
        var comparingItemIndex = i - 1;
        
        while(comparingItemIndex >= 0 && unsortedItem < array[comparingItemIndex]){
            array[comparingItemIndex + 1] = array[comparingItemIndex];
            comparingItemIndex--;
        }
        array[comparingItemIndex + 1] = unsortedItem;
    }
}

Time Complexity: O(n^2)

Space Complexity: ?

Quick Sort

Quicksort is another sorting algorithm based on the Divide and Conquer programming technique. In this algorithm, an element is first chosen as the pivot, and the entire array is then partitioned around this pivot.

As you've probably guessed, a good pivot is crucial for an efficient sort. The pivot can either be a random element, the media element, the first element, or even the last element.

Implementations of quicksort often differ in the way they choose a pivot. In the average case, quicksort will sort a large array with a good pivot in just O(nlogn) time.

The general pseudocode of quicksort repeatedly partitions the array on the pivot and positions it in the correct position of the subarray. It also places the elements smaller than the pivot to its left and elements greater than the pivot to its right.

C#

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

int Partition(int[] array, int lowIdx, int highIdx){
    var pivot = array[highIdx];
    var possibleIdx = lowIdx - 1;
    for(int i = lowIdx; i < highIdx; i++){
        if(array[i] <= pivot){
            possibleIdx++;
            Swap(array, i, possibleIdx);
        }
    }
    possibleIdx++;
    Swap(array, possibleIdx, highIdx);
    
    return possibleIdx;
}

void QuickSort(int[] array, int startIdx, int endIdx){
    if(startIdx < endIdx){
        var pivotIdx = Partition(array, startIdx, endIdx);
        if(startIdx < pivotIdx - 1)              // sort left half 
            QuickSort(array, startIdx, pivotIdx - 1);
        if(pivotIdx < endIdx)                    // sort right half
            QuickSort(array, pivotIdx, endIdx);      
    }
}

Time Complexity: O(n^2) Worst case O(n log n) Average case

Space Complexity: O(log n)

Merge Sort

Divide and Conquer Programming Technique

• Merge sort divides the array in half, sorts each of those halves, and then merge them back together.

• Each of those halves has the same sorting algorithm applied to it.

Merge Sort

C#

void MergeSort(int[] array){
    int[] helper = new int[array.Length];
    MergeSort(array, helper, 0, array.Length - 1);
}
void MergeSort(int[] array, int[] helper, int lowIdx, int highIdx){
    if(lowIdx < highIdx){
        int middleIdx = (lowIdx + highIdx) / 2;
        MergeSort(array, helper, lowIdx, middleIdx);        //sort left half
        MergeSort(array, helper, middleIdx + 1, highIdx);   //sort right half
        Merge(array, helper, lowIdx, middleIdx, highIdx);
    }
}

void Merge(int[] array, int[] helper, int lowIdx, int middleIdx, int highIdx){
    /* Copy both halves into a helper array */
    for(int i = lowIdx; i <= highIdx; i++){
        helper[i] = array[i];
    }
    int helperLeft = lowIdx;
    int helperRight = middleIdx + 1;
    int currentIdx = lowIdx;
    
    while(helperLeft <= middleIdx && helperRight <= highIdx){
        // if left element is smaller than the right element
        if(helper[helperLeft] <= helper[helperRight]){
            array[currentIdx] = helper[helperLeft];
            helperLeft++;
        }
        // else if right element is smaller than the left element
        else{
            array[currentIdx] = helper[helperRight];
            helperRight++;
        }
        currentIdx++;
    }
    int remaining = middleIdx - helperLeft;
    for(int i = 0; i <= remaining; i++){
        array[currentIdx + i]  = helper[helperLeft + i];
    }
}

Time Complexity: O(n log n)

Space Complexity: O(n)

The space complexity being O(n) is due to the auxiliary space used to merge the parts of the array.

Sorting Algorithms Animationstoptal