-
Notifications
You must be signed in to change notification settings - Fork 5
/
Sorter.h
119 lines (106 loc) · 3.99 KB
/
Sorter.h
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
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
////////////////////////////////////////////////////////////////////////////////////
// Copyright © Charalambos "Charis" Poullis, [email protected] //
// This work can only be used under an exclusive license of the author. //
////////////////////////////////////////////////////////////////////////////////////
#ifndef __SORTER_H__
#define __SORTER_H__
#include <stdio.h>
#include "Vector.h"
#include <vector>
template<class T, class R, int S>
class SorterComplexType {
public:
static bool quicksort(std::vector<T> &array, int bottom, int top, std::vector<R> *helper_array=0x00) {
// uses recursion-the process of calling itself
int middle;
if(bottom<top) {
middle = partitionArray(array, bottom, top,helper_array);
quicksort(array, bottom, middle,helper_array); // sort top partition
quicksort(array, middle+1, top,helper_array); // sort bottom partition
}
return true;
}
static bool quicksort(std::vector<Vector<T,S> > &array, int bottom, int top, int element, std::vector<R> *helper_array=0x00) {
// uses recursion-the process of calling itself
int middle;
if(bottom<top) {
middle = partitionArray(array, bottom, top,element,helper_array);
quicksort(array, bottom, middle,element,helper_array); // sort top partition
quicksort(array, middle+1, top,element,helper_array); // sort bottom partition
}
return true;
}
private:
SorterComplexType<T,R,S>() {;}
~SorterComplexType<T,R,S>() {;}
// partitions the array and returns the middle index (subscript)
static int partitionArray(std::vector<T> &array, int bottom, int top, std::vector<R> *helper_array=0x00) {
T x = array[bottom];
int i = bottom - 1;
int j = top + 1;
T temp;
R temp2;
do {
do {
j--;
} while (x <array[j]);
do {
i++;
} while (x >array[i]);
if (i < j) {
temp = array[i]; // switch elements at positions i and j
array[i] = array[j];
array[j] = temp;
if (helper_array) {
temp2 = (*helper_array)[i]; // switch elements at positions i and j
(*helper_array)[i] = (*helper_array)[j];
(*helper_array)[j] = temp2;
}
}
} while (i < j);
return j; // returns middle index
}
// partitions the array and returns the middle index (subscript)
static int partitionArray(std::vector<Vector<T,S> > &array, int bottom, int top, int element, std::vector<R> *helper_array=0x00) {
T x = array[bottom](element);
int i = bottom - 1;
int j = top + 1;
Vector<T,S> temp;
R temp2;
do {
do {
j--;
} while (x <array[j](element));
do {
i++;
} while (x >array[i](element));
if (i < j) {
temp = array[i]; // switch elements at positions i and j
array[i] = array[j];
array[j] = temp;
if (helper_array) {
temp2 = (*helper_array)[i]; // switch elements at positions i and j
(*helper_array)[i] = (*helper_array)[j];
(*helper_array)[j] = temp2;
}
}
} while (i < j);
return j; // returns middle index
}
};
//Custom types
typedef SorterComplexType<unsigned int,unsigned int,2> SorterComplexType2ui;
typedef SorterComplexType<unsigned int,unsigned int,3> SorterComplexType3ui;
typedef SorterComplexType<unsigned int,unsigned int,4> SorterComplexType4ui;
typedef SorterComplexType<int,int,2> SorterComplexType2i;
typedef SorterComplexType<int,int,3> SorterComplexType3i;
typedef SorterComplexType<int,int,4> SorterComplexType4i;
typedef SorterComplexType<float,float,2> SorterComplexType2f;
typedef SorterComplexType<float,float,3> SorterComplexType3f;
typedef SorterComplexType<float,float,4> SorterComplexType4f;
typedef SorterComplexType<float,Vector2f,2> SorterComplexType2vf;
typedef SorterComplexType<float,Vector3f,3> SorterComplexType3vf;
typedef SorterComplexType<double,double,2> SorterComplexType2d;
typedef SorterComplexType<double,double,3> SorterComplexType3d;
typedef SorterComplexType<double,double,4> SorterComplexType4d;
#endif