自制的快速排序算法抛出栈溢出异常：在分区方法中查找下一个枢轴位置

huangapple
go评论97阅读模式
英文:

Home-rolled Quicksort algorithm throwing stack overflow exception: finding next location of pivot in partition method

问题

这是我的快速排序代码，对于正常情况它是有效的，但对于数组中包含相同元素的情况，我的代码出现问题。在这种情况下，我考虑将等于枢轴的元素放在枢轴的左侧。请帮我找出代码中的逻辑错误：

  1. public class Solution {
  3.     public static int partition(int input[], int si, int ei) {
  4.         int pivot = input[si], pivotPos = si, count = 0;
  5.         // 计算小于等于枢轴的元素数量，以便在枢轴左侧留出空间
  6.         for (int i = pivotPos + 1; i < input.length; i++) {
  7.             if (input[i] <= pivot)
  8.                 count++;
  9.         }
  10.         // 交换枢轴和元素
  11.         input[si] = input[si + count];
  12.         input[si + count] = pivot;
  13.         pivotPos = si + count;
  14.         // 确保枢轴左侧的元素都小于等于枢轴，右侧的元素都大于枢轴
  15.         int i = si, j = ei, temp;
  17.         while (i < pivotPos && j > pivotPos) {
  18.             if (input[i] <= pivot)
  19.                 i++;
  20.             else {
  21.                 if (input[j] > pivot)
  22.                     j--;
  23.                 else {
  24.                     temp = input[i];
  25.                     input[i] = input[j];
  26.                     input[j] = temp;
  27.                     i++;
  28.                     j--;
  29.                 }
  30.             }
  31.         }
  32.         return pivotPos;
  33.     }
  35.     public static void quickSort(int input[], int si, int ei) {
  36.         if (si >= ei)
  37.             return;
  38.         int pivotPos = partition(input, si, ei);
  39.         quickSort(input, si, pivotPos - 1);
  40.         quickSort(input, pivotPos + 1, ei);
  41.     }
  43.     public static void quickSort(int[] input) {
  44.         quickSort(input, 0, input.length - 1);
  45.     }
  46. }

输入测试案例：
4 3 8 4 6 5
期望输出：
3 4 4 5 6 8

我的代码在调用分区函数的地方引发堆栈溢出错误。

英文:

hey this is my quicksort code and its working for normal cases but not for those where the array have same elements and in that case i considered putting elements which are equal to pivot to the left side of pivot.Could anyone please rectify the logical mistake in my code:

  2. public class Solution {
  3. public static int partition(int input[],int si, int ei) {
  4. int pivot = input[si],pivotPos = si,count = 0;
  5. // counting no of elements less than pivot so that  space can be left empty to left of pivot
  6. for(int i = pivotPos+1; i&lt;input.length;i++) {
  7. if(input[i]&lt;=pivot)
  8. count++;
  9. }
  10. //swapping pivot with the element
  11. input[si] = input[si+count];
  12. input[si+count] = pivot;
  13. pivotPos = si+count;
  14. // ensuring all elements to the left of pivot are less and to the right are more
  15. int i = si, j = ei,temp;
  16. while(i&lt;pivotPos &amp;&amp; j&gt;pivotPos) {
  17. if(input[i]&lt;=pivot)
  18. i++;
  19. else  {
  20. if(input[j]&gt;pivot)
  21. j--;
  22. else {
  23. temp = input[i];
  24. input[i] = input[j];
  25. input[j] = temp;
  26. i++;
  27. j--;
  28. }
  29. }
  30. }
  31. return pivotPos;
  32. }
  33. public static void quickSort(int input[], int si, int ei) {
  34. if(si&gt;=ei)
  35. return; 
  36. int pivotPos =  partition(input,si,ei);
  37. quickSort(input,si,pivotPos-1);
  38. quickSort(input,pivotPos+1,ei);
  39. }
  40. public static void quickSort(int[] input) {
  41. /* Your class should be named Solution
  42. * Don&#39;t write main().
  43. * Don&#39;t read input, it is passed as function argument.
  44. * No need to print or return the output.
  45. * Taking input and printing output is handled automatically.
  46. */
  47. quickSort(input,0,input.length - 1);
  48. }
  49. }

input test case:
4 3 8 4 6 5
expected output:
3 4 4 5 6 8

my code gives stack overflow error from the point where partition function is being called

答案1

得分: 0

