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
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
|
// Programmieren 1, Praktikum 5, Aufgabe 2
// Sven Eisenhauer
// 16.12.2004
//
// file: main.cpp
//
// purpose: QuickSort algorithm
//
#include <iostream>
using std::cin;
using std::cout;
using std::endl;
#include <iomanip>
using std::setprecision;
using std::setw;
// contains function prototypes for functions srand and rand
#include <cstdlib>
#include <ctime>
// constant definitions
const int arraySize=100; // number of array elements
const int maxNum=1000; // max. Number in Array plus 1
const int arrayStart=0; // first array element
const int arrayEnd=arraySize-1; // last array element
// function prototypes
void quickSort(int [],int,int);
int partition(int [], int,int,int&);
void swapRight(int [], int &,int &, int &, int &, int &);
void swapLeft(int [], int&,int &, int&, int &, int &);
int main()
{
int array[arraySize];
// initialize random number generator
srand(time(0));
// generate array with random content
for (int i=0;i<arraySize;i++) {
array[i]=rand()%maxNum;
}
// show it unsorted
cout << "Unsorted:" << endl;
for (i=0;i<arraySize;i++) {
cout << setw(4) << array[i];
}
cout << endl;
// sort it
quickSort(array,arrayStart,arrayEnd);
// show it sorted
cout << "Sorted:" << endl;
for (i=0;i<arraySize;i++) {
cout << setw(4) << array[i];
}
cout << endl;
// habe fertisch
return 0;
}// end function main
void quickSort(int toSort[], int start, int end)
{
int pos;
// partition the array and get pos, where array is divided
partition(toSort,start,end,pos);
if (pos > start)
// now sort lower part
quickSort(toSort,start,pos-1);
if (pos < end)
// and higher part
quickSort(toSort,pos+1,end);
}// end function quicksort
int partition(int array[],int start, int end, int &pos)
{
int loop=0;
int foundL,foundR;
int newStart=start;
int newEnd=end;
int nextStart=start;
pos=start;
do {
foundR=0;
foundL=0;
// decide whether to search from left or right
// 0: right, 1: left
if (0==(loop%2)) {
swapRight(array,newEnd,newStart,nextStart,pos,foundR);
// set newStart for the next call of a swap fct.
newStart=nextStart;
/*cout << endl << " right "<< loop << " "<< endl;
for (int j=0;j<=end;j++)
cout << setw(4) << array[j];
cout << endl;*/
}
else {
swapLeft(array,newEnd,newStart,nextStart,pos,foundL);
// set newStart for the next call of a swap fct.
newStart=nextStart;
/*cout << endl << " left "<< loop << " "<< endl;
for (int j=0;j<=end;j++)
cout << setw(4) << array[j];
cout << endl;*/
}
loop++;
} while (((1==foundL)||(1==foundR)));
return 0;
}// end function partition
void swapRight(int arr[], int &end,int &newStart,int &nextStart, int &pos, int &found)
{
int i,temp;
// here we start to walk through array, from RIGHT!!!
i=end;
// newStart is the beginning of the area to check of the array
// when newStart==pos (which is the position of we element, which we order at the moment)
// this means: we are done here!
while((i>=newStart)&&(i!=pos)) {
// if we have found a smaller value, when searching from right
if (arr[i]<=arr[pos]) {
// swap the values
temp=arr[i];
arr[i]=arr[pos];
arr[pos]=temp;
// now set the next Start of search from left to one field right of
// the element, we currently searched and swapped
nextStart=newStart+1;
// in i is the actual position of the element which should be ordered
// we should not forget this and tell this the place, from where we were called
pos=i;
// YES!!! we found a smaller value by searching from right
found=1;
break;
}
i--;
}
}// end function swapRight
void swapLeft(int arr[], int &end,int &newStart,int &nextStart, int &pos, int &found)
{
int i,temp;
// here we start to walk through array, from LEFT!!!
i=newStart;
// newStart is the beginning of the area to check of the array
// when newStart==pos (which is the position of we element, which we order at the moment)
// this means: we are done here!
while((i<=end)&&(i!=pos)) {
// if we have found a bigger value, when searching from left
if (arr[i]>arr[pos]) {
// swap the values
temp=arr[i];
arr[i]=arr[pos];
arr[pos]=temp;
// now set the next Start of search from right to one field left of
// the element, we currently searched and swapped
nextStart=newStart-1;
// in i is the actual position of the element which should be ordered
// we should not forget this and tell this the place, from where we were called
pos=i;
// YES!!! we found a smaller value by searching from right
found=1;
break;
}
i++;
}
}// end function swapLeft
|
