Почему этот код heapsort такой медленный, как сортировка выбора? - PullRequest
Новая
       23

Почему этот код heapsort такой медленный, как сортировка выбора?

0 голосов
/ 03 апреля 2019

Я делаю тест производительности на разных методах сортировки, а код Heapsort из GeeksforGeeks медленнее, чем сортировка Selection. Хотя его временная сложность составляет O(n*logn), похоже, он увеличивается в 4 раза, а не в 2 раза.

В следующей таблице показано прошедшее время для каждого из методов сортировки. (от первого столбца до последнего: сортировка выделения, сортировка вставкой, сортировка слиянием, быстрая сортировка, сортировка кучи) 


elements  elapsed time
1,000     0.19   0.03   0.15    0.05    0.11
2,000     0.51   0.06   0.22    0.12    0.41
4,000     1.64   0.11   0.36    0.17    1.53
8,000     7.49   0.21   0.85    0.23    5.89
16,000    33.62  0.34   1.07    0.33    28.01
32,000    123.9  0.99   1.72    0.6    118.07


public class HeapSort 
{ 
    public void sort(int arr[]) 
    { 
        int n = arr.length; 

        for (int i = n / 2 - 1; i >= 0; i--) 
            heapify(arr, n, i); 
        for (int i=n-1; i>=0; i--) 
        { 
            int temp = arr[0]; 
            arr[0] = arr[i]; 
            arr[i] = temp; 
            heapify(arr, i, 0); 
        } 
    } 

    void heapify(int arr[], int n, int i) 
    { 
        int largest = i;
        int l = 2*i + 1; 
        int r = 2*i + 2; 
        if (l < n && arr[l] > arr[largest]) 
            largest = l;  
        if (r < n && arr[r] > arr[largest]) 
            largest = r; 
        if (largest != i) 
        { 
            int swap = arr[i]; 
            arr[i] = arr[largest]; 
            arr[largest] = swap;
            heapify(arr, n, largest); 
        } 
    }
}

public class SelectionSort_asc
{
    public static void sort(int[] a)
    {
        int n = a.length;

        for (int i = 0; i < n - 1; i++) // search all of the nums (except the last one)
        {
            int lowest = i; // index of the smallest number
            int lowkey = a[i]; // the smallest number

            for (int j = i + 1; j < n; j++)
            {
                if(a[j] < lowkey)
                {
                    lowest = j; // change the index of the smallest number
                    lowkey = a[j]; // value of the smallest number also changes
                }
            }
            int temp = a[i];
            a[i] = a[lowest];
            a[lowest] = temp; // swap a[i] and the smallest number found
        }
    }
}

Почему скорость так отличается от ожидаемой? Пожалуйста, помогите.

1 Ответ

0 голосов
/ 03 апреля 2019

Пример кода heapsort. В моей системе 32 000 элементов не занимают достаточно много времени, так как на дисплее отображается 0 миллисекунд. 10 000 000 элементов занимает около 2 секунд. Используя сортировку выбора, которую вы разместили, 64 000 элементов занимают около 2,5 секунд; это намного медленнее. 

package heapsort;
import java.util.Random;

public class heapsort {

    static void HeapSort(int[] a)
    {
    int end;
        Heapify(a);
        end = a.length-1;
        while(end > 0){
            int t = a[0];
            a[0] = a[end];
            a[end] = t;
            end--;
            SiftDown(a, 0, end);
        }
    }

    static void Heapify(int[] a)
    {
    int root;
        if(a.length < 2)
            return;
        root = (a.length - 2) / 2;
        while(true){
            SiftDown(a, root, a.length-1);
            if(root == 0)
                break;
            root--;
        }
    }

    static void SiftDown(int[] a, int root, int end){
    int parent;
    int child;
    int t;
        for(parent = root; (child = parent * 2 + 2) <= end; ){
            if(a[child-1] > a[child])
                child = child-1;
            if(a[child] > a[parent]){
                t = a[child];
                a[child] = a[parent];
                a[parent] = t;
                parent = child;
            } else {
                break;
            }
        }
        if((child = parent * 2 + 1) <= end){
            if(a[child] > a[parent]){
                t = a[child];
                a[child] = a[parent];
                a[parent] = t;
            }
        }
    }

    public static void main(String[] args) {
        int[] a = new int[32000];
        Random r = new Random();
        for(int i = 0; i < a.length; i++)
            a[i] = r.nextInt();
        long bgn, end;
        bgn = System.currentTimeMillis();
        HeapSort(a);
        end = System.currentTimeMillis();
        for(int i = 1; i < a.length; i++){
            if(a[i-1] > a[i]){
                System.out.println("failed");
                break;
            }
        }
        System.out.println("milliseconds " + (end-bgn));
    }
}
...