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
|
#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;
}
|