Menu
Source code of simple quick sort implementation using array ascending order in c programming language. Source code of simple quick sort implementation using array ascending order in c programming language. Void quicksort(int [10],int,int).
The quick sort uses divide and conquer to gain the same advantagesas the merge sort, while not using additional storage. As a trade-off,however, it is possible that the list may not be divided in half. Whenthis happens, we will see that performance is diminished.
A quick sort first selects a value, which is called the pivot value.Although there are many different ways to choose the pivot value, wewill simply use the first item in the list. The role of the pivot valueis to assist with splitting the list. The actual position where thepivot value belongs in the final sorted list, commonly called thesplit point, will be used to divide the list for subsequent calls tothe quick sort.
Figure 12 shows that 54 will serve as our first pivot value.Since we have looked at this example a few times already, we know that54 will eventually end up in the position currently holding 31. Thepartition process will happen next. It will find the split point andat the same time move other items to the appropriate side of the list,either less than or greater than the pivot value.
Figure 12: The First Pivot Value for a Quick Sort¶
Partitioning begins by locating two position markers—let’s call them
leftmark
and rightmark
—at the beginning and end of the remainingitems in the list (positions 1 and 8 in Figure 13). The goalof the partition process is to move items that are on the wrong sidewith respect to the pivot value while also converging on the splitpoint. Figure 13 shows this process as we locate the positionof 54.We begin by incrementing
leftmark
until we locate a value that isgreater than the pivot value. We then decrement rightmark
until wefind a value that is less than the pivot value. At this point we havediscovered two items that are out of place with respect to the eventualsplit point. For our example, this occurs at 93 and 20. Now we canexchange these two items and then repeat the process again.At the point where
rightmark
becomes less than leftmark
, westop. The position of rightmark
is now the split point. The pivotvalue can be exchanged with the contents of the split point and thepivot value is now in place (Figure 14). In addition, all theitems to the left of the split point are less than the pivot value, andall the items to the right of the split point are greater than the pivotvalue. The list can now be divided at the split point and the quick sortcan be invoked recursively on the two halves.Figure 14: Completing the Partition Process to Find the Split Point for 54¶
The
quickSort
function shown in ActiveCode 1 invokes a recursivefunction, quickSortHelper
. quickSortHelper
begins with the samebase case as the merge sort. If the length of the list is less than orequal to one, it is already sorted. If it is greater, then it can bepartitioned and recursively sorted. The partition
functionimplements the process described earlier.To analyze the
quickSort
function, note that for a list of lengthn, if the partition always occurs in the middle of the list, therewill again be (log n) divisions. In order to find the splitpoint, each of the n items needs to be checked against the pivotvalue. The result is (nlog n). In addition, there is no needfor additional memory as in the merge sort process.Unfortunately, in the worst case, the split points may not be in themiddle and can be very skewed to the left or the right, leaving a veryuneven division. In this case, sorting a list of n items divides intosorting a list of 0 items and a list of (n-1) items. Thensorting a list of (n-1) divides into a list of size 0 and a listof size (n-2), and so on. The result is an (O(n^{2}))sort with all of the overhead that recursion requires.
We mentioned earlier that there are different ways to choose the pivotvalue. In particular, we can attempt to alleviate some of the potentialfor an uneven division by using a technique called median of three.To choose the pivot value, we will consider the first, the middle, andthe last element in the list. In our example, those are 54, 77, and 20.Now pick the median value, in our case 54, and use it for the pivotvalue (of course, that was the pivot value we used originally). The ideais that in the case where the the first item in the list does not belongtoward the middle of the list, the median of three will choose a better“middle” value. This will be particularly useful when the original listis somewhat sorted to begin with. We leave the implementation of thispivot value selection as an exercise.
Self Check
- [9, 3, 10, 13, 12]
- It's important to remember that quicksort works on the entire list and sorts it in place.
- [9, 3, 10, 13, 12, 14]
- Remember quicksort works on the entire list and sorts it in place.
- [9, 3, 10, 13, 12, 14, 17, 16, 15, 19]
- The first partitioning works on the entire list, and the second partitioning works on the left partition not the right.
- [9, 3, 10, 13, 12, 14, 19, 16, 15, 17]
- The first partitioning works on the entire list, and the second partitioning works on the left partition.
Q-2: Given the following list of numbers [14, 17, 13, 15, 19, 10, 3, 16, 9, 12] which answer shows the contents of the list after the second partitioning according to the quicksort algorithm?
- 1
- The three numbers used in selecting the pivot are 1, 9, 19. 1 is not the median, and would be a very bad choice for the pivot since it is the smallest number in the list.
- 9
- Good job.
- 16
- although 16 would be the median of 1, 16, 19 the middle is at len(list) // 2.
- 19
- the three numbers used in selecting the pivot are 1, 9, 19. 9 is the median. 19 would be a bad choice since it is almost the largest.
Q-3: Given the following list of numbers [1, 20, 11, 5, 2, 9, 16, 14, 13, 19] what would be the first pivot value using the median of 3 method?
- Shell Sort
- Shell sort is about ``n^1.5``
- Quick Sort
- Quick sort can be O(n log n), but if the pivot points are not well chosen and the list is just so, it can be O(n^2).
- Merge Sort
- Merge Sort is the only guaranteed O(n log n) even in the worst case. The cost is that merge sort uses more memory.
- Insertion Sort
- Insertion sort is ``O(n^2)``
Q-4: Which of the following sort algorithms are guaranteed to be O(n log n) even in the worst case?