cpp-algorithms/quickSort.cpp at master · vedtopkar/cpp-algorithms · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

void quickSortRecursive(vector<int> &vec, int left, int right)
{
  int i = left;
  int j = right;
  int pivot = vec[(left + right)/2];
  cout << "Pivot: " << pivot << endl;

  while(i <= j)
  {
    while(vec[i] < pivot)
    {
      ++i;
    }
    while(vec[j] > pivot)
    {
      --j;
    }
    if(i <= j)
    {
      swap(vec[i], vec[j]);
      ++i;
      --j;
    }
  }
  if(left < j)
  {
    quickSortRecursive(vec, left, j);
  }
  if(i < right)
  {
    quickSortRecursive(vec, i, right);
  }
}

void quickSort(vector<int> &vec)
{
  int right = vec.size() - 1;
  quickSortRecursive(vec, 0, right);
}

int main()
{
  int ints[] = {32,71,12,45,26,88,53,33};
  vector<int> vec(ints, ints + sizeof(ints)/sizeof(int));

  quickSort(vec);

  cout << "Sorted vector:";
  for(vector<int>::iterator it = vec.begin(); it != vec.end(); it++)
  {
    cout << ' ' << *it;
  }

  cout << '\n';

  return 0;
}