Partitioning is the heart of quick sort. Start with the simplest version, which is allowed to go through the list more than once.
What to build
A program that lists numbers in three groups around a pivot value.
Requirements
- First print the numbers smaller than
p. - Then print the numbers equal to
p. - Then print the numbers larger than
p. - Inside each group, keep the order in which the numbers were read.
Input
The first line has n and p. The second line has the n numbers.
Output
All n numbers on one line, separated by spaces.
Constraints
1 ≤ n ≤ 100.
Example
Input:
7 5
7 2 9 5 3 8 5
Output:
2 3 5 5 7 9 8
Why it works
After this split, each group is on the correct side of the others. Quick sort does the same thing in place, then sorts the smaller and larger groups.
Examples
Example 1 · Input
7 5 7 2 9 5 3 8 5
Expected output
2 3 5 5 7 9 8
Example 2 · Input
3 10 1 2 3
Expected output
1 2 3
Hints
Hint 1
Loop over the numbers three times, once for each part.
Hint 2
Print each number in the group where it belongs, in the order it was read.
Solution
Show one correct solution (try it yourself first)
#include <stdio.h>
int main(void) {
int n, p, a[100];
scanf("%d %d", &n, &p);
for (int i = 0; i < n; i++) scanf("%d", &a[i]);
for (int i = 0; i < n; i++)
if (a[i] < p) printf("%d ", a[i]);
for (int i = 0; i < n; i++)
if (a[i] == p) printf("%d ", a[i]);
for (int i = 0; i < n; i++)
if (a[i] > p) printf("%d ", a[i]);
printf("\n");
return 0;
}