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}