Algunos ejercicios de TDA I.
[z.facultad/75.29/ejercicios.git] / quicksort.cpp
1
2 #include <vector>
3 #include <string>
4 #include <iterator>
5 #include <iostream>
6 #include <algorithm>
7
8 using namespace std;
9
10 int pivote(vector<int>& v, int val, int ini, int fin)
11 {
12         int i = ini + 1;
13         int p = fin - 1;
14         while (v[i] <= val && i < fin) ++i;
15         while (v[p] > val) --p;
16         while (i < p)
17         {
18                 swap(v[i], v[p]);
19                 while (v[i] <= val) ++i;
20                 while (v[p] > val) --p;
21         }
22         swap(v[ini], v[p]);
23         return p;
24 }
25
26 void quicksort(vector<int>& v, int ini, int fin)
27 {
28         if (ini < fin)
29         {
30                 int p = pivote(v, v[ini], ini, fin);
31                 quicksort(v, ini, p);
32                 quicksort(v, p+1, fin);
33         }
34 }
35
36 int main()
37 {
38         int n;
39         vector<int> v;
40         while (cin >> n)
41         {
42                 v.push_back(n);
43         }
44         quicksort(v, 0, v.size());
45         copy(v.begin(), v.end(), ostream_iterator<int>(cout, " "));
46         return 0;
47 }
48