I have implemented Mergesort and Quicksort in Python and have noticed that Quicksort runs two times as fast as Mergesort. Is this a property of the algorithm or is Mergesort coded inefficiently? Are there any other suggestions? (I am aware that the timing includes the creation of the random list.) Quicksort: ``` import time, random def quicksort_benchmark(n=2**24): def quicksort(array, low, high): if low = pivot: break while True: j -= 1 if array[j] = j: return j temp = array[i] array[i] = array[j] array[j] = temp start = time.time() # initialize array array = [random.randint(0, n) for i in range(0,n)] quicksort(array, 0, len(array)-1) end = time.time() elapsed = end - start return(elapsed) ``` Mergesort: ``` def mergesort_benchmark(n=2**24): def mergesort(m): if len(m) <= 1: return m left, right = [], [] for i in range(0, len(m)): if i < len(m)//2: left.append(m[i]) else: right.append(m[i]) left = mergesort(left) right = mergesort(right) return(merge(left,right)) def merge(left,right): result = [] i, j = 0, 0 while i < len(left) and j < len(right): if left[i] <= right[j]: result.append(left[i]) i += 1 else: result.append(right[j]) j += 1 for i in range(i, len(left)): result.append(left[i]) for i in range(j, len(right)): result.append(right[i]) return result start = time.time() m = [random.randint(0,n) for i in range(0,n)] m = mergesort(m) end = time.time() elapsed = end - start return(elapsed) ```

I have implemented a iterator based version of Quicksort, which allows the user to define and pass his own pivot-selection-strategy: ``` template It Partition(It begin,It end,It pivot) { std::swap(*begin, *pivot); pivot = begin; It i{ begin }, j = std::next(begin, 1); for(;j != end; j++) { if(*j void Quicksort(It begin, It end, Pivot&& GetPivot) { if (std::distance(begin, end) == 0) return; It pivot{ GetPivot(begin,end) }; It elementAtCorrectPosition = Partition(begin, end,pivot); Quicksort(begin, elementAtCorrectPosition, GetPivot); Quicksort(std::next(elementAtCorrectPosition, 1), end, GetPivot); } ``` The algorithm can be used in the following way: ``` std::vector v{ 3, 8, 2, 5, 1, 4, 7, 6 }; auto quickSort = v; auto stdSort = v; Quicksort(quickSort.begin(), quickSort.end(), [](auto a, auto b) { return a; }); std::sort(stdSort.begin(), stdSort.end()); Assert::IsTrue(quickSort == stdSort); ``` Where the lambda expression ``` [](auto a, auto b) { return a; } ``` is just to demonstrate how a pivot selection strategy can be passed to the algorithm. Any suggestions that lead to a more robust, concise and readable code are welcome. Special thanks to @ratchet freak, who discovered an emberassing bug: The initial implementation only worked for the special case, where the first element is selected as pivot. See above for the corrected version.

Code review my quicksort! It isn't supposed to be superfast or anything and doesn't basecase out to insertion sort or anything. It's optimized for clarity and only sorts arrays of pointers. ``` #define MISC_XCHG(a, b) ({ __typeof__(a) MISC_XCHG__A = (a); (a) = (b); (b) = MISC_XCHG__A; }) static void misc_qsort_internal(void const** A, void const** Z, bool (*cmp)(void const*, void const*)) { while ((Z - A) > 1) { /* quicksort is a bit tricky. the basic idea of just partitioning into = partitions and recursing on each isn't guaranteed to terminate, because everything can end up in the >= part. the key to termination is to make sure at least one element drops out. the element that drops out must be equal to the pivot, so that it can be >= everything in the = part. most simply, this element can be the pivot, which should be inserted between the = parts. so as we build up the regions we keep the pivot at the start of the array and later exchange it with the last element in the = part */ void const** S = A+1; for (void const** I = S; I = part */ MISC_XCHG(*I, *S); /* and shift the >= part over by one */ S++; } else { /* when *I >= pivot */ /* nothing to do, the >= part grows "automatically" */ } } /* now do the business of exchanging the pivot */ void const** R = (S - 1); *A = *R; *R = pivot; /* recursively sort (>=A, =S, =S, =A, <R) */ } } } /* cmp should return true iff [arg1] < [arg2] (strictly). */ static INLINE void misc_qsort(void const** A, uintptr_t L, bool (*cmp)(void const*, void const*)) { misc_qsort_internal(A, (A + L), cmp); } #define MISC_QSORT_VARIANT(s, t) \ static INLINE void misc_qsort_##s(t** A, uintptr_t L, bool (*cmp)(t const*, t const*)) \ { \ misc_qsort(((void const**)(

