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
|
#include <cstdlib>
#include <array>
#include <ctime>
#include <time.h>
#include <iostream>
using namespace std;
void quickSort(int random[], int left, int right)
{
int i = left, j = right;
int tmp;
int pivot = random[(left + right) / 2];
while (i <= j)
{
while (random[i] < pivot)
i++;
while (random[j] > pivot)
j--;
if (i <= j)
{
tmp = random[i];
random[i] = random[j];
random[j] = tmp;
i++;
j--;
}
};
if (left < j)
{
quickSort(random, left, j);
}
if (i < right)
{
quickSort(random, i, right);
}
}
int main()
{
int i, j, temp;
array<int, 10> random = { 14, 27, 94, 2, 11, 1, 192, 88, 8, 21 };
clock_t startTime1 = clock();
//merge sort here
clock_t endTime1 = clock();
clock_t clockTicks1 = endTime1-startTime1;
double mergesort_time = clockTicks1 /(double) CLOCKS_PER_SEC;
cout << "merge sort time: " << mergesort_time << endl;
for(i = 0; i < 10; i++)
{
cout << random[i] << " ";
}
cout << endl;
random = { 14, 27, 94, 2, 11, 1, 192, 88, 8, 21 };
clock_t startTime2 = clock();
for (i = 0; i < 10; i++)
{
for (j = 0; j < 10 - i - 1; j++)
{
if (random[j] > random[j + 1])
{
int temp = random[j];
random[j] = random[j + 1];
random[j + 1] = temp;
}
}
}
clock_t endTime2 = clock();
clock_t clockTicks2 = endTime2;
double bubblesort_time = clockTicks2 /(double) CLOCKS_PER_SEC;
cout << "bubble sort time: " << bubblesort_time << endl;
for(i = 0; i < 10; i++)
{
cout << random[i] << " ";
}
cout << endl;
random = { 14, 27, 94, 2, 11, 1, 192, 88, 8, 21 };
clock_t startTime3 = clock();
quickSort();
clock_t endTime3 = clock();
clock_t clockTicks3 = endTime3-startTime3;
double quicksort_time = clockTicks3 /(double) CLOCKS_PER_SEC;
cout << "quick sort time: " << quicksort_time << endl;
for(i = 0; i < 10; i++)
{
cout << random[i] << " ";
}
cout << endl;
random = { 14, 27, 94, 2, 11, 1, 192, 88, 8, 21 };
clock_t startTime4 = clock();
for (int i = 1; i<10; i++)
{
int j;
int current = random[i];
for(j = i-1; j >= 0 && random[j]> current; j--)
{
random[j + 1] = random[j];
}
random[j + 1] = current;
}
clock_t endTime4 = clock();
clock_t clockTicks4 = endTime4-startTime4;
double insertsort_time = clockTicks4 /(double) CLOCKS_PER_SEC;
cout << "insert sort time: " << insertsort_time << endl;
for(i = 0; i < 10; i++)
{
cout << random[i] << " ";
}
cout << endl;
}
| |