It has been over a month since I posted. I've been really busy with all of my classes.
So, instead of going too in depth with anything, I'm just going to share some code we've written. This is a QuickSort Algorithm that we adapted from the MIT Intro to Algorithms book. We just finished it last night (less than 12 hours ago), so it's not fully tested.
1: #ifndef _QUICKSORT_H
2: #define _QUICKSORT_H
3:
4: #include <vector>
5:
6: using namespace std;
7:
8: namespace QuickSort
9: {
10:
11: /*
12: QuickSort Algorithm using Templates
13:
14: Algorithm was adapted from:
15: Introduction to Algorithms
16: By Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein
17: Contributor Thomas H. Cormen
18: Edition: 2, illustrated
19: Published by MIT Press, 2001
20: ISBN 0262032937, 9780262032933
21: 1180 pages
22: Accessed March 2009
23: via http://books.google.com/books?id=NLngYyWFl_YC
24: See pages 145-147
25:
26: */
27: template<class T>
28: class QuickSort
29: {
30: public:
31: vector<T> *sortingArray;
32: int left;
33: int right;
34:
35: // Constructors
36: QuickSort();
37: QuickSort(vector<T> *sortArray);
38: QuickSort(vector<T> *sortArray, int startIndex, int endIndex);
39:
40: /**********************************************************************
41: * Partition and Swap Functions
42: **********************************************************************/
43: int Partition(vector<T> *sortArray, int startIndex, int endIndex);
44: void Swap(int l, int k);
45:
46: };
47:
48: template<class T>
49: QuickSort<T>::QuickSort()
50: {
51: sortingArray = new vector<T>();
52: left = 0;
53: right = 0;
54: }
55:
56: template<class T>
57: QuickSort<T>::QuickSort(vector<T> *sortArray)
58: {
59: int startIndex = 0;
60: int endIndex = 0;
61:
62: endIndex = (int)(*sortArray).size() - 1;
63:
64: QuickSort(sortArray, startIndex, endIndex);
65: }
66:
67: template<class T>
68: QuickSort<T>::QuickSort(vector<T> *sortArray, int startIndex, int endIndex)
69: {
70: if(startIndex >= endIndex)
71: {
72: return;
73: }
74:
75: // *initialize* the array
76: sortingArray = sortArray;
77:
78: // For instance: 1..n
79: left = startIndex;
80: right = endIndex;
81:
82: if(left < right)
83: {
84: // get pivot
85: int pivot = Partition(sortingArray, left, right);
86:
87: // sort left side
88: QuickSort(sortingArray, left, (pivot-1));
89:
90: // sort right side
91: QuickSort(sortingArray, (pivot+1), right);
92: }
93: }
94:
95: template<class T>
96: int QuickSort<T>::Partition(vector<T> *sortArray, int startIndex, int endIndex)
97: {
98: // initially this start - 1 when startIndex is 0.
99: int l = startIndex - 1;
100: int k = endIndex;
101:
102: for(int i = startIndex; i <= k - 1; i++)
103: {
104: // Go until you find a value smaller than the last value.
105: if((*sortArray)[i] <= (*sortArray)[k])
106: {
107: // increment l
108: l++;
109:
110: // swap i and j
111: // NOTE: this is supposed to swap j with itself the first time.
112: Swap(l, i);
113: }
114: }
115:
116: // when loop is finished, swap
117: Swap(l + 1, k);
118:
119: return l + 1;
120: }
121:
122: template<class T>
123: void QuickSort<T>::Swap(int l, int k)
124: {
125: // create temp variable
126: T tmp;
127:
128: // store first element in temp
129: tmp =(*sortingArray)[l];
130:
131: // swap second element to first element
132: (*sortingArray)[l] = (*sortingArray)[k];
133:
134: // put temp variable in second element
135: (*sortingArray)[k] = tmp;
136: }
137:
138: }
139:
140: #endif
No comments:
Post a Comment