Return to Answer

When describing quicksort partitioning, your v is typically called the "pivot". The code would be clearer if you named the variable according to that convention.

You always choose a[lo] as the pivot. However, that produces pathological performance when the input array is already sorted.

I would prefer to see

while(a[i] < v):

 i += 1
 if (i == hi): break

... written as

while i < hi and a[i] < pivot:
 i += 1

Array index bounds usually work better when specified as inclusive-exclusive ranges, such that sort(a, lo, hi) means "sort a where lo ≤ index ≤ hi". This is a common convention — you can see it in Python's range() and slicings. Also, Java's Arrays.sort(a, fromIndex, toIndex) works with inclusive-exclusive ranges.

Some nice properties of inclusive-exclusive ranges are:

• hi - lo gives you the number of elements in the range.
• When creating a range for the entire array a, hi is just len(a). You save a "-1".
• When splitting [lo, hi) into two consecutive ranges, it becomes [lo, mid) and [mid, hi). You save a "-1".

When describing quicksort partitioning, your v is typically called the "pivot". The code would be clearer if you named the variable according to that convention.

You always choose a[lo] as the pivot. However, that produces pathological performance when the input array is already sorted.

I would prefer to see

while(a[i] < v):

 i += 1
 if (i == hi): break

... written as

while i < hi and a[i] < pivot:
 i += 1

Array index bounds usually work better when specified as inclusive-exclusive ranges, such that sort(a, lo, hi) means "sort a where lo ≤ index < hi". This is a common convention — you can see it in Python's range() and slicings. Also, Java's Arrays.sort(a, fromIndex, toIndex) works with inclusive-exclusive ranges.

Some nice properties of inclusive-exclusive ranges are:

• hi - lo gives you the number of elements in the range.
• When creating a range for the entire array a, hi is just len(a). You save a "-1".
• When splitting [lo, hi) into two consecutive ranges, it becomes [lo, mid) and [mid, hi). You save a "-1".
• In Python, you can conveniently write for i in range(lo, hi) for the most common type of iteration. (Admittedly, iterating backwards is uglier, but it's less common.)

When describing quicksort partitioning, your v is typically called the "pivot". The code would be clearer if you named the variable according to that convention.

You always choose a[lo] as the pivot. However, that produces pathological performance when the input array is already sorted.

I would prefer to see

while(a[i] < v):

 i += 1
 if (i == hi): break

... written as

while i < hi and a[i] < pivot:
 i += 1

Array index bounds usually work better when specified as inclusive-exclusive ranges, such that sort(a, lo, hi) means "sort a where lo ≤ index ≤ hi". This is a common convention — you can see it in Python's range() and slicings. Also, Java's Arrays.sort(a, fromIndex, toIndex) works with inclusive-exclusive ranges.

When describing quicksort partitioning, your v is typically called the "pivot". The code would be clearer if you named the variable according to that convention.

You always choose a[lo] as the pivot. However, that produces pathological performance when the input array is already sorted.

I would prefer to see

while(a[i] < v):

 i += 1
 if (i == hi): break

... written as

while i < hi and a[i] < pivot:
 i += 1

Array index bounds usually work better when specified as inclusive-exclusive ranges, such that sort(a, lo, hi) means "sort a where lo ≤ index ≤ hi". This is a common convention — you can see it in Python's range() and slicings. Also, Java's Arrays.sort(a, fromIndex, toIndex) works with inclusive-exclusive ranges.

Some nice properties of inclusive-exclusive ranges are:

• hi - lo gives you the number of elements in the range.
• When creating a range for the entire array a, hi is just len(a). You save a "-1".
• When splitting [lo, hi) into two consecutive ranges, it becomes [lo, mid) and [mid, hi). You save a "-1".