Objective

Implement partition, which rearranges the range a[lo..hi] around the pivot a[hi] following the Lomuto scheme and returns the index the pivot ends up on.

Steps

• a points to an array of int. lo and hi are indices into it and the range a[lo..hi] covers both ends. Assume lo <= hi and that both index a real element.
• The pivot is a[hi], the last element of the range. Never the first element, never a median of three.
• Lomuto scheme: hold a boundary index i starting at lo, walk j from lo to hi - 1, and each time a[j] <= pivot, swap a[i] with a[j] and move i forward by one.
• Once the walk is over, swap a[i] with a[hi] and return i. That last swap is what drops the pivot into its place.
• The comparison is <=, so a value equal to the pivot goes to the left side. A < there yields a different returned index and a different array, and Grademe compares both.
• On return, every element before the returned index is less than or equal to the pivot, and every element after it is strictly greater.
• lo may equal hi. The range holds one element, nothing moves, and the answer is lo.
• lo and hi need not span the whole array. Anything before lo or after hi must come out of the call byte for byte as it went in, and you must not read there either.
• No library call is available, so write the swap yourself.
• Grademe prints p= followed by your returned index, then the whole array between brackets, values separated by a comma and a space. The examples below show that line.

Objective

Implement partition, which rearranges the range a[lo..hi] around the pivot a[hi] following the Lomuto scheme and returns the index the pivot ends up on.

Steps

• a points to an array of int. lo and hi are indices into it and the range a[lo..hi] covers both ends. Assume lo <= hi and that both index a real element.
• The pivot is a[hi], the last element of the range. Never the first element, never a median of three.
• Lomuto scheme: hold a boundary index i starting at lo, walk j from lo to hi - 1, and each time a[j] <= pivot, swap a[i] with a[j] and move i forward by one.
• Once the walk is over, swap a[i] with a[hi] and return i. That last swap is what drops the pivot into its place.
• The comparison is <=, so a value equal to the pivot goes to the left side. A < there yields a different returned index and a different array, and Grademe compares both.
• On return, every element before the returned index is less than or equal to the pivot, and every element after it is strictly greater.
• lo may equal hi. The range holds one element, nothing moves, and the answer is lo.
• lo and hi need not span the whole array. Anything before lo or after hi must come out of the call byte for byte as it went in, and you must not read there either.
• No library call is available, so write the swap yourself.
• Grademe prints p= followed by your returned index, then the whole array between brackets, values separated by a comma and a space. The examples below show that line.