-
Notifications
You must be signed in to change notification settings - Fork 10
/
sort-soln.c
205 lines (176 loc) · 4.59 KB
/
sort-soln.c
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
#include <stdio.h>
#include <cs50.h>
/**
* Sorts array in place using bubble sort - optimizes to end if there are
* no swaps
*/
void bubble_sort(int array[], int n)
{
// cycle through array
for(int k = 0; k < n - 1; k++)
{
// optimize; check if there are no swaps
int swaps = 0;
// swap adjacent elements if out of order
for(int i = 0; i < n - 1 - k; i++)
{
if (array[i] > array[i + 1])
{
int temp = array[i + 1];
array[i + 1] = array[i];
array[i] = temp;
swaps++;
}
}
if (!swaps)
break;
}
}
/**
* Sorts array in place using selection sort
*/
void selection_sort(int array[], int size)
{
// iterate over array
for(int i = 0; i < size - 1; i++)
{
// smallest element and its position in sorted array
int smallest = array[i];
int position = i;
// unsorted part of array
for(int k = i + 1; k < size; k++)
{
// find the next smallest element
if (array[k] < smallest)
{
smallest = array[k];
position = k;
}
}
// swap
int temp = array[i];
array[i] = smallest;
array[position] = temp;
}
}
/**
* Sorts array in place using insertion sort
*/
void insertion_sort(int array[], int size)
{
// iterate through unsorted part of array from l->r
for(int i = 1; i < size; i++)
{
// define the start of the sorted array
int j = i - 1;
// specify the next element to sort
int to_sort = array[i];
// iterate through sorted part of array from r->l
// figure out where in sorted portion to_sort should go
while(j >= 0 && to_sort < array[j])
{
// shift sorted elements rightward
array[j + 1] = array[j];
j--;
}
// insert element into sorted portion of array
array[j + 1] = to_sort;
}
}
/**
* The power of halving - Merge Sort
*/
void merge (int array[], int start_1, int end_1, int start_2, int end_2)
{
int length = end_2 - start_1 + 1;
int index = start_1;
int temp[length];
// While there are elements in both subarrays
while (start_1 <= end_1 && start_2 <= end_2)
{
// Compare numbers at the start of the subarrays
if (array[start_1] <= array[start_2])
{
// Append smaller to merged array
temp[index] = array[start_1];
index++;
start_1++;
}
else
{
// Append smaller to merged array
temp[index] = array[start_2];
index++;
start_2++;
}
}
// While elements remain in subarray 1 (but not subarray 2)
while (start_1 <= end_1)
{
// Append element to merged array
temp[index] = array[start_1];
start_1++;
index++;
}
// While elements remain in subarray 2 (but not subarray 1)
while (start_2 <= end_2)
{
// Append element to merged array
temp[index] = array[start_2];
start_2++;
index++;
}
// Copy newly sorted array over to original array
for (int i = end_2, j = 0; j < length; i--, j++)
{
array[i] = temp[i];
}
}
void merge_sort (int array[], int start, int end)
{
if (end > start)
{
int middle = (start + end) / 2;
// sort left half
merge_sort(array, start, middle);
// sort right half
merge_sort(array, middle + 1, end);
// merge the two halves
merge(array, start, middle, middle + 1, end);
}
}
/**
* Prints all the elements in an array on one line.
*/
void print_array(int array[], int n)
{
for(int i = 0; i < n; i++)
{
printf("%i ", array[i]);
}
printf("\n");
}
int main(void)
{
int size = 5;
// bubble sort
printf("Bubble sort\n");
int bubble_nums[] = {7, 3, 0, 5, 2};
bubble_sort(bubble_nums, size);
print_array(bubble_nums, size);
// selection sort
printf("Selection sort\n");
int selection_nums[] = {7, 3, 0, 5, 2};
selection_sort(selection_nums, size);
print_array(selection_nums, size);
// insertion sort
printf("Insertion sort\n");
int insertion_nums[] = {7, 3, 0, 5, 2};
insertion_sort(insertion_nums, size);
print_array(insertion_nums, size);
// merge sort
printf("Merge sort\n");
int merge_nums[] = {7, 3, 0, 5, 2};
merge_sort(merge_nums, 0, size - 1);
print_array(merge_nums, size);
}