Problem
Suppose there is an array with numbers :
1, 14, 5, k, 4, 2, 54, k, 87, 98, 3, 1, 32
Output for this can be assuming k =20
1,14,5,4,2,3,1,k,k,54,87,98,32
Now sort this array in a way all k are in middle and all values on left of k are smaller (in any order) and on right are larger (in any order)
Note: k is an integer value within range of 1 - 32768
Follow up: Sorting is ok. what sorting you want to use ? still is sorting necessary ? are there any other approaches ?
Follow up: Used External array with 2 pointers and 3 pointers approach. They wanted more efficient solution.
Solution
/*
============================================================================
Author : James Chen
Email : a.james.chen@gmail.com
Description : Three ways sorting
Created Date : 17-06-2013
Last Modified :
============================================================================
*/
#include <iostream>
#include <iomanip>
#include <algorithm>
using namespace std;
void ThreeWaysSorting(int* arr, int len, int key)
{
int bottom(-1);
int top(len);
int i(0);
while(i < top){
if(arr[i] < key){
swap(arr[++bottom], arr[i]);
i++;
}
else if(arr[i] == key){
i++;
}
else{
swap(arr[--top], arr[i]);
}
}
}
int main(int argc, char* argv[])
{
int testCase[] = {1, 14, 5, 20, 4, 2, 54, 20, 87, 98, 3, 1, 32 };
int len = sizeof(testCase)/sizeof(testCase[0]);
int k = 20;
for(k = 0; k < len; ++k){
cout << "Before sorting" << endl;
random_shuffle(testCase, testCase + len);
for(int i = 0; i < len; ++i){
cout << setw(4) << testCase[i];
}
cout << endl;
cout << "The k is " << testCase[k] << endl;
ThreeWaysSorting(testCase, len, testCase[k]);
cout << "After sorting" << endl;
for(int i = 0; i < len; ++i){
cout << setw(4) << testCase[i];
}
cout << endl;
cout << "----------------------------------------" << endl;
}
return 0;
}
Output
Before sorting
32 14 98 5 1 1 20 20 4 54 87 2 3
The k is 32
After sorting
14 3 5 1 1 20 20 4 2 32 87 54 98
----------------------------------------
Before sorting
2 32 54 4 1 1 5 87 20 20 98 14 3
The k is 32
After sorting
2 3 4 1 1 5 14 20 20 32 98 87 54
----------------------------------------
Before sorting
20 32 5 4 1 2 1 20 3 54 98 14 87
The k is 5
After sorting
3 1 4 1 2 5 20 32 54 98 14 87 20
----------------------------------------
Before sorting
14 4 20 98 20 5 2 1 1 87 3 54 32
The k is 98
After sorting
14 4 20 20 5 2 1 1 87 3 54 32 98
----------------------------------------
Before sorting
14 32 4 3 1 1 54 87 5 20 2 98 20
The k is 1
After sorting
1 1 3 4 32 54 87 5 20 2 98 20 14
----------------------------------------
Before sorting
5 1 14 3 2 20 87 54 1 4 98 32 20
The k is 20
After sorting
5 1 14 3 2 4 1 20 20 98 32 54 87
----------------------------------------
Before sorting
54 20 20 1 14 2 32 5 3 98 4 1 87
The k is 32
After sorting
1 20 20 1 14 2 5 3 4 32 98 87 54
----------------------------------------
Before sorting
3 14 5 4 98 87 32 20 20 1 54 2 1
The k is 20
After sorting
3 14 5 4 1 2 1 20 20 54 32 87 98
----------------------------------------
Before sorting
1 1 14 20 54 98 5 20 32 87 2 4 3
The k is 32
After sorting
1 1 14 20 3 4 5 20 2 32 87 98 54
----------------------------------------
Before sorting
3 20 54 1 5 1 2 32 87 98 20 14 4
The k is 98
After sorting
3 20 54 1 5 1 2 32 87 20 14 4 98
----------------------------------------
Before sorting
54 20 4 3 87 1 98 14 1 2 32 20 5
The k is 32
After sorting
5 20 4 3 20 1 14 1 2 32 98 87 54
----------------------------------------
Before sorting
98 4 3 1 5 20 2 32 20 54 14 1 87
The k is 1
After sorting
1 1 3 5 20 2 32 20 54 14 4 87 98
----------------------------------------
Before sorting
1 5 3 32 1 2 4 54 20 98 14 20 87
The k is 87
After sorting
1 5 3 32 1 2 4 54 20 14 20 87 98
----------------------------------------
Press any key to continue . . .