=== Source Code ===
===== bubble sort =====
template<typename T> inline void bubbleSort(T * array, int size) { for (int i = 0; i < size; i++) { for (int j = 0; j < size - 1; j++) { if (array[j] > array[j + 1]) { T swap = array[j + 1]; array[j + 1] = array[jFile:BubbleSort.png]; array[j] = swap; } } } }
===== selection sort =====
template<typename T> inline void selectionSort(T * array, int size) { for (int i = 0; i < size; i++) { int min = i; for (int j = i; j < size; j++) { if (array[min] > array[j]) min = j; } T temp = array[i]; array[i] = array[minFile:SelectionSort1.png]; array[min] = temp; } }
===== insertion sort =====
template<typename T> inline void insertionSort(T * array, int size) { T curr; int j; for (int i = 0; i < size; i++) { curr = array[i[File:InsertionSort.png]]; for (j = i; j > 0 && array[j - 1] > curr; j--) { array[j] = array[j - 1File:InsertionSort2.png]; } array[j] = curr; } }
===== merge sort =====
template<typename T> inline void mergeSort(T * array, int size) { T * temp = new T[size]; mergeSort(array, temp, 0, size - 1); delete[] temp; } template<typename T> inline void mergeSort(T * array, T * temp, int start, int end) { if (start < end) { int mid = (start + end) / 2; mergeSort(array, temp, start, mid); mergeSort(array, temp, mid + 1, end); merge(array, temp, start, mid + 1, end); } } template<typename T> inline void merge(T * array, T * temp, int startA, int startB, int endB) { int aptr = startA; int bptr = startB; int idx = startA; while (aptr < startB && bptr < endB + 1) { if (array[aptr] < array[bptr]) { temp[idx] = array[aptr]; idx++; aptr++; } else { temp[idx++] = array[bptr]; bptr++; } } while (aptr<startB) { temp[idx] = array[aptr]; idx++; aptr++; } while (bptr < endB + 1) { temp[idx++] = array[bptr]; bptr++; } for (int i = startA; i <= endB; i++) { array[iFile:MergeSort.png] = temp[i]; } }
===== heap sort =====
template<typename T> inline void heapSort(T * array, int size) { for (int i = size / 2 - 1; i >= 0; i--) { heapify(array, size, i); } for (int i = size - 1; i >= 0; i--) { std::swap(array[0], array[i]); heapify(array, i, 0); } } template <typename T> void heapify(T * array, int size, int i) { int largest = i; int left = 2 * i + 1; int right = 2 * i + 2; if (left < size && array[left] > array[largest]) largest = left; if (right < size && array[right] > array[largest]) largest = right; if (largest != i) { stdFile::swap(array[iHeapSort.png], array[largest]); heapify(array, size, largest); } }
===== quick sort =====
template<typename T> inline void quickSort(T * array, int size) { quickSort(array, 0, size - 1); } template<typename T> inline void quickSort(T * array, int left, int right) { if (right - left <= 3) { insertionSort(array, left, right); } else { int mid = (left + right) / 2; std::swap(array[right], array[mid]); int pivotpt = right; int i = left; int j = right - 1; T pivot = array[pivotpt]; while (i<j) { while (i< right - 1 && array[i]<pivot) i++; while (j > 0 && array[j]>pivot) j--; if (i<j) stdFile::swap(array[i++QuickSort.png], array[j--]); } if (i == j && array[i] < array[pivotpt]) i++; std::swap(array[i], array[pivotpt]); quickSort(array, left, i - 1); quickSort(array, i + 1, right); } }
===== counting sort =====
template<typename T> inline void countingSort(T * array, int size, int RANGE) { T output[size]; int count[RANGE + 1]; std:File:memset(count, 0, sizeof(count)); for (int i = 0; array[i]; ++i) { ++count[(int)array[iCountingSort.png]]; } for (int i = 1; i <= RANGE; ++i) { count[i] += count[i-1]; } for (int i = 0; array[i]; ++i) { output[(int)count[(int)array[i]] - 1] = array[i]; --count[(int)array[i]]; } for (int i = 0; i < size; i++) { array[i] = output[i]; } }
===== radix sort =====
template<typename T> inline void radixSort(T * array, int size) { T maxNumber = array[0]; for (int i = 1; i < size; i++) { if (array[i] > maxNumber) maxNumber = array[i]; } T exp = 1; T * temp = new T[size]; while (maxNumber / exp > 0) { T decimalBucket[10] = { 0 }; for (int i = 0; i < size; i++) decimalBucket[(int)array[i] / (int)exp % 10]++; for (int i = 1; i < 10; i++) decimalBucket[i] += decimalBucket[i - 1File:RadixSort.png]; for (int i = size - 1; i >= 0; i--) temp[(int)--decimalBucket[(int)array[i] / (int)exp % 10]] = array[i]; for (int i = 0; i < size; i++) array[i] = temp[i]; exp *= 10; } }
===== bucket sort =====
template<typename T> inline void bucketSort(T * array, int size, int bucketSize) { std::vector<T> buckets[bucketSize]; T max = getMax(array, size); int divider = std[File::ceil(T(max + 1) / bucketSize); for (int i = 0; i < size; i++) { int j = floor(array[i] / divider); buckets[j].push_back(array[i]); } for (int i = 0; i < bucketSize; i++) { sort(buckets[i].begin(), buckets[i].end()); } int k = 0; for (int i = 0; i < bucketSize; i++) { for (int j = 0; j < buckets[i]BucketSort.size(); j++) { array[k++] = buckets[ipng][j]; } } }
===== shell sort =====
template <typename T> void shellSort(T * array, int size) { T temp; for (int gap = size / 2; gap > 0; gap /= 2) { for (int i = gap; i < size; i += 1) { temp = array[i]; int j; for (j = i; j >= gap && array[j - gap] > temp; j -= gap) { array[j] = array[j - gapFile:ShellSort.png]; } array[j] = temp; } } }
=== Results ===
Flat profile: Each sample counts as 0.01 seconds. % cumulative self self total time seconds seconds calls Ts/call Ts/call name 99.71 3.46 3.46 void radixSort<float>(float*, int) 0.29 3.47 0.01 void quickSort<float>(float*, int, int) 0.00 3.47 0.00 1091 0.00 0.00 void std::__move_median_first<__gnu_cxx::__normal_iterator<float*, std::vector<float, std::allocator<float> > > >(__gnu_cxx::__normal_iterator<float*, std::vector<float, std::allocator<float> > >, __gnu_cxx::__normal_iterator<float*, std::vector<float, std::allocator<float> > >, __gnu_cxx::__normal_iterator<float*, std::vector<float, std::allocator<float> > >) 0.00 3.47 0.00 112 0.00 0.00 void std::vector<float, std::allocator<float> >::_M_insert_aux<float const&>(__gnu_cxx::__normal_iterator<float*, std::vector<float, std::allocator<float> > >, float const&&&) 0.00 3.47 0.00 10 0.00 0.00 void std::__insertion_sort<__gnu_cxx::__normal_iterator<float*, std::vector<float, std::allocator<float> > > >(__gnu_cxx::__normal_iterator<float*, std::vector<float, std::allocator<float> > >, __gnu_cxx::__normal_iterator<float*, std::vector<float, std::allocator<float> > >) 0.00 3.47 0.00 10 0.00 0.00 void std::__introsort_loop<__gnu_cxx::__normal_iterator<float*, std::vector<float, std::allocator<float> > >, int>(__gnu_cxx::__normal_iterator<float*, std::vector<float, std::allocator<float> > >, __gnu_cxx::__normal_iterator<float*, std::vector<float, std::allocator<float> > >, int) 0.00 3.47 0.00 1 0.00 0.00 _GLOBAL__sub_I_main
==== Call Graph ====
==== Clustered Column Chart ====
