Question

Steps and formula (if applied) are mandatory for all the questions.

3.   a) Sort 99, 54, 64, 23, 12, 09, 45, 32, 19, 65, 89 using Quick sort. Write the algorithm.

                                                                 

b) Sort 69, 74, 64, 23, 12, 09, 45, 32, 19, 65, 88, 33, 60, 38 using Shell sort. Write the algorithm.

Answer 1

a) Sort 99, 54, 64, 23, 12, 09, 45, 32, 19, 65, 89 using Quick sort. Write the algorithm.

Quick Sort: In data structures, Quick Sort is a divide and conquer algorithm. In this sort, one element has to be picked i.e: whether it is the fist element, last element or random as a pivot, and that pivot partitions the given array.

Algorithm:
Choose one element as a pivot.
Partition the array such that
All pivot element should be in the correct position in the soring list.
All left side elements of the pivot are less than equal to the pivot.
All the right side elements of the pivot are greater than the pivot.
Sort the subarray to the left side of the pivot element and subarray to the right side of pivot recursively.

Given list of elements in an array:
99, 54, 64, 23, 12, 09, 45, 32, 19, 65, 89

1) Chose the first element as ivot.

99, 54, 64, 23, 12, 09, 45, 32, 19, 65, 89

2) Search from the left side that is greater than the pivot and search from the right side that is less than the pivot.

99, 54, 64, 23, 12, 09, 45, 32, 19, 65, 89

Here there is no element greater than the pivot. So swap with pivot.

89, 54, 64, 23, 12, 09, 45, 32, 19, 65, 99

3) At this point, left side array is less than the pivot. So again sort the left side subarray 89, 54, 64, 23, 12, 09, 45, 32, 19, 65 using 89 as the pivot

89, 54, 64, 23, 12, 09, 45, 32, 19, 65, 99

4) Search from the left side that is greater than the pivot and search from the right side that is less than the pivot.

89, 54, 64, 23, 12, 09, 45, 32, 19, 65, 99

Here there is no element greater than the pivot. So swap with pivot.

65, 64, 23, 12, 09, 45, 32, 19, 89, 99

5) At this point, the left side array is less than the pivot, right side elements are greater than the pivot(89). So again sort the left side subarray 65, 64, 23, 12, 09, 45, 32, 19 using 65 as the pivot

65, 64, 23, 12, 09, 45, 32, 19, 89, 99

6) Search from the left side that is greater than the pivot and search from the right side that is less than the pivot.

65, 64, 23, 12, 09, 45, 32, 19, 89, 99

Here there is no element greater than the pivot. So swap with pivot.

19, 64, 23, 12, 09, 45, 32, 65, 89, 99

7) At this point, the left side array is less than the pivot, right side elements are greater than the pivot(65). So again sort the left side subarray 19, 64, 23, 12, 09, 45, 32 using 19 as the pivot

19, 64, 23, 12, 09, 45, 32, 65, 89, 99

8) Search from the left side that is greater than the pivot and search from the right side that is less than the pivot.

19, 64, 23, 12, 09, 45, 32, 65, 89, 99

Swap them:

19, 09, 23, 12, 64, 45, 32, 65, 89, 99

9)  Search from the left side that is greater than the pivot and search from the right side that is less than the pivot.

19, 09, 23, 12, 64, 45, 32, 65, 89, 99

10) Search from the left side that is greater than the pivot and search from the right side that is less than the pivot.

19, 09, 23, 12, 64, 45, 32, 65, 89, 99

Swap them:

19, 09,12, 23, 64, 45, 32, 65, 89, 99

11) Here you can see two sets of array which are less than ivot and grater than pivot"

19,09,12 23,64,32,65,89,99

12) Apply the quicksort algorithm on two sets:

19,09,12 23,64,32,65,89,99

12,09,19 23,64,32,65,89,99

09,12,19 23, 32,64,65,89,99

b) Sort 69, 74, 64, 23, 12, 09, 45, 32, 19, 65, 88, 33, 60, 38 using Shell sort. Write the algorithm.

The Shell Sort: In data structures, Shell sort is nothing but a dimenshing increment sort. It is same as insertion sort but the difference is by breaking list into number of smller sublists. We seperate these sublists usig the key by assuming to the shell sort.

b) Sort

69, 74, 64, 23, 12, 09, 45, 32, 19, 65, 88, 33, 60, 38

Let us assume h as 7 such that each list contains 7 elements and compare two sublists as like we do in insertion sort.

69, 74, 64, 23, 12, 09, 45, 32, 19, 65, 88, 33, 60, 38

Compare {69,32} {74,19} {64,65} {23,88} {12,33} {09,60} {45,38} and swap accordingly.

32,19,64,23,12,09,38,69,74,65,88,33,60,45

Now, Let us assume h as 2 such that each list contains 2 elements and compare two sublists as like we do in insertion sort.

32,19,64,23,12,09,38,69,74,65,88,33,60,45

32,19, 64,23, 12,09, 38,69, 74,65 88,33, 60,45

Sort accordinlgly:

19,32 23,64 09,12 38,69 74,65 33,88, 45,60

19,23 32,64 09,12 38,69 65,74 33,45 60,88

09,12 19,23 32,64 38,69 65,74 33,45 60,88

As we can see, left side subset is sorted. Let us apply shell sort on remaining elements.

09,12,19,23 32,64 33,45 38,69 60,88 65,74

Now, Let us assume h as 1 such that each list contains 1 elements and compare two sublists as like we do in insertion sort.

09,12,19,23 32, 64 33, 45 38, 69 60, 88 65, 74

09,12,19,23 32, 33, 64, 38, 45, 60, 69, 65, 88, 74

09,12,19,23 32, 33, 38, 45, 60, 64, 69, 65, 74, 88

09,12,19,23 32, 33, 38, 45, 60, 64, 65, 69, 74, 88