Introduction

Sorting algorithms are used to rearrange numbers in an array in increasing or decreasing order. Actually, sorting is not to used to sort numbers only. Suppose we have an array of student object. Each student have an age, and we want to sort the students by their increasing age. In this problem, we will also use sorting algorithms to sort them. In general, sorting algorithms are used to sort an array of objects with a custom rule for sorting we specify for the sorting algorithms.

Prerequisite

The reader of this tutorial should know basic programming skills, and should be able write simple programs with c or c++. Readers also should know how to compute the time complexity of algorithms.

Selection Sort

Selection sort selects the minimum element in a non-sorted part and put this element at the beginning of the non-sorted part. So, selection sort algorithm simply is ( assume ascending sort) :

1. Initialize an index that reflects the beggining of the non-sorted part we will begin with. So, this index we be equal to the first element in the array at the begging.
2. Loop from index to the last element of the array.
3. Get the minimum element in the array.
4. Put this minimum element in the first element of the non-sorted part which is the index place.
5. Increase index by 1.
6. Check whether the index is equal to the last element of the array :
   • If true, terminate the program, and our array is sorted.
   • Else, go to step 2.

As you can see the algorithm worst time complexity is O(n^2). The best time complexity is also O(n^2).

Cpp Code

#include<bits/stdc++.h>
using namespace std;

void SelectionSort(vector<int> &arr){
    int index = 0;
    int sz = arr.size();
    while(index!=sz-1){
        int mnIdx = index;  /* storing the minimum element index */
        // Get the minimum element index
        for(int i = index; i < sz; i++){
            mnIdx = arr[mnIdx] > arr[i] ? i : mnIdx;
        }
        swap(arr[mnIdx],arr[index]);
        index++;
    }
}

int main(){
    vector<int> arr = {1,5,20,2,9,4};
    SelectionSort(arr);
    for(int i=0;i<6;i++)cout<<arr[i]<<" ";
}

Bubble Sort

Bubble sort is the simplest sorting algorithm. Bubble sort keeps swapping the elements that are not in order until all array elements are inplace. Bubble sort algorithm is :

1. Loop on the array.
2. Check for every 2 subsequent elements that are not in order and swap them. Like (5 , 3) this 2 subsequent elements are reversed. As, 5 is bigger than 3. so we swap them.
3. Check whether any swaps have been made.
   • If true we go to step 1.
   • Else, the array is sorted and we can terminate the algorithm.

The algorithm worst time complexity is O(n^2). The best time complexity is also O(n).

Cpp Code

#include<bits/stdc++.h>
using namespace std;

void BubbleSort(vector<int> &arr){
    bool sorted = false;
    int sz = arr.size();
    while(!sorted){
        sorted = true;
        for(int i = 0; i < sz-1; i++){
            if(arr[i]>arr[i+1]){
                swap(arr[i],arr[i+1]);
                sorted = false;
            }
        }
    }
}

int main(){
    vector<int> arr = {1,5,20,2,9,4};
    BubbleSort(arr);
    for(int i=0;i<6;i++)cout<<arr[i]<<" ";
}

Insertion Sort

Insertion sort works the same way as we sort the playing cards. It picks each element and tries to put the element in its right place in the array.

Insertion sort algorithm is :

1. Loop on elements from the second element. We will name the current element in this loop the key.
2. Loop on elements before the key until we get to a point that the element is smaller than key.
3. we will insert the key to this position where the element to its left is smaller. and the one on its right is bigger.

The algorithm worst time complexity is O(n^2). The best time complexity is also O(n).

Cpp Code

#include<bits/stdc++.h>
using namespace std;

void InsertionSort(vector<int> &arr){
    int sz = arr.size();
    for(int key = 1; key < sz; key++){
        int j = key-1;
        int storeKey = arr[key];
        while(j>=0&&arr[j]>storeKey){
            arr[j+1] = arr[j];
            j--;
        }
        arr[j+1] = storeKey;
    }
}

int main(){
    vector<int> arr = {1,5,20,2,9,4};
    InsertionSort(arr);
    for(int i=0;i<6;i++)cout<<arr[i]<<" ";
}