Just for learning purposes i wrote an implementation of quicksort algorithm. I made some modifications to the algorithm to make it faster, that are: - two pivots setted to the boundaries of the middle partition(), to avoid having two other variables counting the equal elements - the partitioning method checks first the presence of less(in left partition) or greater(in right partition) than pivot elements, if both are present, rather than moving the pivot twice, it just swaps them; if not behaves normally. I benchmarked it a bit and compared the performance to std::sort; my algorithm, with random elements is faster than the STD one when there are more than 10000000, otherwise, with less elements std::sort is faster by some milliseconds(see below for actual benchmark results) ``` #include template void quickSort(iterator begin, iterator end) { if (end - begin > 1) { auto lpivot = begin + (end - begin) / 2; auto rpivot = lpivot; auto pValue = *lpivot; auto left_it = lpivot - 1; auto right_it = rpivot + 1; auto lValue = *left_it; auto rValue = *right_it; bool isGreater = false; bool isLess = false; while (left_it != begin-1 || right_it != end) { if (lValue >= pValue) { if (lValue == pValue) { lpivot--; std::iter_swap(lpivot, left_it); } else isGreater = true; } if (rValue <= pValue) { if (rValue == pValue) { rpivot++; std::iter_swap(rpivot, right_it); } else isLess = true; } if (isGreater && isLess) { std::iter_swap(left_it, right_it); } else if (isGreater) {

I've added a sort function to my library of utility functions. I will need to extend its behaviour at a later time but for now it's just a replacement for the `qsort()` function. I've implemented Yaroslavskiy's Double Pivot QuickSort which is fast and easy to implement (and has been selected as the sort of choice for Java7). I've removed recursion via a fixed stack and randomized the choice of the pivot elements to avoid O(n^2) behaviour when the array is already sorted. I've also tested the difference of having a final insertion sort run on the entire array instead of many insertion sort runs on shorter arrays but I've seen no noticeable difference. As for the stack depth I've tested that the average depth increase logarithmically (as expected). For example for 100 000 elements the average is 22, for 1 000 000 (10x) is 55. The chosen size should be more than enough for any realistic array. The swap operation is dominant: any improvement will directly impact the overall speed. I tried copying one-byte-at-times and `memcpy()` but they were slower. The random number generator `utl_rnd()` is surely not the best PRNG around but is fast and should be good enough for the purpose. I'd be especially interested in any comment about speed. Currently this is just a little slower than gcc's `qsort()` (e.g. 1.6ms vs 1.2ms to sort an array of 10 million random integers). Code is below (alternatively as github gist: https://gist.github.com/rdentato/8cf8007525feacc8df519bc91e98f20d): ``` /* Quick and dirty PRNG (xorshift) */ static uint32_t utl_rnd() { static uint32_t rnd = 0; while (rnd == 0) rnd = (uint32_t)time(0); rnd ^= rnd > 17; rnd ^= rnd = 4) { \ tmp32 = *(uint32_t *)pa; \ *(uint32_t *)pa = *(uint32_t *)pb;\ *(uint32_t *)pb = tmp32;\ sz-=4; pa+=4; pb+=4;\ }\

Is this algorithm good or can I improve it? ``` static void QuickSort(int[] a) { QuickSort(a, 0, a.Length - 1); } static void QuickSort(int[] a, int start, int end) { if (start >= end) { return; } int num = a[start]; int i = start, j = end; while (i num) { j--; } a[i] = a[j]; while (i < j && a[i] < num) { i++; } a[j] = a[i]; } a[i] = num; QuickSort(a, start, i - 1); QuickSort(a, i + 1, end); } ```

