|
12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758 |
- //============================================================================
- // Name : quiz3.cpp
- // Author : Christos Choutouridis
- // Version :
- // Copyright : Your copyright notice
- // Description : Hello World in C++, Ansi-style
- //============================================================================
-
-
-
- int v[] = {
- 3, 10, 8, 2, 7, 1, 5, 9, 6, 4
- };
-
-
- void swap (int i, int j) {
- int t = v[i];
- v[i] = v[j];
- v[j] = t;
- }
-
- // partition(int f, int l) : permutes the values in vector v[]
- // between positions f and l, using as pivot the element v[l], such
- // that
- // f <= i < p ==> v[i] <= v[p]
- // p < i <= l ==> v[p] < v[i]
- // The function returns the position p of the pivot.
- int partition(int f, int l) {
- int pivot = v[l]; // element v[l] is the pivot
- int i = f; // i points to the beginning of the vector
-
- // loop over vector
- for (int j = f; j < l; j++)
- if (v[j] < pivot) // element smaller than pivot
- swap(i++,j); // swap it with position pointed by i
-
- swap(i, l ); // swap pivot to its correct position
- return (i); // return pivot's position
- }
-
- // qsort(int f, int l) : sorts the elements of v[] between positions f:l
- void qsort(int f, int l) {
- int pivot;
- if (f < l) {
- pivot = partition(f, l);
-
- qsort(f, pivot - 1); // Before pi
- qsort(pivot + 1, l); // After pi
- }
- }
-
-
- int main() {
- int n = 10;
-
- qsort (0, 9);
- return 0;
- }
|