我认为我已经修复了你的代码，同时最小程度地更改了你的代码风格。你会注意到，尽管我们实际上不需要它，但我保留了一些你的代码。我将它们留在那里供你对比。

  1. public class QuickSort {
  3.     public static int partition(int input[], int si, int ei) {
  4.         int pivot = input[si], pivotPos = si, count = 0;
  5.         // 计算小于 pivot 的元素数量，以便在 pivot 左侧留出空间
  7.         for (int i = pivotPos + 1; i < input.length; i++) {
  8.             if (input[i] <= pivot) {
  9.                 count++;
  10.             }
  11.         }
  12.         // 上面的 count 不是我们需要的信息
  13.         // 我们需要知道在 si 和 ei（包括）之间有多少个元素小于 pivot 的值
  15.         // 修正的逻辑在这里：
  16.         int smallerThanPivotCount = 0;
  17.         for (int i = si; i <= ei; i++) { // 请注意，我们的逻辑包括 ei
  18.             if (input[i] < pivot)
  19.                 smallerThanPivotCount++;
  20.         }
  22.         // 交换 pivot 与元素
  23.         input[si] = input[si + smallerThanPivotCount];
  24.         input[si + smallerThanPivotCount] = pivot;
  25.         pivotPos = si + smallerThanPivotCount;
  27.         // 接下来
  28.         // 确保 pivot 左侧的所有元素都小于 pivot，右侧的所有元素都大于 pivot
  29.         int i = si, j = ei, temp;
  31.         while (i < pivotPos && j > pivotPos) {
  32.             if (input[i] <= pivot)
  33.                 i++;
  34.             else {
  35.                 if (input[j] >= pivot)
  36.                     j--;
  37.                 else {
  38.                     temp = input[i];
  39.                     input[i] = input[j];
  40.                     input[j] = temp;
  41.                     i++;
  42.                     j--;
  43.                 }
  44.             }
  45.         }
  46.         return pivotPos;
  47.     }
  49.     public static void quickSort(int input[], int si, int ei) {
  50.         if (si >= ei)
  51.             return;
  52.         int pivotPos = partition(input, si, ei);
  53.         quickSort(input, si, pivotPos - 1);
  54.         quickSort(input, pivotPos + 1, ei);
  55.     }
  57.     public static void quickSort(int[] input) {
  58.         /* 你的类应该命名为 Solution
  59.          * 不要写 main()。
  60.          * 不要读取输入，它作为函数参数传递。
  61.          * 无需打印或返回输出。
  62.          * 输入和输出处理都是自动完成的。
  63.          */
  64.         quickSort(input, 0, input.length - 1);
  65.     }
  66. }

我认为你的问题只是没有正确地计算向前移动 pivot 所需的空格数量。我已经编写了代码。我不能百分之百保证它是正确的，但它通过了我的一小部分单元测试，包括你自己的示例数组。我建议你自己检查它以理解逻辑。然后清理掉多余的部分，使它成为你自己的代码。祝好运。

英文:

I think I have fixed your code while making minimal changes to your code style. You'll notice that I left some of your code in even though it isn't what we actually need to do. I left that in for your comparison.

  1. public class QuickSort {
  2. public static int partition(int input[],int si, int ei) {
  3. int pivot = input[si],pivotPos = si,count = 0;
  4. // counting no of elements less than pivot so that  space can be left empty to left of pivot
  5. for(int i = pivotPos+1; i&lt;input.length;i++) {
  6. if(input[i]&lt;=pivot) {
  7. count++;
  8. }
  9. }
  10. // the above var count is not the info we need
  11. // we need to know how many elements between si and ei (inclusive)
  12. // are less than the value of pivot
  13. // corrected logic here:
  14. int smallerThanPivotCount = 0;
  15. for (int i = si; i &lt;= ei; i++) { // note that our logic includes ei
  16. if (input[i] &lt; pivot)
  17. smallerThanPivotCount++;
  18. }
  19. //swapping pivot with the element
  20. input[si] = input[si + smallerThanPivotCount];
  21. input[si + smallerThanPivotCount] = pivot;
  22. pivotPos = si + smallerThanPivotCount;
  23. // next we are
  24. // ensuring all elements to the left of pivot are less and to the right are more
  25. int i = si, j = ei,temp;
  26. while(i&lt;pivotPos &amp;&amp; j&gt;pivotPos) {
  27. if(input[i]&lt;=pivot)
  28. i++;
  29. else  {
  30. if(input[j]&gt;=pivot)
  31. j--;
  32. else {
  33. temp = input[i];
  34. input[i] = input[j];
  35. input[j] = temp;
  36. i++;
  37. j--;
  38. }
  39. }
  40. }
  41. return pivotPos;
  42. }
  43. public static void quickSort(int input[], int si, int ei) {
  44. if(si&gt;=ei)
  45. return;
  46. int pivotPos =  partition(input,si,ei);
  47. quickSort(input,si,pivotPos - 1);
  48. quickSort(input,pivotPos+1,ei);
  49. }
  50. public static void quickSort(int[] input) {
  51. /* Your class should be named Solution
  52. * Don&#39;t write main().
  53. * Don&#39;t read input, it is passed as function argument.
  54. * No need to print or return the output.
  55. * Taking input and printing output is handled automatically.
  56. */
  57. quickSort(input,0,input.length - 1);
  58. }
  59. }

I think your problem was just that you didn't correctly count the number of spaces forward you needed to shift the pivot. I have written code. I don't guarantee you 100% that it is correct, but it does pass my short list of unit tests, including your own example array. I suggest examining it yourself to understand the logic. Then clean up the extra stuff and make it your own. Cheers.

huangapple
  • 本文由 发表于 2023年5月24日 17:45:44
  • 转载请务必保留本文链接：https://go.coder-hub.com/76322171.html
  • arrays
  • java
  • quicksort
  • sorting
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定