Task: Insertion Sort

Time Complexity
O(n²)
For Best Case - O(n)

Code:

#include<iostream>
using namespace std;

int main()
{
    int a[] = {16, 190, 11, 15, 10, 12, 14};
    int n = 7;

    for (int i = 1 ; i < n; i++)
    {
        int temp = a[i];
        int j = i - 1;

        while ((temp < a[j]) && (j >= 0))
        {
            a[j+1] = a[j]; //moves element forward
            j = j - 1;
        }

        a[j+1] = temp; //insert element in proper place
    }
    
    for (int i = 0; i < n; i++)
    {
        cout << a[i] << "\t";
    }
    return 0;
}


Task: Bubble Sort

Time Complexity
O(n²)
For Best Case - O(n²)

Code:

#include<iostream>
using namespace std;

int main()
{
    int a[10], n;
    cout << "Enter the number of elements: " ;
    cin >> n;

    cout << "Enter the array elements: ";
    for (int i = 0; i < n; i++)
    {
        cin >> a[i];
    }

    for (int i = 1; i < n; ++i)
    {
        for (int j = 0; j < (n - i); ++j)
        {
            if (a[j] > a[j+1])
            {
                int temp = a[j];
                a[j] = a[j+1];
                a[j+1] = temp;
            }
            
        }
        
    }
    
    cout << "\nArray after sorting: ";
    for (int i = 0; i < n; ++i)
    {
        cout << a[i];
        if (i < n-1)
        {
            cout << ", ";
        }
        
    }

    return 0;
    
}

Task: Selection Sort

Time Complexity
O(n²)
For Best Case - O(n²)

Code:

#include<iostream>
using namespace std;

const int n = 7;
int a[n] = {4, 6, 3, 2, 1, 9, 7};

void display()
{
    int i;
    cout << "\t[";

    for(i = 0; i < n; i++) //navigate through all items
    {
        cout << a[i];
        if (i<n-1)
        {
            cout << ",";
        }    
    }
    cout << "]\n" << endl;
}

void SelectionSort()
{
    for (int i = 0; i < n - 1; i++) //loop through all numbers
    {
        int indexMin = i; //set current element as minimum

        for (int j = i + 1; j < n; j++) //check the element to be minimum
        {
            if (a[j] < a[indexMin])
            {
                indexMin = j;
            }
            
        }
        if (indexMin != i)
        {
            cout << "Items swapped:\t[" << a[i] << ", " << a[indexMin] << "]" << endl;

            //swap the numbers
            int temp = a[indexMin];
            a[indexMin] = a[i];
            a[i] = temp;
        }
        
        cout << "Iteration " << i + 1;
        display();
    }    
}

int main()
{
    cout << "Input Array: ";
    display();

    SelectionSort();
    cout << "\nOutput Array: ";
    display();
}