Below is a Python implementation of the quicksort algorithm using parallelism. It takes about 1 second per every 10 items in the list, which is hilariously unacceptable. Why is it so slow? ``` from multiprocessing import * def quicksort(lyst, connection=None): if len(lyst) > 1: pivot = lyst.pop(len(lyst)-1) wall = 0 for i in range(len(lyst)): if lyst[i] <= pivot: lyst[wall], lyst[i] = lyst[i], lyst[wall] wall += 1 receiveLeft, sendLeft = Pipe() receiveRight, sendRight = Pipe() Process(target=quicksort, args=(lyst[:wall], sendLeft)).start() Process(target=quicksort, args=(lyst[wall:], sendRight)).start() lyst = receiveLeft.recv() + [pivot] + receiveRight.recv() if connection: connection.send(lyst) connection.close() return lyst if __name__ == '__main__': quicksort([8,4,6,9,1,3,10,2,7,5]) ``` EDIT Thanks for the responses. As it turns out, switching to Threads and limiting the number of them I was spawning sped things up. However, my linear version of the algorithm still performed better.

I decided for educational purpose to make a generic sort like the one in the standard library as an exercise for my self in learning more about how to do generic programming in C and so I would really appreciate it if you guys could tell me how I could have done a better job and what other various improvements I could add to make my code better. I have quite a bit of functions to go through so I'm going to explain what each function does as much as I need to. Main ``` int main() { /* Throughout this source code, if you see an unsigned int, more than likely I'm using an unsigned int because I'm comparing to a variable of type size_t */ unsigned int i; int a[] = {200, 1, 99, 23, 56, 207, 369, 136, 147, 21, 4, 75, 36, 12}; size_t numberOfElements = sizeof(a)/sizeof(a[0]); /* No point in performing quick sort if it does not have more than 1 elements and if the array is sorted. */ if(numberOfElements > 1 && !isSorted(a, numberOfElements, sizeof(int), cmp)) { quickSort_h(a, numberOfElements, sizeof(int), cmp); } for(i = 0; i < numberOfElements; i++) { printf("%d ", a[i]); } return 0; } ``` Quick Sort Helper ``` void quickSort_h(void *base, size_t nitems, size_t memSize, int (*cmp)(const void *, const void *)) { quickSort(base, 0, nitems - 1, memSize, cmp); insertionSort(base, nitems, memSize, cmp); } ``` Quick Sort ``` /* Here we are doing a tail recurse optimization and using our threshold value(20) to know when to move to Insertion Sort. */ void quickSort(void *base, int first, int last, size_t memSize, int (*cmp)(const void *, const void *)) { while(last - first > THRESHOLD) { int pivot; pivot = qSortPartition(base, first, last, memSize, cmp); /* Here we are checking which is easier to recurse by checking if the subarray on the left is shorter than the one on the right and vice versa. */

I'm trying to get my Quicksort implementation doing fewer comparisons. The first element is used as a pivot. Could you give me some directions if there are any places that should be optimized in a sense of making fewer comparisons? As I understand, it's due to a redundant recursion pass, since the partition subroutine and comparisons counting in it are implemented correctly. ``` #include using namespace std; using uint = unsigned int; uint PartitionSub(vector& inp, uint l, uint r, uint& numOfCmp); void QuickSort(vector& inp, uint l, uint r, uint& numOfCmp) { if (r - l & inp, uint l, uint r, uint& numOfCmp) { auto swap = [&inp](uint a, uint b) { uint buf = inp[a]; inp[a] = inp[b]; inp[b] = buf; }; //numOfCmp += r - l; // we can use this, but ++numOfCmp just before // comparison is more clear uint i = l + 1; uint j = l + 1; uint p = inp[l]; for (; j <= r; j++) { ++numOfCmp; if (inp[j] <= p) { if (i != j) swap(i, j); i++; } } uint newPivotIdx = i - 1; swap(l, newPivotIdx); return newPivotIdx; } ```

I have not used C++ for a while. Could you please tell me if my usage of the `` module is correct? I am not sure if I need to be creating a new instance of `uniform_int_distribution` on each recursive call. I am not sure that I should be seeding the generator on each recursive call. I suspect these two actions need to happen somewhere outside but I do not know. Other improvements are also welcome, of course. ``` #include #include using generator = std::mt19937; template void quicksort(iterator fst, iterator lst) { if (fst >= lst) {return;} generator g(42); auto i = fst, j = lst; auto rval = std::uniform_int_distribution<>(0, std::distance(i, j)); auto pivot = *(fst + rval(g)); while (i void qsort(iterator begin, iterator end) { if (begin == end) {return;} quicksort(begin, end - 1); } ```