Yurttas/PL/OOL/Cplusplus/F/05/04/03/00/quicksort.cpp

 1/*
 2   Copyright(C) 2002
 3   All Rights Reserved. Salih Yurttas, ZCubes, BitsOfCode Software Systems, Inc..
 4
 5   Permission to use, copy, modify, and distribute this
 6   software and its documentation for EDUCATIONAL purposes
 7   and without fee is hereby granted provided that this
 8   copyright notice appears in all copies.
 9
10   date   : January 1, 2002.
11   author : Salih Yurttas.
12
13   quicksort.cpp
14*/
15
16
17#include <vector>
18
19using namespace std;
20
21template<class T, class C>
22int partition(vector<T>& list,
23              int i,
24              int j,
25              const C& compare) {
26
27  int middle=(i+j)/2;            /* middle as the pivot       */
28
29  T pivot=list[middle];
30  list[middle]=list[i];
31  list[i]=pivot;
32
33  int p=i;
34
35  for(int k=i+1; k<=j; k++)
36    if(compare(list[k],pivot)) { /* elements less than pivot  */
37      T temp=list[++p];          /* replaced by list[++p]     */
38      list[p]=list[k];
39      list[k]=temp;
40    }
41
42  T temp=list[i];                /* pivot in list[p]          */
43  list[i]=list[p];
44  list[p]=temp;
45
46  return p;                      /* return pivot position     */
47}
48
49
50template<class T, class C>
51void quicksort(vector<T>& list,
52               int i,
53               int n,
54               const C& compare) {
55  int p;
56
57  if(i<n) {
58    p=partition(list,            /* p is the list pivot position */
59                i,
60                n,
61                compare);
62    quicksort(list,
63              i,
64              p-1,
65              compare);
66    quicksort(list,
67              p+1,
68              n,
69              compare);
70  }
71}
72
73template<class T, class C>
74void quicksort(vector<T>& list,
75               const C& compare) {
76  int n = list.size();
77
78  quicksort(list,
79            0,
80            n-1,
81            compare);
82}