Quick sort:

- O(nlogn) best and average.
- Worst case is O(n^2)
- divide and conquer mother fucker
- probably not stable (same keys may change order)
- pick a pivot, p, in the array (usually in the middle)
- partition into two arrays, one with all values <= p, the other with all values >= p
- the partition step can be done in place
- call quicksort on the two arrays
- if the array size is zero, you're done

templatevoid qs2 (vector &; arr, int left, int right) { if (left >= right) return; int i = left, j = right; int pivot = arr[(left + right) / 2]; while (i <= j) { while (arr[i] < pivot) i++; while (arr[j] > pivot) j--; if (i <= j) { swap(arr[i], arr[j]); i++; j--; } }; qs2(arr, left, i - 1); qs2(arr, i + 1, right); }

- worst case is O(nlogn)
- better for using slower data access things like files, tape drives
- don't have to store everything in memory

templatevoid mergeSort (vector & v) { if (v.size() < 2) return; // first divide in two, until only size 1 left int n = v.size(); int middle = n / 2; vector left; left.insert(left.begin(), v.begin(), v.begin() + middle); vector right; right.insert(right.begin(), v.begin() + middle, v.end()); mergeSort(left); mergeSort(right); v.clear(); // then reconstitute such that the new result is in order while (left.size() > 0 || right.size() > 0) { if (left.size() > 0 && right.size() > 0) { if (left[0] <= right[0]) { v.push_back(left.front()); left.erase(left.begin()); } else { v.push_back(right.front()); right.erase(right.begin()); } } else if (left.size() > 0) { v.insert(v.end(), left.begin(), left.end()); left.clear(); } else if (right.size() > 0) { v.insert(v.end(), right.begin(), right.end()); right.clear(); } } }

## No comments:

Post a Comment