I'm afraid TNTSuperMan is correct. In this case, it looks like the implementation of this Quick has a pivot that is found in a non-random assignment with no comparisons. It is tough to use a system like this since from the left, from the right, or even exactly in the center (with a special input), there is a way for the pivot to not guarantee any additional items in the partition it creates. I am going to guess that this implementation uses an LR pointer partition scheme with a left or right pivot. When it tries to sort, sometimes, either end of the partition scheme would only result in the left pivot being the least or the right pivot being the greatest item. However, the sort doesn't know that until it tries and finds nothing. This is considered a single scan. Abusing the weaknesses of algorithms that have weak strategies is not that difficult. A reversed array tends to kill algorithms that rely on there being some sortedness amidst the unsortedness in the array, which Quicksorts with a left or right pivot traditionally rely on. However, on a reversed array, no sortedness exists. Thus, nothing less than or greater than the pivot, and the algorithm scans a subset of the N items O(N) times, and N * O(N) = O(N^2).
@@PCBoyStudios Bro chill 💀 The title was "Sometimes it isn't" not that it's always slow. Anyways, this implementation uses a classic Lomuto Partition, implementing the standard quicksort. If you look at the quicksort algorithm, you will see my implementation is the standard. The point of the video though, was to show quick sort's weakness, and how in some cases, it is not a reliable algorithm like merge sort or heap sort is.
Quick sort is usually fast.
but Worst case is O(n^2).
@@TNTSuperMan did you even watch the video
I'm afraid TNTSuperMan is correct.
In this case, it looks like the implementation of this Quick has a pivot that is found in a non-random assignment with no comparisons. It is tough to use a system like this since from the left, from the right, or even exactly in the center (with a special input), there is a way for the pivot to not guarantee any additional items in the partition it creates.
I am going to guess that this implementation uses an LR pointer partition scheme with a left or right pivot. When it tries to sort, sometimes, either end of the partition scheme would only result in the left pivot being the least or the right pivot being the greatest item. However, the sort doesn't know that until it tries and finds nothing. This is considered a single scan.
Abusing the weaknesses of algorithms that have weak strategies is not that difficult. A reversed array tends to kill algorithms that rely on there being some sortedness amidst the unsortedness in the array, which Quicksorts with a left or right pivot traditionally rely on. However, on a reversed array, no sortedness exists. Thus, nothing less than or greater than the pivot, and the algorithm scans a subset of the N items O(N) times, and N * O(N) = O(N^2).
@@PCBoyStudios Bro chill 💀
The title was "Sometimes it isn't"
not that it's always slow.
Anyways, this implementation uses a classic Lomuto Partition, implementing the standard quicksort. If you look at the quicksort algorithm, you will see my implementation is the standard. The point of the video though, was to show quick sort's weakness, and how in some cases, it is not a reliable algorithm like merge sort or heap sort is.