-
Notifications
You must be signed in to change notification settings - Fork 31
Expand file tree
/
Copy pathSorting.cpp
More file actions
executable file
·122 lines (111 loc) · 2.38 KB
/
Sorting.cpp
File metadata and controls
executable file
·122 lines (111 loc) · 2.38 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
#include<stdio.h>
#include<math.h>
#include<stdlib.h>
#define NELEM 15
void insertion_sort(int s[], int n)
{
for(int i=0; i<n; i++) {
int j=i;
while((j>0) && (s[j] < s[j-1])) {
int tmp = s[j-1];
s[j-1] = s[j];
s[j] = tmp;
j = j-1;
}
}
}
void selectionSort(int data[], int count)
{
int min, temp;
for(int i = 0; i < count - 1; i++) {
min = i;
for(int j = i+1; j < count; j++)
if(data[j] < data[min])
min = j;
temp = data[i];
data[i] = data[min];
data[min] = temp;
}
}
void q_sort(int numbers[], int left, int right)
{
int pivot, l_hold, r_hold;
l_hold = left;
r_hold = right;
pivot = numbers[left];
while (left < right) {
while ((numbers[right] >= pivot) && (left < right))
right--;
if(left != right) {
numbers[left] = numbers[right];
left++;
}
while((numbers[left] <= pivot) && (left < right))
left++;
if(left != right) {
numbers[right] = numbers[left];
right--;
}
}
numbers[left] = pivot;
pivot = left;
left = l_hold;
right = r_hold;
if(left < pivot)
q_sort(numbers, left, pivot-1);
if(right > pivot)
q_sort(numbers, pivot+1, right);
}
void quick_sort(int numbers[], int array_size)
{
q_sort(numbers, 0, array_size - 1);
}
bool merge (int list1[], int size1, int list2[], int size2, int list3[])
{
int i1, i2, i3;
if (size1+size2 > NELEM) {
return false;
}
i1 = 0; i2 = 0; i3 = 0;
while (i1 < size1 && i2 < size2) {
if (list1[i1] < list2[i2]) {
list3[i3++] = list1[i1++];
} else {
list3[i3++] = list2[i2++];
}
}
while (i1 < size1) {
list3[i3++] = list1[i1++];
}
while (i2 < size2) {
list3[i3++] = list2[i2++];
}
}
void mergeSort (int array[], int size)
{
int temp[NELEM], mid, i;
if (size < 2) {
return;
} else {
mid = size / 2;
mergeSort(array, mid);
mergeSort(array + mid, size - mid);
merge (array, mid, array + mid, size - mid, temp);
for (i = 0; i < size; i++) {
array[i] = temp[i];
}
}
}
int main()
{
int s[NELEM+2] = {2,4,5,10,19,28,1,2,3,4,5,31,32,34,100};
//insertion_sort(s,NELEM);
//selectionSort(s,NELEM);
//quickSort(s,NELEM-1);
mergeSort(s, NELEM);
for(int i=0; i<NELEM; i++)
{printf("%d ",s[i]);
}
printf("\n");
return 0;
}