Portal:Mathematics/Selected picture/20: Difference between revisions

Content deleted Content added

Inline

Revision as of 20:08, 5 December 2017

< Previous Next >

{{Selected picture | image = Sorting quicksort anim.gif | size = 280px | caption = animation of dots of varying heights being sorted by height using the quicksort algorithm | text = Quicksort (also known as the partition loll xd u dumb (:::

@@ Line 4: / Line 4: @@
 | size       = 280px
 | caption    = animation of dots of varying heights being sorted by height using the quicksort algorithm
+| text       = '''[[Quicksort]]''' (also known as the ''partition loll xd u dumb (:::
-| text       = '''[[Quicksort]]''' (also known as the ''partition-exchange sort'') is an efficient [[sorting algorithm]] that works for items of any type for which a [[total order]] (i.e., "≤") relation is defined. This animation shows how the algorithm partitions the input array (here a random [[permutation]] of the numbers 1 through 33) into two smaller arrays based on a selected ''pivot'' element (bar marked in red, here always [[Quicksort#Lomuto partition scheme|chosen to be the last element]] in the array under consideration), by swapping elements between the two sub-arrays so that those in the first (on the left) end up all smaller than the pivot element's value (horizontal blue line) and those in the second (on the right) all larger. The pivot element is then moved to a position between the two sub-arrays; at this point, the pivot element is in its final position and will never be moved again. The algorithm then proceeds to recursively apply the same procedure to each of the smaller arrays, partitioning and rearranging the elements until there are no sub-arrays longer than one element left to process. (As can be seen in the animation, the algorithm actually sorts all left-hand sub-arrays first, and then starts to process the right-hand sub-arrays.) First developed by [[Tony Hoare]] in 1959, quicksort is still a commonly used algorithm for sorting in computer applications. [[Best, worst and average case|On the average]], it requires {{math|[[Big O notation|O]](''n'' log ''n'')}} comparisons to sort {{mvar|n}} items, which [[Sorting algorithm#Comparison of algorithms|compares favorably]] to other popular sorting methods, including [[merge sort]] and [[heapsort]]. Unfortunately, on rare occasions (including cases where the input is already sorted or contains items that are all equal) quicksort requires a worst-case {{math|O(''n''<sup>2</sup>)}} comparisons, while the other two methods remain {{math|O(''n'' log ''n'')}} in their worst cases. Still, when implemented well, quicksort can be about two or three times faster than its main competitors. Unlike merge sort, the standard implementation of quicksort does not preserve the order of equal input items (it is not [[stable sort|stable]]), although stable versions of the algorithm do exist at the expense of requiring {{math|O(''n'')}} additional storage space. Other variations are based on different ways of choosing the pivot element (for example, choosing a random element instead of always using the last one), using more than one pivot, switching to an [[insertion sort]] when the sub-arrays have shrunk to a sufficiently small length, and using a three-way partitioning scheme (grouping items into those smaller, larger, and ''equal to'' the pivot—a modification that can turn the worst-case scenario of all-equal input values into the best case). Because of the algorithm's "divide and conquer" approach, parts of it can be done [[Parallel algorithm|in parallel]] (in particular, the processing of the left and right sub-arrays can be done simultaneously). However, other sorting algorithms (including merge sort) experience much greater speed increases when performed in parallel.
-| credit     = [[User:RolandH|RolandH]]
-| link       = Quicksort
-| page       = picture
-| framecolor = transparent
-}}<!-- note: please do not change the "page" or "framecolor" parameters -->