为什么我的快速排序方法极其缓慢?

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

Why is my Quick Sort method extremely slow?

问题

I just tried to write a quickSort() method in Java for testing, but it's performing very slowly. I want to find out what's wrong?

英文:

Just trying the iterative version of merge sort and it performs much slower than all sorting algorithms. Where am I going wrong?

public static void quickSort(int[] arr) {
    int size = arr.length;
    int count = 0;
    int[] stackArr = new int[size]; 

    stackArr[count] = 0;
    stackArr[++count] = size - 1;

    while (count >= 0) {
        int end = stackArr[count--];
        int start = stackArr[count--];
            
        int pivot = partition(arr, start, end);

        if (pivot - 1 > start) {
            stackArr[++count] = start;
            stackArr[++count] = pivot - 1;
         }
        if (pivot + 1 < end) {
            stackArr[++count] = pivot + 1;
            stackArr[++count] = end;
        }         
    }
}

public static int partition(int[] arr, int start, int end) {
    int countIndex = start ;
    for (int i = start; i < end; i++) {
        if (arr[i] <= arr[end]) {
            swap(arr, i, countIndex);
            countIndex++;
        }
    }
    swap(arr, countIndex, end);
    return countIndex;
}

public static void swap(int[] arr, int i, int j) {
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

I just tried to write a quickSort() method in java for testing and it performs really slow. I want to find out what is wrong?

答案1

得分: 1

以下是翻译好的部分:

问题中的代码将最后一个元素用作枢轴,这在已排序或逆向排序的数据上是最坏情况。问题中没有显示用于基准测试排序函数的代码:第一次排序可能对数组进行排序,然后排序后的数组可能用于基准测试中的其他排序函数。为了避免这种情况,可以使用第二个数组。在创建随机数组后,对于每个排序测试,将其复制到第二个数组并在第二个数组上进行排序。

问题还使用了Lomuto分区方案,如果存在重复值,它会恶化为最坏情况。

以下代码几乎是Hoare的快速排序的原始版本的副本,该版本是在没有本地堆栈的系统上实现的。为了将堆栈大小限制为O(log2(n)),较大的分区索引被推送到堆栈上,而较小的分区则通过回到分区代码来处理。

英文:

The code in the question is using the last element as pivot, which is worst case on already sorted or reverse sorted data. Not shown in the question is the code to benchmark the sort functions: it is possible that the first sort sorts the array, and then that sorted array is being used for the rest of the sort functions in the bench mark. To avoid this, use a second array. After creating the randomized array, for each sort test, copy it to a second array and test the sort on the second array.

The question is also using Lomuto partition scheme, which degrades towards worst case if there are duplicate values.

The following code is a near duplicate of Hoare's original version of quick sort which was implemented on a system without a native stack. To limit stack size to O(log2(n)), the larger partition indexes are pushed onto the stack, while the smaller partition is handled by looping back to partition code.

    @SuppressWarnings("empty-statement")
    public static void qsort(int[] a)
    {
        if(a.length < 2)
            return;
        // count = (1+floor(log2(a.length)))<<1 
        int count  = (32-Integer.numberOfLeadingZeros(a.length))<<1;
        int[] stack = new int[count];
        count = 0;
        stack[count++] = a.length-1;
        stack[count++] = 0;
        while(count != 0){
            int lo = stack[--count];
            int hi = stack[--count];
            while(lo < hi){
                int  md = lo+(hi-lo)/2;     // partition
                int  ll = lo-1;
                int  hh = hi+1;
                int t;
                int p = a[md];
                while(true){
                    while(a[++ll] < p);
                    while(a[--hh] > p);
                    if(ll >= hh)
                        break;
                    t     = a[ll];
                    a[ll] = a[hh];
                    a[hh] = t;
                }
                ll = hh++;
                // push larger partition indexes onto stack
                // loop on smaller partition
                if((ll - lo) >= (hi - hh)){
                    stack[count++] = ll;
                    stack[count++] = lo;
                    lo = hh;
                } else {
                    stack[count++] = hi;
                    stack[count++] = hh;
                    hi = ll;
                }
            }
        }
    }

huangapple
  • 本文由 发表于 2023年4月7日 04:35:00
  • 转载请务必保留本文链接:https://go.coder-hub.com/75953553.html
匿名

发表评论

匿名网友

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

确定