英文:
Pivot selection for QuickSort , what is going , is something incorrect in my algo?
问题
以下是您要求的翻译内容：
能否有人请指导我关于快速排序的实现。我试图可视化我实现的快速排序有什么问题，当我选择将枢轴作为数组中的最后一个元素时。
以下是我的代码：
public void quickSort(int[] input, int left, int right) {
if(left < right) {
//int pivot = input[(left + right) / 2]; // 使用这个时正常工作
//int pivot = input[left]; // 使用这个时正常工作
int pivot = input[right];
int index = partition(input, left, right, pivot); // 第12行
quickSort(input, left, index - 1); // 第13行
quickSort(input, index, right); // 第14行
}
}
private int partition(int[] input, int left, int right, int pivot) {
while(left <= right) {
while(input[left] < pivot) {
left++;
}
while(input[right] > pivot) {
right--;
}
if(left <= right) {
int temp = input[left];
input[left] = input[right];
input[right] = temp;
left++;
right--;
}
}
return left;
}
当我选择枢轴为
int pivot = input[(left + right) / 2]; // 使用这个时正常工作
int pivot = input[left + (right - left) / 2]; // 使用这个时正常工作
int pivot = input[left]; // 使用这个时正常工作
当枢轴为 input[right] 时，会出现以下异常：
Exception in thread "main" java.lang.StackOverflowError
at com.maverick.solution.Solution.quickSort(Solution.java:12)
at com.maverick.solution.Solution.quickSort(Solution.java:13)
请指导我如何纠正这个问题或出了什么问题。
谢谢！
英文:
Can some one please guide me with my implementation of QuickSort. I am trying to visualize what is wrong with my implementation of quick sort , when I select the pivot as the last element in the array.
Below is my code :
public void quickSort(int[] input, int left, int right) {
if(left < right) {
//int pivot = input[(left + right) / 2]; // works fine with this
//int pivot = input[left]; // works fine with this
int pivot = input[right];
int index = partition(input, left, right, pivot); // line 12
quickSort(input, left, index - 1); // line 13
quickSort(input, index, right); // line 14
}
}
private int partition(int[] input, int left, int right, int pivot) {
while(left <= right) {
while(input[left] < pivot) {
left++;
}
while(input[right] > pivot) {
right--;
}
if(left <= right) {
int temp = input[left];
input[left] = input[right];
input[right] = temp;
left++;
right--;
}
}
return left;
}
If works fine when I select the pivot as
int pivot = input[(left + right) / 2]; // works with this
int pivot = input[left + (right - left) / 2]; // works with this
int pivot = input[left]; // works with this
When pivot is input[right], it fails with the exception of
Exception in thread "main" java.lang.StackOverflowError
at com.maverick.solution.Solution.quickSort(Solution.java:12)
at com.maverick.solution.Solution.quickSort(Solution.java:13)
Please guide me, in correcting the issue or what is going wrong.
Thanks !
答案1
得分: 1
问题基本上出现在最大元素到达数组末尾时。在这种情况下，left 和 right 的值将会相等，partition() 将返回 array.length+1，然后会一次又一次地进行相同的函数调用。
示例：[5,4,3,2,1]
如果你调试代码，你会发现问题出现在调用 quickSort([1,4,3,2,5],1,4) 时。这个调用会触发 partition()，它会返回 5，然后在下一行再次发生 quickSort([1,4,3,2,5],1,4)，循环继续进行。
也许需要对 partition() 的逻辑进行修正，当 left 和 right 的值都相等，并且最大元素位于 right 位置时。
思考一下 partition() 的工作，基本上是要返回数组排序的索引，你的 partition() 逻辑是否实现了这一点？
尝试不同的输入并调试代码。
有关快速排序的更多信息，你可以参考这本书。
英文:
The problem basically comes when the largest element reaches the end of the array. In that situation, left and right values will be equal and partition() will return array.length+1 and same function call will be made again and again.
Example: [5,4,3,2,1]
If you debug the code, you will see that the problem starts when a quickSort([1,4,3,2,5],1,4) call happens. This calls partition() which returns 5 and in the next line again quickSort([1,4,3,2,5],1,4) happens, the cycle continues.
Probably a correction in logic is required for partition(), when both left and right values have become equal and when largest element is present at right position.
Think about the work of partition(), which basically is to return index till which array is sorted, is your logic for partition() achieving it?
Try different inputs and debug the code.
For more on quick sort, you can refer this book
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论