Блог

Я провожу тест производительности для разных методов сортировки, и код сортировки по куче из GeeksforGeeks работает медленнее, чем сортировка по выбору. Хотя его временная сложность составляет 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 amp;amp; arr[l] > arr[largest]) 
            largest = l;  
        if (r < n amp;amp; 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
        }
    }
}

  

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

Пример кода сортировки по куче. В моей системе 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));
    }
}