Skip to content

Instantly share code, notes, and snippets.

@Ovilia
Created June 10, 2015 12:59
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save Ovilia/6b95db9ad25202e1bfd6 to your computer and use it in GitHub Desktop.
Save Ovilia/6b95db9ad25202e1bfd6 to your computer and use it in GitHub Desktop.
Sorting Algorithms
#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