1: //TestStuff20141022Lab.cpp
2: //Wednesday, October 22, 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:
15: void Partition
16: (
17: vector<int>& v, //inout
18: vector<int>::size_type low, //in
19: vector<int>::size_type high, //in
20: vector<int>::size_type& pivotIndex //out
21: )
22: {
23: swap(v.at(low), v.at((low + high) / 2));
24: int pivot = v.at(low);
25: vector<int>::size_type lastSmall = low;
26: vector<int>::size_type i;
27: for (i = low + 1; i <= high; i++)
28: if (v.at(i) < pivot)
29: {
30: ++lastSmall;
31: swap(v.at(lastSmall), v.at(i));
32: }
33: swap(v.at(low), v.at(lastSmall));
34: pivotIndex = lastSmall;
35: }
36:
37:
38: void FindKthSmallest
39: (
40: vector<int> &v, //inout
41: vector<int>::size_type low, //in
42: vector<int>::size_type high, //in
43: vector<int>::size_type k //in
44: )
45: {
46: if (low < high)
47: {
48: vector<int>::size_type pivotIndex;
49: Partition(v, low, high, pivotIndex);
50: if (k < pivotIndex + 1)
51: FindKthSmallest(v, low, pivotIndex - 1, k);
52: if (k > pivotIndex + 1)
53: FindKthSmallest(v, pivotIndex + 1, high, k);
54: }
55: }
56:
57: int main(int argc, char* argv[])
58: {
59: vector<int> v;
60: RandomGenerator g;
61: for (int i = 1; i < 15; i++) v.push_back(g.getNextInt(10, 99));
62: cout << endl;
63: for (vector<int>::size_type i = 0; i < v.size(); i++)
64: cout << v.at(i) << " ";
65: cout << endl;
66: FindKthSmallest(v, 0, v.size() - 1, 7);
67: //for (vector<int>::size_type i = 0; i < v.size(); i++)
68: //cout << v.at(i) << " ";
69: //cout << endl;
70: }
71: