-::QUICK SORT ALGORITHM IN DATA STRUCTURE:--

QUICK SORT ALGORITHM IN DATA STRUCTURE:-

   

                                                                                                       BY 

                                                                                                          SHEELAJ BABU

                                                                                                               B.TECH(IIIT-BGP)

WHAT IS QUICK SORT ALGORITHM ???

:- (1) QuickSort is one of the most efficient sorting algorithms and is based on the splitting of an array into smaller ones. 

(2):- Quick sort also falls into the category of divide and conquer approach of problem-solving methodology.

Quick Sort WORKING:-

1. Taking the analogical view in perspective, consider a situation where one had to sort the papers bearing the names of the students, by name. One might use the approach as follows:
1. Select a splitting value, say L. The splitting value is also known as Pivot.
2. Divide the stack of papers into two. A-L and M-Z. It is not necessary that the piles should be equal.
2. The approach used here is recursion at each split to get to the single-element array.
3. At every split, the pile was divided and then the same approach was used for the smaller piles.
4. Due to these features, quick sort is also called as partition exchange sort.

An example might come in handy to understand the concept.

Consider the following array: 50, 23, 9, 18, 61, 32

Step 1: Decide any value to be the pivot from the list (generally the last value). Suppose for two values “Low” and “High” corresponding to the first index, and last index.

In our case low is 0 and high is 5.

Values at low and high are 50 and 32 and Value of pivot is 32.

Hence, call for partitioning, rearranging the array in such a way that pivot (32) comes to its actual position. And to the left of the pivot, the array has all the elements less than it, and to the right greater than it.

In the partition function, we start from the first element and compare it with the pivot. Since 50 is greater than 32, we don’t make any change and move on to the next element 23.

Compare again with the pivot. Since 23 is less than 32, we swap 50 and 23. The array becomes 23, 50, 9, 18, 61, 32.

We move on to the next element 9 which is again less than pivot (32) thus swapping it with 50 makes our array as

23, 9, 50, 18, 61, 32.

Similarly, for next element 18 which is less than 32, the array becomes

23, 9, 18, 50, 61, 32 Now 61 is greater than pivot (32), hence no changes.

Lastly, we swap our pivot with 50 so that it comes to the correct position.

Thus the pivot (32) comes at its actual position and all elements to its left are lesser, and all elements to the right are greater than itself.

Step 2: Hence the array after the first step becomes

23, 9, 18, 32, 61, 50

Step 3: Now USING the list is divided into two parts:-

1. Sublist before pivot
2. Sublist after pivot

Sub-list before and after Pivot

Step 4: Repeat the steps for these sublists again.

The final array thus becomes:- 9, 18, 23, 32, 50, 61..>>>

SO THIS IS BEST SOLUTION FOR QUICK SORTING....