79194

C++ QuickSort Pivot Optimization

Question:

Currently, I have a barebones implementation of the quicksort algorithm to sort some randomly generated numbers. The sort is efficient, more so than merge sort. However, for specific number sets (e.g. reversed numbers that need to be sorted the other way around), I need to optimized the pivot.

int* partition (int* first, int* last); void quickSort(int* first, int* last) { if (last - first <= 1) return; int* pivot = partition(first, last); quickSort(first, pivot); quickSort(pivot + 1, last); } int* partition (int* first, int* last) { int pivot = *(last - 1); int* i = first; int* j = last - 1; for (;;) { while (*i < pivot && i < last) i++; while (*j >= pivot && j > first) j--; if (i >= j) break; swap (*i, *j); } swap (*(last - 1), *i); return i; }

So for this code, I either want to use a random number as the pivot for the partitioning step, or use the median of the first, middle, and last elements as the pivot.

How would I do this?

I'm new to sorting algorithms, and my understanding of them is not complete just yet.

Answer1:

Just change these lines:

int pivot = *(last - 1); … swap ((last - 1), i);

to something like:

int* pos = (first + rand(last - first)); int pivot = *pos; … swap (pos, i);

or

int* pos = mean_of_three((last - 1), (first), ((first + last) / 2)); int pivot = *pos; … swap (pos, i);

where mean_of_three take 3 pointers and returns a pointer to the mean.

Answer2:

As you have already mentioned, selecting first or last element of the array as pivot is not the best practice and cause the algorithm to fall into O(n^2). the best choice of pivot selection algorithm depends on the data that your program is likely to encounter. If there is a chance that the data will be sorted or nearly sorted, then random pivot is a very good choice(and very easy to implement) to avoid the O(n^2) behavior. On the other hand, the expense of selecting the middle element rather than the first is minimal and provides quite effective protection against sorted data.

Then again, if you are assured that your data will not be sorted or nearly sorted, then the median-of-three partitioning strategy seems to be the best.

int PickPivotUsingMedian(int a[], int first, int last) { int mid = (first+ right)/2; if (a[mid ] < a[first]) swap(&a[first],&a[mid ]); if (a[last] < a[first]) swap(&a[first],&a[last]); if (a[last]< a[mid ]) swap(&a[mid ],&a[last]); swap(&a[mid], &a[last - 1]);//since the largest is already in the right. return a[last - 1]; }

Answer3:

Choose a random index within the bounds of your array and use that element as the pivot.

Recommend

  • Is it possible to quicksort objects based on their keys in an array, using JavaScript?
  • Bad thread access/seg fault QuickSort
  • SIGSEV in custom QuickSort implementation
  • How to write a simple list-based quicksort in Idris?
  • Loading a TGA File and Using it with OpenGL
  • C++ exception safety paranoia: how much is too much?
  • How do I create shared library using ld?
  • Selection Sort, For Java
  • How to populate html table with info from list in django
  • Prevent page break in text block with iText, XMLWorker
  • Problem with Django using Apache2 (mod_wsgi), Occassionally is “unable to import from module” for no
  • Shouldn't else be indented in the below code
  • WPF - CanExecute dosn't fire when raising Commands from a UserControl
  • Scrapy recursive link crawler
  • NetLogo BehaviorSpace - Measure runs using reporters
  • How to handle AllServersUnavailable Exception
  • Rearranging Cells in UITableView Bug & Saving Changes
  • Circular dependency while pushing http interceptor
  • Linker errors when using intrinsic function via function pointer
  • Acquiring multiple attributes from .xml file in c#
  • FormattedException instead of throw new Exception(string.Format(…)) in .NET
  • How to CLICK on IE download dialog box i.e.(Open, Save, Save As…)
  • embed rChart in Markdown
  • How to get Windows thread pool to call class member function?
  • IndexOutOfRangeException on multidimensional array despite using GetLength check
  • How can I remove ASP.NET Designer.cs files?
  • EntityFramework adding new object to nested object collection
  • Checking variable from a different class in C#
  • Django query for large number of relationships
  • costura.fody for a dll that references another dll
  • Why is Django giving me: 'first_name' is an invalid keyword argument for this function?
  • Observable and ngFor in Angular 2
  • How to Embed XSL into XML
  • How can I use `wmic` in a Windows PE script?
  • failed to connect to specific WiFi in android programmatically
  • UserPrincipal.Current returns apppool on IIS
  • Conditional In-Line CSS for IE and Others?
  • java string with new operator and a literal
  • How to push additional view controllers onto NavigationController but keep the TabBar?
  • How can I use threading to 'tick' a timer to be accessed by other threads?