Quick sort algorithm

Quick Sort:-

Steps for doing quick sort -

1. Select an element as pivot from the list.
2. Divide the list into two parts such that all the elements on the left side of the pivot are smaller than pivot and the elements on the right side are greater than pivot.
3. Store the pivot at its correct position in between the two lists.
4. One element has reached at its correct position.
5. Repeat steps 1-3 for each of the sub-lists created.
6. Stop the process untill one element is left in each of the sub-list.

Algorithm :-

Quick_Sort(low, high)

1. If(low > high)

          Return

2. Set pivot = arr[low]

3. Set i = low +1

4. Set j = high

5. Repeat step 6 until i > high or arr[i] >pivot than

6. Increment i by 1

7. Repeat step 8 until j < low or arr[j] < pivot than

8. Decrement j by 1

9. If i < j

          swap arr[i] with arr[j]

10. If i <= j

          go to step 5.

11. If low < j

          swap arr[low] with arr[j]

12. Quick_Sort (low, j-1)

13. Quick_Sort (j+1, high)

Example:-

1.         28  55  46  38  16  89  83  30

             |

         pivot   

               -------------------------> Greater value     

2.         28  55  46  38  16  89  83  30

                         <------------------- Smaller value

3.         28  55  46  38  16  89  83  30

                   ||                ||

                        SWAP

4.         28  16  46  38  55  89  83  30

       smaller <-------

                               |                         

5.         28  16  46  38  55  89  83  30 

                          |

                          ----------> greater value

6.        28  16  46  38  55  89  83  30

                   |     |

           No change as smaller value is already on the left

7. Divide the list. 

           28  16               46  38  55  89  83  30 

           List A                         List B

8. Swap 16 with 28 in A

          16   28        // truncate pivot from A

           16              // only one element left no sorting req.

9. Similarly, repeat the process for list B.

10.     16                  46  38  55  89  83  30

11.     16  28            46  38 30            89  83  55    

                                  |          |                List C

                                   SWAP

12.     16  28           30  38  46            89  83  55

13. Repeat the process until all the lists don't get sorted.

14. After that merge them. Sorted list will be -

                   16  28  30  38  46  55  83  89  

Shell sort algorithm

Shell Sort Algorithm:-

Shell sort algorithm is an improved version of Insertion sort algorithm. In an average case when list is already partially sorted insertion sort is not an efficient way to solve the problem. Thus, we use shell sort algorithm.

        In shell sort algorithm, we divide the list in no. of lists according to the length of the list and then apply insertion sort on each sub-list. And then merge all the sub-lists to form one.

Example:-

       0   1   2   3  4   5   6    7     8   9  10

     70 30 40 10 80 20 90 110 75 60 45

We can divide it into 3 parts with 2 having 4 elements and one having 3 elements.

       0       3      6     9                 1       4     7        10                 2     5     8

    70 10 90 60         30 80 110 45          40 20 75

Apply insertion sort on each sub-list.

     0       3      6      9                1     4        7     10                  2      5     8

    10 60 70 90         30 45 80 110          20 40 75 

Merge them.

     0   1   2   3  4   5   6    7     8   9  10

    10 30 20 60 45 40 70 80 75 90 110

Divide it into two parts.

     0   2   4    6   8   10                1  3   5   7   9  

    10 20 45 70 75 110              30 60 40 80 90

Sort them using insertion sort.

      0   2    4   6   8   10                 1   3  5    7   9

     10 20 45 70 75 110               30 40 60 80 90

Merge them.

      0    1   2    3  4  5   6   7   8  9     10

     10 30 20 40 45 60 70 80 75 90 110 

Apply insertion sort to the list.

        10 20 30 40 45 60 70 75 80 90 110                

The list is sorted now.

Insertion Sort Algorithm

Insertion Sort:-

Insertion sort algorithm has two case scenarios -

• Best case
• Worst case

1. In worst case the given array elements are arranged in reverse /decreasing order. Thus, we have to do 1 comparison in first pass, 2 in second and n-1 comparisons in (n-1)th  pass.Thus, the total no. of comparisons made will be equal to (n^2)/2 and the complexity will be O(n^2).
2. Best case is occurred when given list is already sorted. In this case we have to make only one comparison in each pass. So, the complexity will be O(n).

In both cases no. of  passes are (n-1).

where n is the no. of elements in given array.

Algorithm:-

int i,j,temp,x[n];

for(i = 1; i < n; i++)

{

            temp = x[i];

            j = i - 1;

            while( temp < x[j] && j >= 0)

            {

                       x[j + 1] = x[j];

                       j = j - 1;

            }

            x[j + 1] = temp;

}  

Example:-

              70 80 30 10 20

1. Split the array in two parts. One sorted list and second unsorted       list.

              70            80 30 10 20

          sorted              unsorted

2. Start placing elements in first list from second list at their correct     position.

              70  80           30  10  20

              

              30  70  80        10  20

              10  30  70  80      20

              10  20  30  70  80

The list is sorted now.

 

Selection Sort Algorithm

Selection Sort Algorithm:-

Like Bubble sort algorithm, Selection sort is also used to sort the given array elements but in Selection sort the smallest number from given array elements reaches its correct position or index in first pass. n-1 comparisons are made in the first pass, n-2 in second pass and so on until the given array is unsorted.

Total no. of comparisons =

(n-1) + (n-2) + ... + 4 + 3 + 2 + 1 = n(n-1)/2

Number of passes <= n - 1

where n is the no. of array elements.

            Complexity of Selection sort is also as same as of the Bubble sort, O(n^2).

Example:-

 

Bubble Sort Algorithm

Bubble Sort Algorithm :

Bubble sort algorithm is a method to sort the unsorted list. In Bubble sort technique largest number reaches its correct position /index on pass one. Pass 1 requires n-1 comparisons where n is the number of elements in the array. Similarly pass 2 requires one less comparison so number of comparisons are n-2 and so on until number of pass becomes equal to n-1. 

           So, total number of comparisons required are -

(n-1) + (n-2) + (n-3) + ........ + 3 + 2 + 1 = n(n-1)/2

           Thus, the complexity of bubble sort algorithm is O(n^2).

Example:- 

Sort the following array using Bubble Sort Algorithm-