|
|
| Line 24: |
Line 24: |
| | === Source Code === | | === Source Code === |
| | ===== bubble sort ===== | | ===== bubble sort ===== |
| − | template<typename T>
| + | [[File:BubbleSort.png]] |
| − | 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[j];
| |
| − | array[j] = swap;
| |
| − | }
| |
| − | }
| |
| − | }
| |
| − | }
| |
| − | | |
| | | | |
| | ===== selection sort ===== | | ===== selection sort ===== |
| − | template<typename T>
| + | [[File:SelectionSort1.png]] |
| − | 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[min];
| |
| − | array[min] = temp;
| |
| − | }
| |
| − | }
| |
| | | | |
| | ===== insertion sort ===== | | ===== insertion sort ===== |
| − | template<typename T>
| + | [[File:InsertionSort.png]] |
| − | inline void insertionSort(T * array, int size) {
| + | |
| − | T curr;
| + | [[File:InsertionSort2.png]] |
| − | int j;
| |
| − | for (int i = 0; i < size; i++) {
| |
| − | curr = array[i];
| |
| − | for (j = i; j > 0 && array[j - 1] > curr; j--) {
| |
| − | array[j] = array[j - 1];
| |
| − | }
| |
| − | array[j] = curr;
| |
| − | }
| |
| − | }
| |
| | | | |
| | ===== merge sort ===== | | ===== merge sort ===== |
| − | template<typename T>
| + | [[File:MergeSort.png]] |
| − | 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[i] = temp[i];
| |
| − | }
| |
| − | }
| |
| | | | |
| | ===== heap sort ===== | | ===== heap sort ===== |
| − | template<typename T>
| + | [[File:HeapSort.png]] |
| − | 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) {
| |
| − | std::swap(array[i], array[largest]);
| |
| − | heapify(array, size, largest);
| |
| − | }
| |
| − | }
| |
| | | | |
| | ===== quick sort ===== | | ===== quick sort ===== |
| − | template<typename T>
| + | [[File:QuickSort.png]] |
| − | 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)
| |
| − | std::swap(array[i++], 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 ===== | | ===== counting sort ===== |
| − | template<typename T>
| + | [[File:CountingSort.png]] |
| − | inline void countingSort(T * array, int size, int RANGE) {
| |
| − | T output[size];
| |
| − | int count[RANGE + 1];
| |
| − | std::memset(count, 0, sizeof(count));
| |
| − |
| |
| − | for (int i = 0; array[i]; ++i) {
| |
| − | ++count[(int)array[i]];
| |
| − | }
| |
| − |
| |
| − | 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 ===== | | ===== radix sort ===== |
| − | template<typename T>
| + | [[File:RadixSort.png]] |
| − | 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 - 1];
| |
| − |
| |
| − | 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 ===== | | ===== bucket sort ===== |
| − | template<typename T>
| + | [[File:BucketSort.png]] |
| − | inline void bucketSort(T * array, int size, int bucketSize) {
| |
| − | std::vector<T> buckets[bucketSize];
| |
| − | T max = getMax(array, size);
| |
| − | int divider = std::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].size(); j++) {
| |
| − | array[k++] = buckets[i][j];
| |
| − | }
| |
| − | }
| |
| − | }
| |
| | | | |
| | ===== shell sort ===== | | ===== shell sort ===== |
| − | template <typename T>
| + | [[File:ShellSort.png]] |
| − | 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 - gap];
| |
| − | }
| |
| − | array[j] = temp;
| |
| − | }
| |
| − | }
| |
| − | }
| |
| | | | |
| | === Results === | | === 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 ==== | | ==== Call Graph ==== |
| | + | |
| | + | |
| | ==== Clustered Column Chart ==== | | ==== Clustered Column Chart ==== |
| | | | |
