了解快速排序 [英] Understanding quicksort
问题描述
我很难理解quicksort，大多数演示和解释都忽略了实际发生的情况（
< h2> Quicksort
Quicksort 步骤为：
- 从列表中选择一个称为枢轴的元素。
- 对列表重新排序，以便所有值小于该枢轴的元素都位于该枢轴之前，而所有值大于枢轴的元素都紧随其后（相等的值可以任一种方式）。分割之后，枢轴处于其最终位置。这称为分区操作。
- 递归地对较小元素的子列表和较大元素的子列表进行排序。
递归的基本情况是大小为零或一的列表，不需要排序。
Lomuto分区方案
- 此方案选择枢轴，该枢轴通常是数组
中的最后一个元素。 - 算法维护索引以将数据透视表放入变量i中，并且每次找到小于或等于数据透视表的元素时，该
索引都会递增，并且该元素将为放在
枢纽之前。 - 由于此方案更紧凑，更易于理解，因此经常在入门资料中使用。
- 效率比Hoare的原始方案低。 / li>
分区算法（使用Lomuto分区方案）
算法分区（A，lo，hi）是
枢轴：= A [hi]
i：= lo //放置位置用
交换j：= lo到hi – 1如果A [j]≤枢轴，则
然后
用A [j]交换A [i]
i：= i + 1
交换A [i]与A [hi]
return i
快速排序算法（使用Lomuto分区方案）
算法quicksort（A， lo，hi）如果lo<然后
p：= partition（A，lo，hi）
quicksort（A，lo，p – 1）
quicksort（A，p + 1，hi）
Hoare分区方案
-
使用两个索引，它们从被数组
分割的数组的末端开始，然后彼此靠近，直到它们检测到
反转：一对元素，一个大于枢轴，小一个
，彼此的顺序错误。然后交换掉
个反转元素。 -
此算法有许多变体，例如，从 A [hi] 代替 A [lo]
分区算法（使用Hoare分区方案）
算法分区（ A，lo，hi）是
枢轴点：= A [lo]
i：= lo – 1
j：= hi + 1
永远循环
做
i：= i + 1
而A [i]<枢纽
做
j：= j – 1
而A [j]>如果i> = j，则枢纽
，然后
返回j
用A [j]交换A [j]
快速排序算法（使用Hoare分区方案）
algorithm quicksort（A，lo，hi）是
如果lo<然后
p：=分区（A，lo，hi）
quicksort（A，lo，p）
quicksort（A，p + 1，hi）
使用额外的内存
def quicksort（array）：
less = []
等于= []
更大= []
（如果len（array）> 1：
枢轴= array [0]
对于x在数组中：
如果x<枢纽：
less.append（x）
如果x ==枢纽：
equal.append（x）
如果x>枢纽：
更大。追加（x）
返回排序（较少）+等于+排序（更大）
其他：
返回数组
用法：
快速排序（[12， 4,5,6,7,3,1,15]）
没有额外的内存
def分区（数组，开始，结束）：
枢轴=开始
用于我在xrange（begin + 1，end + 1）中：如果array [i]< = array [begin]：
枢轴+ = 1
array [i]，array [pivot ] = array [pivot]，array [i]
array [pivot]，array [begin] = array [begin]，array [pivot]
返回枢轴
def quicksort （array，begin = 0，end = None）：
如果end为None：
end = len（array）-1
如果begin> = end：
return
ivot =分区（数组，开始，结束）
quicksort（数组，开始，枢轴-1）
quicksort（数组，pivot + 1，结束）
用法：
快速排序（[97，200，100，101，211，107]）
在您的示例中
调试Lomuto分区
参考：
- < a href = http://www.cs.bilkent.edu.tr/~atat/473/lecture05.pdf rel = noreferrer> http://www.cs.bilkent.edu.tr/~atat/ 473 / lecture05.pdf
- http://codefap.com/2012/08/the-quick-sort-algorithm/
- http://visualgo.net/sorting
- https://en.wikipedia.org/wiki/Quicksort
I'm having a hard time understanding quicksort, most of the demonstrations and explanations leave out what actually happens (http://me.dt.in.th/page/Quicksort/ for example).
Wikipedia says:
Pick an element, called a pivot, from the array. Partitioning: reorder the array so that all elements with values less than the pivot come before the pivot, while all elements with values greater than the pivot come after it (equal values can go either way). After this partitioning, the pivot is in its final position. This is called the partition operation. Recursively apply the above steps to the sub-array of elements with smaller values and separately to the sub-array of elements with greater values.
How would that work with an array of 9,1,7,8,8 for example with 7 as the pivot? The 9 needs to move to the right of the pivot, all quicksort implementations are in place operations it seems so we can't add it after the 8,8, so the only option is to swap the 9 with the 7.
Now the array is 7,1,9,8,8. The idea behind quicksort is that now we have to recursively sort the parts to the left and right of the pivot. The pivot is now at position 0 of the array, meaning there's no left part, so we can only sort the right part. This is of no use as 7>1 so the pivot ended up in the wrong place.
In this image 4 is the pivot, then why is 5 going almost all the way to the left? It's bigger than 4! After a lot of swapping it ends up being sorted but I don't understand how that happened.
Quicksort
The Quicksort steps are:
- Pick an element, called a pivot, from the list.
- Reorder the list so that all elements with values less than the pivot come before the pivot, while all elements with values greater than the pivot come after it (equal values can go either way). After this partitioning, the pivot is in its final position. This is called the partition operation.
- Recursively sort the sub-list of lesser elements and the sub-list of greater elements. The base case of the recursion are lists of size zero or one, which never need to be sorted.
Lomuto partition scheme
- This scheme chooses a pivot which is typically the last element in the array.
- The algorithm maintains the index to put the pivot in variable i and each time it finds an element less than or equal to pivot, this index is incremented and that element would be placed before the pivot.
- As this scheme is more compact and easy to understand, it is frequently used in introductory material.
- Is less efficient than Hoare's original scheme.
Partition algorithm (using Lomuto partition scheme)
algorithm partition(A, lo, hi) is
pivot := A[hi]
i := lo // place for swapping
for j := lo to hi – 1 do
if A[j] ≤ pivot then
swap A[i] with A[j]
i := i + 1
swap A[i] with A[hi]
return i
Quicksort algorithm (using Lomuto partition scheme)
algorithm quicksort(A, lo, hi) is
if lo < hi then
p := partition(A, lo, hi)
quicksort(A, lo, p – 1)
quicksort(A, p + 1, hi)
Hoare partition scheme
Uses two indices that start at the ends of the array being partitioned, then move toward each other, until they detect an inversion: a pair of elements, one greater than the pivot, one smaller, that are in the wrong order relative to each other. The inverted elements are then swapped.
There are many variants of this algorithm, for example, selecting pivot from A[hi] instead of A[lo]
partition algorithm (using Hoare partition scheme)
algorithm partition(A, lo, hi) is
pivot := A[lo]
i := lo – 1
j := hi + 1
loop forever
do
i := i + 1
while A[i] < pivot
do
j := j – 1
while A[j] > pivot
if i >= j then
return j
swap A[i] with A[j]
quicksort algorithm(using Hoare partition scheme)
algorithm quicksort(A, lo, hi) is
if lo < hi then
p := partition(A, lo, hi)
quicksort(A, lo, p)
quicksort(A, p + 1, hi)
Hoare partition scheme vs Lomuto partition scheme
The pivot selection
The execution speed of the algorithm depends largely on how this mechanism is implemented, poor implementation can assume that the algorithm is run at a slow speed.
The choice of pivot determines partitions the data list, therefore, this is the most critical part of the implementation of the Quicksort algorithm. It is important to try that selecting the pivot left and right partitions have an identical size as much as possible.
Best and worst case
Worst case
The most unbalanced partition occurs when the pivot divides the list into two sublists of sizes _0 and n − 1. This may occur if the pivot happens to be the smallest or largest element in the list, or in some implementations when all the elements are equal.
Best Case In the most balanced case, each time we perform a partition we divide the list into two nearly equal pieces. This means each recursive call processes a list of half the size.
Formal analysis
- Worst-case analysis = O(n²)
- Best-case analysis = O(n) factor
- Average-case analysis = O(n log n)
Examples source
Using additional memory
def quicksort(array):
less = []
equal = []
greater = []
if len(array) > 1:
pivot = array[0]
for x in array:
if x < pivot:
less.append(x)
if x == pivot:
equal.append(x)
if x > pivot:
greater.append(x)
return sort(less)+equal+sort(greater)
else:
return array
Usage:
quicksort([12,4,5,6,7,3,1,15])
Without additional memory
def partition(array, begin, end):
pivot = begin
for i in xrange(begin+1, end+1):
if array[i] <= array[begin]:
pivot += 1
array[i], array[pivot] = array[pivot], array[i]
array[pivot], array[begin] = array[begin], array[pivot]
return pivot
def quicksort(array, begin=0, end=None):
if end is None:
end = len(array) - 1
if begin >= end:
return
pivot = partition(array, begin, end)
quicksort(array, begin, pivot-1)
quicksort(array, pivot+1, end)
Usage:
quicksort([97, 200, 100, 101, 211, 107])
In your example
Debug Lomuto partition
References:- http://www.cs.bilkent.edu.tr/~atat/473/lecture05.pdf
- http://codefap.com/2012/08/the-quick-sort-algorithm/
- http://visualgo.net/sorting
- https://en.wikipedia.org/wiki/Quicksort
这篇关于了解快速排序的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
