- #1
pc2-brazil
- 205
- 3
Good evening,
I have a doubt concerning the worst case scenario of the quicksort algorithm, based on the number of comparisons made by the algorithm.
Every source about this subject seems to agree that the worst case scenario is when the list to be sorted is already sorted and the pivot is the smaller element on the list. In this case, the total number of comparisons is n(n - 1)/2, where n is the number of items in the list
But it seems to me that the worst case happens when the list is sorted in decreasing order and the pivot is the first element in the list, which, in this case, would be the greatest element on the list.
For example, consider the list {4, 3, 2, 1}. I will chose the pivot as the first element. Each step of the quicksort will divide the original list as follows:
In the first step, {4, 3, 2, 1} is divided into two lists: {3, 2, 1, 4} (elements smaller than the pivot plus the pivot appended in the end) and {} (elements greater than the pivot: empty list). The first step requires 3 comparisons to find that 3, 2, 1 are smaller than 4.
Similarly, in the second step, the list {3, 2, 1, 4} is divided into {2, 1, 3} and {4}, requiring 3 comparisons (to find that 2, 1 are smaller than 3 and 4 is greater than 3).
The third step divides {2, 1, 3} into {1, 2} and {3}, requiring 2 comparisons.
The last step divides {1, 2} into {1} and {2}, requiring 1 comparison.
If I sum the number of comparisons for each step, I find 3 + 3 + 2 + 1 = 9.
In fact, if I generalize the above situation to n elements sorted in decreasing order, with the first element as the pivot, I get n(n - 1)/2 + n - 1 comparisons.
If I chose the pivot to be the smaller element on the list, and the list were sorted {1, 2, 3, 4}, the number of comparisons would be n(n - 1)/2 = 4(3)/2 = 6.
9 comparisons is greater than 6 comparisons. Why isn't it the worst case?
I have a doubt concerning the worst case scenario of the quicksort algorithm, based on the number of comparisons made by the algorithm.
Every source about this subject seems to agree that the worst case scenario is when the list to be sorted is already sorted and the pivot is the smaller element on the list. In this case, the total number of comparisons is n(n - 1)/2, where n is the number of items in the list
But it seems to me that the worst case happens when the list is sorted in decreasing order and the pivot is the first element in the list, which, in this case, would be the greatest element on the list.
For example, consider the list {4, 3, 2, 1}. I will chose the pivot as the first element. Each step of the quicksort will divide the original list as follows:
In the first step, {4, 3, 2, 1} is divided into two lists: {3, 2, 1, 4} (elements smaller than the pivot plus the pivot appended in the end) and {} (elements greater than the pivot: empty list). The first step requires 3 comparisons to find that 3, 2, 1 are smaller than 4.
Similarly, in the second step, the list {3, 2, 1, 4} is divided into {2, 1, 3} and {4}, requiring 3 comparisons (to find that 2, 1 are smaller than 3 and 4 is greater than 3).
The third step divides {2, 1, 3} into {1, 2} and {3}, requiring 2 comparisons.
The last step divides {1, 2} into {1} and {2}, requiring 1 comparison.
If I sum the number of comparisons for each step, I find 3 + 3 + 2 + 1 = 9.
In fact, if I generalize the above situation to n elements sorted in decreasing order, with the first element as the pivot, I get n(n - 1)/2 + n - 1 comparisons.
If I chose the pivot to be the smaller element on the list, and the list were sorted {1, 2, 3, 4}, the number of comparisons would be n(n - 1)/2 = 4(3)/2 = 6.
9 comparisons is greater than 6 comparisons. Why isn't it the worst case?