Do one partition step of quick sort, Lomuto style: the pivot is the last number. Scan the other numbers from left to right; each one smaller than the pivot is swapped to the end of the "smaller" part. Finally, swap the pivot into place. Print the array and the pivot's new index.
What to build
One Lomuto partition step, shown in full.
Requirements
- Use the last number as the pivot.
- Swap each number smaller than the pivot to the end of the smaller part.
- Print the array, then the pivot's new index.
Input
The first line has n (1 ≤ n ≤ 100). The second line has the n numbers.
Output
Two lines: the array after partitioning, and the pivot's index.
Constraints
1 ≤ n ≤ 100.
Example
Input:
7
7 2 9 4 3 8 5
Output:
2 4 3 5 9 8 7
3
Why it works
The numbers before index i are always smaller than the pivot. After the final swap, the pivot sits exactly where it belongs in sorted order.
Examples
7 7 2 9 4 3 8 5
2 4 3 5 9 8 7 3
4 4 3 2 1
1 3 2 4 0
Hints
Hint 1
pivot = a[n - 1]; i = 0 marks the end of the smaller part.
Hint 2
For j from 0 to n - 2: if a[j] < pivot, swap a[i] and a[j], then i++.
Hint 3
Finally swap a[i] with a[n - 1]; the pivot's index is i.
Solution
Show one correct solution (try it yourself first)
#include <stdio.h>
void swap(int *a, int *b) {
int t = *a;
*a = *b;
*b = t;
}
int partition(int a[], int lo, int hi) {
int pivot = a[hi];
int i = lo;
for (int j = lo; j < hi; j++) {
if (a[j] < pivot) {
swap(&a[i], &a[j]);
i++;
}
}
swap(&a[i], &a[hi]);
return i;
}
int main(void) {
int n;
int a[100];
scanf("%d", &n);
for (int i = 0; i < n; i++) scanf("%d", &a[i]);
int p = partition(a, 0, n - 1);
for (int i = 0; i < n; i++) {
if (i > 0) printf(" ");
printf("%d", a[i]);
}
printf("\n%d\n", p);
return 0;
}