Sorting

Sorting

7 Basics Sorting algos are describe here.

--> Bubble sort            

--> Selection Sort              

--> Insertion Sort

--> Counting sort           

--> Quick Sort                     

--> Merge Sort                   

--> Radix Sort

1. Bubble Sort.

--> Bubble Sort also known as Exchange Sort.
--> It works by repeatedly stepping throughout the list to be sorted, comparing two items at a time and swapping them if they are in the wrong order. 
--> The pass through the list is duplicated until no swaps are desired, which means the list is sorted.

       Bubble Sort Algorithm: Steps on how it works:

In an unsorted array of 5 elements, start with the first two elements and sort them in ascending order. (Compare the element to check which one is greater).

Compare the second and third element to check which one is greater, and sort them in ascending order.

Compare the third and fourth element to check which one is greater, and sort them in ascending order.

Compare the fourth and fifth element to check which one is greater, and sort them in ascending order.

Repeat steps 1–5 until no more swaps are required.

         Code:

Some Characteristics of Bubble Sort:

• Large values are always sorted first.
• It only takes one iteration to detect that a collection is already sorted.
• The best time complexity for Bubble Sort is O(n). The average and worst time complexity is O(n²).
• The space complexity for Bubble Sort is O(1), because only single additional memory space is required.

Complexity:                   BEST               Average                    Worst

    Bubble Sort Ω(N) Θ(N^2) O(N^2)

     2. Selection Sort:

-->  Selection sort is one of the easiest sorting algorithm out there. In Selection sort, to sort an unsorted array, all we have to do is find the minimum in the array and swap it with the first element in the unsorted array. After each swapping increase the starting index of the array by one.

Selection Sort Algorithm: Steps on how it works:

1. Iterate over the unsorted array, keeping track of the minimum value as you go.
2. When you get to the end of the array, you know which element is the minimum.
3. Swap the minimum element and the first element in the unsorted array.
4. The first element is now considered sorted.
5. Repeat until the rest of the array is sorted.

Code:

Complexity:

                                        Best               Average               Worst

Selection Sort Ω(N^2) Θ(N^2) O(N^2)

3 . Insertion Sort:

The Insertion sort algorithm is one of the key sorting algorithms used in Computer Science.

To start with, the algorithm considers the first value of a list as a sorted sub-list (of one value to start with). This iterative algorithm then checks each value in the remaining list of values one by one. It inserts the value into the sorted sub-list of the data set in the correct position, moving higher ranked elements up as necessary.

    Code:

Complexity:            Best                  Average               Worst

                 

Insertion Sort Ω(N) Θ(N^2) O(N^2)