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
|
#include <iostream>
using namespace std;
template < class ItemType > void Swap(ItemType r, ItemType l)
{
ItemType tmp;
tmp = r;
r = l;
l = tmp;
}
template < class ItemType > void SelectionSort(ItemType values[], int numValues)
// Post: The elements in the array values are sorted by key.
{
int SelComp = 0;
int endIndex = numValues - 1;
for (int current = 0; current < endIndex; current++) {
Swap(values[current], values[MinIndex(values, current, endIndex)]);
SelComp++;
}
cout << "These integers were sorted using Selection Sort and the number of comparisons made were " << SelComp << "." << endl;
}
template < class ItemType > int MinIndex(ItemType values[], int start, int end)
// Post: Function value = index of the smallest value in
// values [start] . . values [end].
{
int indexOfMin = start;
for (int index = start + 1; index <= end; index++)
if (values[index] < values[indexOfMin])
indexOfMin = index;
return indexOfMin;
}
template < class ItemType > void InsertItem(ItemType values[], int startIndex, int endIndex)
// Post: values[0]..values[endIndex] are now sorted.
{
bool finished = false;
int current = endIndex;
bool moreToSearch = (current != startIndex);
while (moreToSearch && !finished) {
if (values[current] < values[current - 1]) {
Swap(values[current], values[current - 1]);
current--;
moreToSearch = (current != startIndex);
} else
finished = true;
}
}
template < class ItemType > void InsertionSort(ItemType values[], int numValues)
{
int InsertComp = 0;
for (int count = 0; count < numValues; count++) {
InsertItem(values, 0, count);
InsertComp++;
}
cout << "These integers were sorted using Insertion Sort and the number of comparisons made were " << InsertComp << "." << endl;
}
template < class ItemType > void BubbleUp(ItemType values[], int start, int end)
// Post: Neighboring elements that were out of order have been
// swapped between values [start] and values [end],
// beginning at values [end].
{
for (int index = end; index > start; index--)
if (values[index] < values[index - 1])
Swap(values[index], values[index - 1]);
}
template < class ItemType > void BubbleSort(ItemType values[], int numValues)
// Post: Sorts array values[0 . . numValues-1 ] into ascending
// order by key
{
int BubbleComp = 0;
int current = 0;
while (current < numValues - 1) {
BubbleUp(values, current, numValues - 1);
current++;
BubbleComp++;
}
cout << "These integers were sorted using Bubble Sort and the number of comparisons made were " << BubbleComp << "." << endl;
}
int main()
{
int int_array[10] = { 43, 7, 10, 23, 18, 4, 19, 5, 66, 14 };
float float_array[10] = { 43.2, 7.1, 10.5, 23.9, 18.7, 4.2, 19.3, 5.7, 66.8, 14.4 };
int numValues = 10;
cout << "Here is unsorted integer array: ";
for (int i = 0; i < 10; i++)
cout << int_array[i] << ' ';
cout << endl;
cout << "Here is unsorted double array: ";
for (int i = 0; i < 10; i++)
cout << float_array[i] << ' ';
cout << endl;
BubbleSort(int_array, numValues);
BubbleSort(float_array, numValues);
InsertionSort(int_array, numValues);
InsertionSort(float_array, numValues);
SelectionSort(int_array, numValues);
SelectionSort(float_array, numValues);
system("pause");
return 0;
}
| |
