Return to Answer

edited body

Source Link

edited Sep 14, 2019 at 11:31

user555045

It's a relatively basic quicksort with no "fancy features", so it has the same issues that basic quicksort always has:

O(n) space usage. When using recursion, that easily means "unexpected termination". When using an explicit stack, it means potentially wasting a ton of memory. The solution is to use recursion (or emulated recursion, with the explicit stack) only for the largestsmallest half of the partition, and loop (tail recursion) for the smallerlarger half.
O(n²) time in common cases. Picking the last (or first) element as the pivot has bad behavior for common inputs. Picking the middle element is easy and at least a little better, there are more advanced options such as median-of-3 etc. In most cases the O(n²) worst case stays, for example with the famous "median of 3 killer sequence", but a rare worst case has less impact than a common worst case.
Inefficient partitioning (Lumoto's scheme). Hoare's original partioning scheme on average performs 1/3rd as many swaps. It is more complicated to code, but partitioning is the heart of quicksort: efficient partitioning is what makes quicksort quick.

It's a relatively basic quicksort with no "fancy features", so it has the same issues that basic quicksort always has:

O(n) space usage. When using recursion, that easily means "unexpected termination". When using an explicit stack, it means potentially wasting a ton of memory. The solution is to use recursion (or emulated recursion, with the explicit stack) only for the largest half of the partition, and loop (tail recursion) for the smaller half.
O(n²) time in common cases. Picking the last (or first) element as the pivot has bad behavior for common inputs. Picking the middle element is easy and at least a little better, there are more advanced options such as median-of-3 etc. In most cases the O(n²) worst case stays, for example with the famous "median of 3 killer sequence", but a rare worst case has less impact than a common worst case.
Inefficient partitioning (Lumoto's scheme). Hoare's original partioning scheme on average performs 1/3rd as many swaps. It is more complicated to code, but partitioning is the heart of quicksort: efficient partitioning is what makes quicksort quick.

It's a relatively basic quicksort with no "fancy features", so it has the same issues that basic quicksort always has:

O(n) space usage. When using recursion, that easily means "unexpected termination". When using an explicit stack, it means potentially wasting a ton of memory. The solution is to use recursion (or emulated recursion, with the explicit stack) only for the smallest half of the partition, and loop (tail recursion) for the larger half.
O(n²) time in common cases. Picking the last (or first) element as the pivot has bad behavior for common inputs. Picking the middle element is easy and at least a little better, there are more advanced options such as median-of-3 etc. In most cases the O(n²) worst case stays, for example with the famous "median of 3 killer sequence", but a rare worst case has less impact than a common worst case.
Inefficient partitioning (Lumoto's scheme). Hoare's original partioning scheme on average performs 1/3rd as many swaps. It is more complicated to code, but partitioning is the heart of quicksort: efficient partitioning is what makes quicksort quick.

Source Link

answered Sep 14, 2019 at 10:35

user555045

It's a relatively basic quicksort with no "fancy features", so it has the same issues that basic quicksort always has:

O(n) space usage. When using recursion, that easily means "unexpected termination". When using an explicit stack, it means potentially wasting a ton of memory. The solution is to use recursion (or emulated recursion, with the explicit stack) only for the largest half of the partition, and loop (tail recursion) for the smaller half.
O(n²) time in common cases. Picking the last (or first) element as the pivot has bad behavior for common inputs. Picking the middle element is easy and at least a little better, there are more advanced options such as median-of-3 etc. In most cases the O(n²) worst case stays, for example with the famous "median of 3 killer sequence", but a rare worst case has less impact than a common worst case.
Inefficient partitioning (Lumoto's scheme). Hoare's original partioning scheme on average performs 1/3rd as many swaps. It is more complicated to code, but partitioning is the heart of quicksort: efficient partitioning is what makes quicksort quick.