Sorting Algorithms

Sorting Algorithms:
---------------------------
1- Selection Sort
2- Bubble Sort
3- Merge Sort
============================================================
1- Selection Sort: 
- Time Complexity : O(N^2)
---------------------------------------
void swap(int*ele1,int*ele2)
{
int temp;
temp=*ele1;
*ele1=*ele2;
*ele2=temp;
}

/*
in this code: the use of mini variable is to determine the index of the smallest number in the array first then we swap after the inner loop finishes. Without the mini variable, we have to move the swap function into the inner loop and swap whenever the condition is true and that takes more time!
*/
void selectSortElements(int*arr,int size)
{
int i,j,mini;
for(i=0;i<size-1;i++)
{

mini=i;

/* The inner for loop is used to determine the index of the smallest element in the array */
for(j=i+1;j<size;j++)
{
if(arr[j]<arr[mini])
{
mini=j;
}
}
swap(&arr[i],&arr[mini]);
}
}

=================================================
2-Bubble Sort:-
--------------------

void bubbleSort(int*arr , int size)
{
    int i,j;

    for(i=0;i<size-1;i++)
    {
        for(j=0;j<size-i-1;j++)
        {
            if( arr[j]>arr[j+1])
            {
                 swap(&arr[j],&arr[j+1]);
             }   
         }
    }
}

The above function always runs O(n^2) time even if the array is sorted.It can be optimized by stopping the algorithm if inner loop didn’t cause any swap.

The optimized version of bubble sort:
---------------------------------------------------

void bubbleSort(int*arr, int size)
{
int i , sortFlag=0;
while(!sortFlag)
{
sortFlag=1;
for(i=size-1;i>=0;i--)
{
if(arr[i]<arr[i-1])
{
swap(&arr[i],&arr[i-1]);
sortFlag=0;
}
}
}
}

NOTES:
========

Worst and Average Case Time Complexity: O(n*n). Worst case occurs when array is reverse sorted.

Best Case Time Complexity: O(n). Best case occurs when array is already sorted.

=========================================================
Merge Sort:
------------------

Perfectly explained: https://www.geeksforgeeks.org/merge-sort/