sorting algorithms

optimized-bubble-sort.cpp

#include <iostream>
/*

it works by swaping the adjacent elements if they are in wrong order

Complexity Analysis of Selection Sort:

Time Complexity:
it always runs O(n^2) time even if the array is sorted. it was optimized by stopping algorithm

*/

void swap(int *xp, int *yp)
{
    int temp = *xp;
    *xp = *yp;
    *yp = temp;
}

int bubble_sort(int arr[], int n)
{
    int i, j, min_idx, total_call_count = 0;
    bool is_already_sorted = false; // indicates whether we are already sorted

    for (i = 0; i < n - 1; i++)
    {
        is_already_sorted = true;

        for (j = 0; j < n - 1; j++)
        {
            total_call_count++;
            if (arr[j + 1] < arr[j])
            {
                swap(&arr[j + 1], &arr[j]);
                is_already_sorted = false;
            }
        }

        if (is_already_sorted == true) // interrupt query since it's already sorted. it is unnecessary to loop through
            break;
    }

    return total_call_count;
}

int main(int argc, char **argv)
{

    int arr[] = {1, 2, 5, 4, 8};

    std::cout << "before bubble_sort : " << std::endl;
    for (int i = 0; i < 5; i++)
        std::cout << arr[i] << " ";
    std::cout << std::endl;

    int total_call_count = bubble_sort(arr, 5);

    std::cout << "after bubble_sort : " << total_call_count << std::endl;
    for (int i = 0; i < 5; i++)
        std::cout << arr[i] << " ";
    std::cout << std::endl;

    return 0;
}

selection-sort.cpp

#include <iostream>

/*

This algorithm sorts an array by repeatedly finding the minimum element  from unsorted part 


Complexity Analysis of Selection Sort:

Time Complexity:
One loop to select an element of Array one by one = O(N)
Another loop to compare that element with every other Array element = O(N)
Therefore overall complexity = O(N)*O(N) = O(N*N) = O(N2)

Auxiliary Space:
O(1) as the only extra memory used is for temporary variable

*/

void swap(int *xp, int *yp)
{
    int temp = *xp;
    *xp = *yp;
    *yp = temp;
}

void selection_sort(int arr[], int n)
{
    int i, j, min_idx;
    for (i = 0; i < n - 1; i++)
    {
        min_idx = i;
        for (j = i + 1; j < n; j++)
            if (arr[j] < arr[min_idx])
                min_idx = j;

        if (min_idx != i)
            swap(&arr[i], &arr[min_idx]);
    }
}

void printArray(int arr[], int size)
{
    int i;
    for (i = 0; i < size; i++)
        std::cout << arr[i] << " ";
    std::cout << std::endl;
}

int main(int argc, char **argv)
{

    int arr[] = {64, 25, 12, 22, 11};

    std::cout << "before selection sort: " << std::endl;
    for (int i = 0; i < 5; i++)
        std::cout << arr[i] << " ";
    std::cout << std::endl;

    selection_sort(arr, 5);

    std::cout << "after selection sort: " << std::endl;
    for (int i = 0; i < 5; i++)
        std::cout << arr[i] << " ";
    std::cout << std::endl;

    return 0;

}