Sortowanie- Bubble, Quick, Insertion- porówanie czasów

Question

Witam, porównuję czasy sortowania poszczególnych algorytmów i z tego co się orientuję to QuickSort powinno być najszybsze .. natomiast u mnie najlepiej wypada Insertion Sort. Może mam coś nie tak z algorytmem Quick?

import java.util.Random;

public class Main {

    public static void main(String[] args) {
        Random random = new Random();
        int[] arrayToSort = new int[10000];
        int[] unsortedArray;
        for (int i = 0; i < 10000; i++) {
            arrayToSort[i] = random.nextInt(10000);
            System.out.print(arrayToSort[i] + ", ");
        }
        unsortedArray = arrayToSort;
        System.out.println(" ");
        System.out.println("---------------");
        long timeBeforeBubbleSort = System.nanoTime();
        arrayBubbleSort(arrayToSort);
        long timeAfterBubbleSort = System.nanoTime();
        System.out.println("Bubble sort: ");
        for (int sort : arrayToSort) {
            System.out.print(sort + ", ");
        }
        System.out.println(" ");
        System.out.println("Czas sortowania bąbelkowego: " + calculateTimeOfSorting(timeBeforeBubbleSort, timeAfterBubbleSort)
        );
        arrayToSort = unsortedArray;
        System.out.println("---------------");
        long timeBeforeInsertionSort = System.nanoTime();
        arrayInsertionSort(arrayToSort);
        long timeAfterInsertionSort = System.nanoTime();
        System.out.println("Insertion sort: ");
        for (int sort : arrayToSort) {
            System.out.print(sort + ", ");
        }
        System.out.println(" ");
        System.out.println("Czas sortowania przez  wstawianie: " + calculateTimeOfSorting(timeBeforeInsertionSort, timeAfterInsertionSort));
        arrayToSort = unsortedArray;
        System.out.println("---------------");
        long timeBeforeQuickSort = System.nanoTime();
        arrayQuickSort(arrayToSort, 0, arrayToSort.length - 1);
        long timeAfterQuickSort = System.nanoTime();
        System.out.println("Quick sort: ");
        for (int sort : arrayToSort) {
            System.out.print(sort + ", ");
        }
        System.out.println(" ");
        System.out.println("Czas sortowania szybkiego: " + calculateTimeOfSorting(timeBeforeQuickSort, timeAfterQuickSort));


    }

    public static void arrayBubbleSort(int[] arrayToSort) {
        for (int i = 0; i < arrayToSort.length; i++) {
            for (int j = 0; j < arrayToSort.length - 1; j++) {
                if (arrayToSort[j] > arrayToSort[j + 1]) {
                    int temp = arrayToSort[j];
                    arrayToSort[j] = arrayToSort[j + 1];
                    arrayToSort[j + 1] = temp;
                }
            }
        }
    }

    public static void arrayInsertionSort(int[] arrayToSort) {
        int currentNumber, otherIndex;
        for (int i = 1; i < arrayToSort.length; i++) {
            currentNumber = arrayToSort[i];
            otherIndex = i;
            while (otherIndex > 0 && currentNumber < arrayToSort[otherIndex - 1]) {
                arrayToSort[otherIndex] = arrayToSort[otherIndex - 1];
                otherIndex--;
            }
            arrayToSort[otherIndex] = currentNumber;
        }
    }

    public static void arrayQuickSort(int[] arrayToSort, int left, int right) {
        if (left >= right) {
            return;
        }
        int pivotValue = arrayToSort[right];
        int border = left - 1;
        int i = left;

        while (i < right) {
            if (arrayToSort[i] < pivotValue) {
                border++;
                if (border != i) {
                    int temp = arrayToSort[border];
                    arrayToSort[border] = arrayToSort[i];
                    arrayToSort[i] = temp;
                }
            }
            i++;
        }
        border++;
        if (border != right) {
            int temp = arrayToSort[border];
            arrayToSort[border] = arrayToSort[right];
            arrayToSort[right] = temp;
        }

        arrayQuickSort(arrayToSort, left, border - 1);
        arrayQuickSort(arrayToSort, border + 1, right);
    }

    public static long calculateTimeOfSorting(long timeBefore, long timeAfter) {
        long difference = timeAfter - timeBefore;
        long timeOfSortingToMicroseconds = (long) (difference* 0.001);
        return timeOfSortingToMicroseconds;

    }
}

 

Comments

Jakby się czepiać czystych formalizmów to nie zawsze tak jest z tą szybkością algorytmów, to zależy od konkretnego przypadku tj. dla odpowiedniego porządku danych wejściowych najgorszy przypadek quicksorta (zlozonosc kwadratowa), może się okazać wolniejszy niż najlepszy przypadek insertsorta (liniowa). I tak dla np małych tablic quicksort jest faktycznie wolniejszy niż insertsort.

Answer 1

Nie wnikałem w szczegóły, ale... na oko wszędzie poza pierwszym razem "sortujesz" już posortowaną tablicę.

Konkretniej:

unsortedArray = arrayToSort;
arrayBubbleSort(arrayToSort);

unsortedArray i arrayToSort to ta sama tablica. unsortedArray też staje się posortowane.

Comments

dzięki, zrobiłam to w inny sposób (przypisanie tablicy arrayToSort do 3 różnych tablic za pomocą pętli) i w ten sposób nie sortuję posortowanych tablic. Przy okazji mój problem z czasem też się rozwiązał, nie do końca rozumiem dlaczego ale działa :)

---

przypisanie tablicy arrayToSort do 3 różnych tablic za pomocą pętli

(można było też po prostu skopiować tablice używając .clone())

---

nie znałam tej opcji, spróbuję. dzięki