Java – can the modified quicksort be the best case of O (n)?

It is generally believed that the best case for quick sorting is O (nlogn), because each partition of the array is about half Others say that the worst case is order n ^ 2, assuming that the array has been sorted

Can't we modify quicksort by setting a Boolean value called swap? For example, if there is no initial exchange at the first pass, we can assume that the array has been sorted, so the data is no longer partitioned

I know that the modified bubble sort uses it by checking the exchange, allowing the best case to be o (n) instead of O (n ^ 2) Can this method be applied to quick sorting? Why or why not?

Solution

There is a mistake in your method

Our pivot element is 5 After the first pass, there is no exchange (because 4 and 3 are small), but the array is not sorted So you have to start dividing it, which leads to n log n