Sorting

Some basic sorting algorithms {must know}

1) Bubble sort
2) Insertion sort
3) Selection sort

bubble sort :



> worst case time complexity : O(n^2)
> best case time complexity : O(n) { when list is already sorted }
> worst case space complexity: O(1) auxiliary

> not used anymore,

Insertion sort :
algotithm : assume a sorted array in the given array, select one of the card and insert it into its correct position in the sorted array .



> better than selection and bubble sort
> space complexity : O(1)
> worst case time complexity : O(n^2)
> best case time complexity : O(n) {when array is already sorted }
> it is stable : stability means that it does not change the order of elements with equal keys
> modified version : shell sort
> for small input, insertion sort may perform better than even quick sort

selection sort
simply select the element one by one in increasing order and insert them into their correct position



> worse (almost half ) than insertion sort.
> time complexity O(n2) { both worse and best }
> variant : heap sort