Created
June 10, 2015 12:59
-
-
Save Ovilia/6b95db9ad25202e1bfd6 to your computer and use it in GitHub Desktop.
Sorting Algorithms
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <assert.h> | |
#include <stdlib.h> | |
#include <stdio.h> | |
#include <time.h> | |
//#define PRINT_RESULT | |
// insert sort: n * n | |
template <typename T> | |
void insertSort(int len, T* arr) | |
{ | |
// i is the index of first unsorted element | |
for (int i = 1; i < len; ++i) { | |
T key = arr[i]; | |
int j = i - 1; | |
// find larger element in the left and move one position right | |
while (j >=0 && arr[j] > key) { | |
arr[j + 1] = arr[j]; | |
--j; | |
} | |
arr[j + 1] = key; | |
} | |
} | |
// merge: n | |
template <typename T> | |
void merge(T* arr, int start, int split, int end) | |
{ | |
int lenL = split - start + 1; | |
int lenR = end - split; | |
// copy two parts to two arrays | |
T* arrL = new T[lenL]; | |
for (int i = 0; i < lenL; ++i) { | |
arrL[i] = arr[start + i]; | |
} | |
T* arrR = new T[lenR]; | |
for (int i = 0; i < lenR; ++i) { | |
arrR[i] = arr[split + 1 + i]; | |
} | |
// amt of unmerged elements in two parts | |
int left = 0; | |
int right = 0; | |
// index of next elements in arr | |
int next = start; | |
while (left < lenL && right < lenR) { | |
if (arrL[left] <= arrR[right]) { | |
arr[next] = arrL[left]; | |
++left; | |
} else { | |
arr[next] = arrR[right]; | |
++right; | |
} | |
++next; | |
} | |
// copy rest part | |
for (; left < lenL; ++left) { | |
arr[next] = arrL[left]; | |
++next; | |
} | |
for (; right < lenR; ++right) { | |
arr[next] = arrR[right]; | |
++next; | |
} | |
delete []arrL; | |
delete []arrR; | |
} | |
// merge sort: n * log(n) | |
template <typename T> | |
void mergeSort(T* arr, int start, int end) | |
{ | |
if (start < end) { | |
int split = (end + start) / 2; | |
mergeSort(arr, start, split); | |
mergeSort(arr, split + 1, end); | |
merge(arr, start, split, end); | |
} | |
} | |
// select sort(unstable): n * n | |
template <typename T> | |
void selectSort(int len, T* arr) | |
{ | |
int loops = len - 1; | |
for (int i = 0; i < loops; ++i) { | |
// index of the min element | |
int minId = i; | |
for (int j = i + 1; j < len; ++j) { | |
if (arr[j] < arr[minId]) { | |
minId = j; | |
} | |
} | |
// swap arr[i] and arr[minId], making this sort unstable | |
T tmp = arr[i]; | |
arr[i] = arr[minId]; | |
arr[minId] = tmp; | |
} | |
} | |
// bubble sort: n * n | |
template <typename T> | |
void bubbleSort(int len, T* arr) | |
{ | |
for (int i = len - 1; i >= 0; --i) { | |
for (int j = 0; j < i; ++j) { | |
if (arr[j] > arr[j + 1]) { | |
T tmp = arr[j]; | |
arr[j] = arr[j + 1]; | |
arr[j + 1] = tmp; | |
} | |
} | |
} | |
} | |
// partition(used in quick sort): n | |
// return split index | |
template <typename T> | |
int partition(T* arr, int start, int end) | |
{ | |
// element to compare | |
T cmp = arr[end]; | |
// split position of upper and lower part | |
int split = start - 1; | |
for (int i = start; i <= end; ++i) { | |
// swap those less than cmp | |
if (arr[i] <= cmp) { | |
++split; | |
T tmp = arr[split]; | |
arr[split] = arr[i]; | |
arr[i] = tmp; | |
} | |
} | |
return split; | |
} | |
// quick sort(unstable): n * n | |
template <typename T> | |
void quickSort(T* arr, int start, int end) | |
{ | |
if (start < end) { | |
int split = partition(arr, start, end); | |
quickSort(arr, start, split - 1); | |
quickSort(arr, split + 1, end); | |
} | |
} | |
void testSort() | |
{ | |
for (int i = 0; i < 20; ++i) { | |
// random length | |
int len = rand() % 16 + 1; | |
#ifdef PRINT_RESULT | |
printf("old[%d]: ", len); | |
#endif | |
// random data | |
int* arr = new int[len]; | |
for (int j = 0; j < len; ++j) { | |
arr[j] = rand(); | |
#ifdef PRINT_RESULT | |
printf("%d ", arr[j]); | |
#endif | |
} | |
#ifdef PRINT_RESULT | |
printf("\n"); | |
#endif | |
//insertSort(len, arr); | |
//mergeSort(arr, 0, len - 1); | |
//selectSort(len, arr); | |
//bubbleSort(len, arr); | |
quickSort(arr, 0, len - 1); | |
// check after sorting | |
int lastElement = arr[0]; | |
for (int j = 0; j < len; ++j) { | |
assert(arr[j] >= lastElement); | |
lastElement = arr[j]; | |
#ifdef PRINT_RESULT | |
printf("%d ", arr[j]); | |
#endif | |
} | |
#ifdef PRINT_RESULT | |
printf("\n\n"); | |
#endif | |
delete []arr; | |
} | |
} | |
/** | |
* run time: | |
* quick 270s | |
* bubble 140s | |
* merge 33000s | |
* insert 70s | |
* select 170s | |
*/ | |
void timeTestSmall() | |
{ | |
time_t start = time(NULL); | |
for (int i = 0; i < 1000000000; ++i) { | |
int arr[] = {1, 2, 3, 5, 4}; | |
insertSort(5, arr); | |
//mergeSort(arr, 0, 4); | |
//selectSort(5, arr); | |
//bubbleSort(5, arr); | |
//quickSort(arr, 0, 4); | |
} | |
time_t end = time(NULL); | |
printf("%d\n", end - start); | |
} | |
/** | |
* run time: | |
* quick 70s | |
* bubble 76000s | |
* merge 2400s | |
* insert 26000s | |
* select 40000s | |
*/ | |
void timeTestLarge() | |
{ | |
time_t start = time(NULL); | |
for (int j = 0; j < 1; ++j) { | |
const int len = 100000; | |
int arr[len]; | |
for (int i = 0; i < len; ++i) { | |
arr[i] = rand(); | |
} | |
insertSort(len, arr); | |
//mergeSort(arr, 0, len - 1); | |
//selectSort(len, arr); | |
//bubbleSort(len, arr); | |
//quickSort(arr, 0, len - 1); | |
} | |
time_t end = time(NULL); | |
printf("%d\n", end - start); | |
} | |
int main() | |
{ | |
//testSort(); | |
timeTestLarge(); | |
return 0; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment