Repository navigation
Expand file tree
/
Copy pathsorting.h
More file actions
215 lines (195 loc) · 6.3 KB
/
Copy pathsorting.h
File metadata and controls
215 lines (195 loc) · 6.3 KB
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
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
#ifndef SORTING_JL
#define SORTING_JL
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
using namespace std;
// Every function sorts the array in place, from the smallest to the greatest value.
/********************/
/* HELPERS */
/********************/
// Swap the Values of Two Positions.
void swapValues(int *array, int a, int b){
int temp = array[a];
array[a] = array[b];
array[b] = temp;
}
// Check if an Array is Sorted. Returns 1 if it's sorted from the smallest to the greatest or 0 if it's not.
int isSorted(const int *array, int size){
for(int i = 1; i < size; i++){
if(array[i-1] > array[i]){
return 0;
}
}
return 1;
}
// Print all Elements of an Array. Displays elements in the following format: [1, 2, 3, 4, 5]
void printValues(const int *array, int size){
printf("[");
for(int i = 0; i < size; i++){
printf("%d", array[i]);
if(i < size-1){
printf(", ");
}
}
printf("]\n");
}
/********************/
/* SIMPLE SORTING */
/********************/
// Bubble Sort: compare neighbours and swap them if they are in the wrong order, until a pass makes no swaps.
// O(n^2), but O(n) if the array is already sorted.
void bubbleSort(int *array, int size){
for(int pass = 0; pass < size-1; pass++){
int swapped = 0;
// After each pass the greatest value of the unsorted part is at its end, so we stop one position earlier.
for(int i = 0; i < size-1-pass; i++){
if(array[i] > array[i+1]){
swapValues(array, i, i+1);
swapped = 1;
}
}
if(!swapped){
break;
}
}
}
// Selection Sort: find the smallest value of the unsorted part and put it at its beginning. Always O(n^2).
void selectionSort(int *array, int size){
for(int i = 0; i < size-1; i++){
int minimum = i;
for(int j = i+1; j < size; j++){
if(array[j] < array[minimum]){
minimum = j;
}
}
if(minimum != i){
swapValues(array, i, minimum);
}
}
}
// Insertion Sort: take each value and move it to the left until it's in its place, like sorting cards in your hand.
// O(n^2), but O(n) if the array is already (or almost) sorted.
void insertionSort(int *array, int size){
for(int i = 1; i < size; i++){
int value = array[i];
int j = i-1;
while(j >= 0 && array[j] > value){
array[j+1] = array[j];
j--;
}
array[j+1] = value;
}
}
/********************/
/* EFFICIENT SORTING*/
/********************/
// Merge Two Sorted Halves: array[low..middle] and array[middle+1..high], using the temporary memory.
void mergeHalves(int *array, int *temp, int low, int middle, int high){
int left = low;
int right = middle+1;
int position = low;
while(left <= middle && right <= high){
// We use <= so equal values keep their order (the sort is stable).
if(array[left] <= array[right]){
temp[position++] = array[left++];
}
else{
temp[position++] = array[right++];
}
}
while(left <= middle){
temp[position++] = array[left++];
}
while(right <= high){
temp[position++] = array[right++];
}
for(int i = low; i <= high; i++){
array[i] = temp[i];
}
}
// Sort the Positions low..high with Merge Sort.
void mergeSortRange(int *array, int *temp, int low, int high){
if(low >= high){
return;
}
int middle = low + (high-low) / 2;
mergeSortRange(array, temp, low, middle);
mergeSortRange(array, temp, middle+1, high);
mergeHalves(array, temp, low, middle, high);
}
// Merge Sort: split the array in two halves, sort each half and merge them. Always O(n log n), uses O(n) extra memory.
// Returns 1 if successful or 0 if there's no memory for the temporary array.
int mergeSort(int *array, int size){
if(size < 2){
return 1;
}
int* temp = (int*)malloc(size * sizeof(int));
if(!temp){
return 0;
}
mergeSortRange(array, temp, 0, size-1);
free(temp);
return 1;
}
// Partition the Positions low..high around a Pivot (the middle value): smaller values to its left, greater ones to its right.
// Returns the final position of the pivot.
int partitionQuickSort(int *array, int low, int high){
// Using the middle value as pivot avoids the worst case O(n^2) when the array is already sorted.
swapValues(array, low + (high-low) / 2, high);
int pivot = array[high];
int smaller = low;
for(int i = low; i < high; i++){
if(array[i] < pivot){
swapValues(array, i, smaller);
smaller++;
}
}
swapValues(array, smaller, high);
return smaller;
}
// Sort the Positions low..high with Quick Sort.
void quickSortRange(int *array, int low, int high){
if(low >= high){
return;
}
int pivot = partitionQuickSort(array, low, high);
quickSortRange(array, low, pivot-1);
quickSortRange(array, pivot+1, high);
}
// Quick Sort: choose a pivot, put the smaller values to its left and the greater ones to its right, and sort both sides.
// O(n log n) on average, O(n^2) in the worst case. It doesn't need extra memory.
void quickSort(int *array, int size){
quickSortRange(array, 0, size-1);
}
// Move a Value Down in a Max Heap stored in array[0..size-1] (the same idea as siftDownHeap in heap.h).
void siftDownHeapSort(int *array, int size, int index){
while(1){
int left = 2*index + 1;
int right = 2*index + 2;
int largest = index;
if(left < size && array[left] > array[largest]){
largest = left;
}
if(right < size && array[right] > array[largest]){
largest = right;
}
if(largest == index){
break;
}
swapValues(array, index, largest);
index = largest;
}
}
// Heap Sort: turn the array into a max heap and move the maximum to the end, one value at a time.
// Always O(n log n) and it doesn't need extra memory.
void heapSort(int *array, int size){
for(int i = size/2 - 1; i >= 0; i--){
siftDownHeapSort(array, size, i);
}
for(int end = size-1; end > 0; end--){
swapValues(array, 0, end);
siftDownHeapSort(array, end, 0);
}
}
#endif //SORTING_JL