1: //TestStuff20141020Lab.cpp
2: //Monday, October 20, 2014
3:
4: #include <iostream>
5: #include <vector>
6: #include <algorithm> //for swap
7: using namespace std;
8:
9: #include "utilities.h"
10: using Scobey::Pause;
11: using Scobey::RandomGenerator;
12:
13:
14: void Partition
15: (
16: vector<int>& v, //inout
17: vector<int>::size_type low, //in
18: vector<int>::size_type high, //in
19: vector<int>::size_type& pivotIndex //out
20: )
21: {
22: swap(v.at(low), v.at((low + high) / 2));
23: int pivot = v.at(low);
24: vector<int>::size_type lastSmall = low;
25: vector<int>::size_type i;
26: for (i = low + 1; i <= high; i++)
27: if (v.at(i) < pivot)
28: {
29: ++lastSmall;
30: swap(v.at(lastSmall), v.at(i));
31: }
32: swap(v.at(low), v.at(lastSmall));
33: pivotIndex = lastSmall;
34: }
35:
36: void FindKthSmallest
37: (
38: vector<int> &v, //inout
39: vector<int>::size_type low, //in
40: vector<int>::size_type high, //in
41: vector<int>::size_type k //in
42: )
43: {
44: if (low < high)
45: {
46: vector<int>::size_type pivotIndex;
47: Partition(v, low, high, pivotIndex);
48: if (k < pivotIndex + 1)
49: FindKthSmallest(v, low, pivotIndex - 1, k);
50: if (k > pivotIndex + 1)
51: FindKthSmallest(v, pivotIndex + 1, high, k);
52: }
53: }
54:
55:
56: int main(int argc, char* argv[])
57: {
58: vector<int> v;
59: RandomGenerator g;
60: for (int i = 1; i < 15; i++) v.push_back(g.getNextInt(10, 99));
61: cout << endl;
62: for (vector<int>::size_type i = 0; i < v.size(); i++)
63: cout << v.at(i) << " ";
64: cout << endl;
65: FindKthSmallest(v, 0, v.size() - 1, 7);
66: for (vector<int>::size_type i = 0; i < v.size(); i++)
67: cout << v.at(i) << " ";
68: cout << endl;
69: }
70:
71: