英文:
randomized quick sort base case not working (sometimes)
问题
在实现快速排序时，我认为当数组中只有两个或三个元素时，无需继续分割数组，因为如果你只是分割了基准元素，最终会得到一个有序数组。
问题在于，在添加了以下if语句之后，输出看起来循环：
if e-s == 2 or e-s == 1:
partition(arr,s,e)
return
在没有上述条件的情况下，代码正常工作。
英文:
While implementing quick sort I thought that when there's two or three element in the arr there's no need to continue dividing the arr since if you just partitioned the pivot you will end up with a sorted array.
The problem is after adding the following if statement there was output looking cyclic
if e-s == 2 or e-s == 1:
partition(arr,s,e)
return
without the if condition above the code works fine
import random
def quickSort(arr,s,e):
if s >= e: return
if e-s == 2 or e-s == 1:
partition(arr,s,e)
return
x = randPartition (arr,s,e)
quickSort(arr,s,x-1)
quickSort(arr,x+1,e)
def partition(arr,s,e):
pivot = arr展开收缩
x = s
for i in range (s+1,e+1):
if arr[i] < pivot :
x+=1
arr[x],arr[i]=arr[i],arr[x]
arr展开收缩,arr[x] = arr[x],arr展开收缩
return x
def randPartition(arr,s,e):
x = random.randint(s,e)
arr[x],arr展开收缩 = arr展开收缩,arr[x]
return partition(arr,s,e)
arr = [1,5,0,3,-15,12,96,99,1500,-1500,66,120]
quickSort(arr,0,len(arr)-1)
print(arr)
output
[-1500, -15, 0, 1, 3, 12, 5, 66, 96, 99, 120, 1500]
[-1500, -15, 0, 1, 5, 3, 12, 66, 96, 120, 99, 1500]
[-1500, -15, 0, 1, 3, 5, 12, 66, 96, 99, 120, 1500]
[-1500, -15, 0, 1, 3, 5, 12, 66, 99, 96, 120, 1500]
[-1500, -15, 0, 1, 3, 5, 12, 66, 96, 99, 1500, 120]
[-1500, -15, 0, 1, 3, 5, 12, 66, 96, 120, 99, 1500]
[-1500, -15, 0, 1, 3, 5, 12, 66, 96, 99, 120, 1500]
[-1500, -15, 0, 1, 3, 5, 12, 66, 96, 99, 120, 1500]
[-1500, -15, 0, 1, 3, 5, 12, 66, 96, 99, 1500, 120]
[-1500, -15, 0, 3, 1, 5, 12, 66, 96, 99, 120, 1500]
[-1500, -15, 0, 1, 3, 5, 12, 66, 96, 99, 120, 1500]
[-1500, -15, 0, 1, 3, 5, 12, 66, 96, 99, 1500, 120]
[-1500, -15, 0, 1, 3, 5, 12, 66, 96, 99, 120, 1500]
[-1500, -15, 0, 1, 3, 5, 12, 66, 96, 99, 1500, 120]
[-1500, -15, 0, 1, 3, 5, 12, 66, 96, 99, 120, 1500]
答案1
得分: 1
### 你就快完成了！只需处理2元素和3元素的情况
你目前通过调用`partition`函数同时处理两种情况。实际上，对于两个元素的情况，你可以简单地使用一个`if`语句，如果它们的顺序不对，就交换它们。
~~~
import random
def quickSort(arr, s, e):
if s >= e:
return
if e - s == 1:
if arr展开收缩 > arr[e]:
arr展开收缩, arr[e] = arr[e], arr展开收缩
return
if e - s == 2:
partition(arr, s, e)
return
x = randPartition(arr, s, e)
quickSort(arr, s, x-1)
quickSort(arr, x+1, e)
def partition(arr, s, e):
pivot = arr展开收缩
x = s
for i in range(s+1, e+1):
if arr[i] < pivot:
x += 1
arr[x], arr[i] = arr[i], arr[x]
arr展开收缩, arr[x] = arr[x], arr展开收缩
return x
def randPartition(arr, s, e):
x = random.randint(s, e)
arr[x], arr展开收缩 = arr展开收缩, arr[x]
return partition(arr, s, e)
arr = [1, 5, 0, 3, -15, 12, 96, 99, 1500, -1500, 66, 120]
quickSort(arr, 0, len(arr)-1)
print(arr)
~~~
### 结果
~~~
[-1500, -15, 0, 1, 3, 5, 12, 66, 96, 99, 120, 1500]
~~~
英文:
You are almost there! Just need to separate the 2-element and 3-element cases
You currently are handling both by a call to partition. In fact, for the two-element case you can just do a simple if that swaps them if they are the wrong way round.
import random
def quickSort(arr,s,e):
if s >= e:
return
if e-s == 1:
if arr展开收缩 > arr[e]:
arr展开收缩, arr[e] = arr[e], arr展开收缩
return
if e-s == 2:
partition(arr,s,e)
return
x = randPartition (arr,s,e)
quickSort(arr,s,x-1)
quickSort(arr,x+1,e)
def partition(arr,s,e):
pivot = arr展开收缩
x = s
for i in range (s+1,e+1):
if arr[i] < pivot:
x+=1
arr[x],arr[i]=arr[i],arr[x]
arr展开收缩,arr[x] = arr[x],arr展开收缩
return x
def randPartition(arr,s,e):
x = random.randint(s,e)
arr[x],arr展开收缩 = arr展开收缩,arr[x]
return partition(arr,s,e)
arr = [1,5,0,3,-15,12,96,99,1500,-1500,66,120]
quickSort(arr,0,len(arr)-1)
print(arr)
Result
[-1500, -15, 0, 1, 3, 5, 12, 66, 96, 99, 120, 1500]
答案2
得分: 0
问题在于对 partition 的单次调用不能保证结果已排序。例如，如果子数组（在 s 和 e 之间）是 [1, 3, 2]，那么 partition 不会做任何改变（因为 1 是枢纽元，3 和 2 都比它大）。只有当枢纽元碰巧移动到中间时，结果才会被排序。如果你想用只调用 partition 处理长度为3的数组，那么在第一次调用的枢纽元没有在中间时，就再调用一次，并且在不包括该枢纽元的子数组上调用它：
if e - s < 3:
x = partition(arr, s, e)
if e - s == 2 and x != s + 1:
partition(arr, s + (x == s), e - (x == e))
return
英文:
The problem is that the single call to partition does not guarantee that the result is sorted. For instance, if the subarray (between s and e) consists of [1, 3, 2], then partition will not make any changes (because 1 is the pivot and indeed 3 and 2 are both greater than it). Only if the pivot happens to get moved to the middle will the result be sorted.
If you want to deal with a length-3 array with only calls to partition, then call partition a second time if the pivot of the first call didn't arrive in the middle, and call it on the subarray that excludes that pivot:
if e - s < 3:
x = partition(arr, s, e)
if e - s == 2 and x != s + 1:
partition(arr, s + (x == s), e - (x == e))
return
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论