int array -> Integer Array

Nu er det godt nok lidt sent, så jeg garantere ikke 100%.

Men jeg mener du må caste dem enkeltvis til den nye type.

Eventuelt kan du jo bare bruge den Indbyggede sort i Arrays.sort();

Jeg søger en alternativ sorteringsalgoritme som er hurtigere end QuickSort og MergeSort, har du nogen forslag ??

Hvis jeg skal caste dem enkeltvis, så skal jeg jo bruge en forløkke mere, og det tager jo farten af algoritmen...

Sådan ser sammenhængen ud:

protected void sort() {
      Integer[] arr = new Integer[array.length];   

      for(i=0;i<array.length;i++){
//  Den oprindelige:    arr[i] = new Integer((int)(Math.random()));
        arr[i] = new Integer((int)(array));
      }
     
      qsort(arr);
    }

Det er korrekt det tager farten af algoritmen, men tidskomplexiteten er O(1) altså den er ligefrem propertional med antal elementer og derfor stadigvæk en hurtig routine.

Hvis du har et begrænset område tallene kan være indenfor ville jeg anvende en Bucketsort som er meget hurtig med en komplexitet på O(1);

Hvis du skal sortere alle tal imellem 1 og 10 laver du 10 spande, så tager du tallene en efter en, og tæller spanden med det rigtige nummer 1 op, osv.

f.eks. tallet 5 tæller spand #5 1 op osv.

bagefter løber du spandende igennem og udlæser antallet.

Så er det sorteret.

Ulempe ved f.eks. personnumre kræver det rigtigt mange spande, men er MEGET hurtig.

Og jeg vil gerne helt af med forløkken, da arrayet bliver dannet i en anden klasse...derfor vil jeg caste arrayet (array) så jeg kan sætte den lige ind i qsort(array)..

din qsort() hvad type kræver den som parameter ?

public static void qsort( Comparable[] c)

Så må du få metoden der generere data der skal sorteres til at lave dem om til Integers med det samme.

Er O(1) ikke konstant tid? - det må være O(n). Det ville nok være smartest at lave qsort om til public static void qsort( int[] c ) - du kan bare lave din egen compareTo:

static int compareTo( int i1, int i2 )
{
  return i2 - i1; //eller omvendt?..
}

- og udskifte al brug af "Comparable" med "int".

Der er ikke nogen generelle sorterings-algoritmer som er hurtigere end
quicksort, heapsort og mergesort der alle er n*log(n) algoritmer.

Og selvom heapsort har lidt bedre teoretiske egenskaber, så
viser mange års erfaring at quicksort er hurtigst.

Hvis du er interessert i hurtig sortering, så skal du ikke sortere
Integer[] men int[], da der er et markant overhead på at sortere
vilkårlige objekter.

Prøv og kør følgende program - det vil illustrere:

import java.util.Arrays;

public class SortTest {
    private final static int N = 1000000;
    public static void main(String[] args) {
        int[] ia = new int[N];
        Integer[] ioa = new Integer[N];
        for (int i = 0; i < N; i++) {
            ia[i] = (int) (Math.random() * N);
            ioa[i] = new Integer(ia[i]);
        }
        test1((int[]) ia.clone());
        test2((int[]) ia.clone());
        test3((Integer[]) ioa.clone());
        test4((Integer[]) ioa.clone());
    }
    public static void test1(int[] ia) {
        long t1 = System.currentTimeMillis();
        qsint(ia);
        long t2 = System.currentTimeMillis();
        for (int i = 0; i < 10; i++)
            System.out.print(" " + ia[i]);
        System.out.println();
        System.out.println("int homemade QS : " + (t2 - t1));
        return;
    }
    public static void test2(int[] ia) {
        long t1 = System.currentTimeMillis();
        Arrays.sort(ia);
        long t2 = System.currentTimeMillis();
        for (int i = 0; i < 10; i++)
            System.out.print(" " + ia[i]);
        System.out.println();
        System.out.println("int Java builtin sort: " + (t2 - t1));
        return;
    }
    public static void test3(Integer[] ioa) {
        long t1 = System.currentTimeMillis();
        qsobj(ioa);
        long t2 = System.currentTimeMillis();
        for (int i = 0; i < 10; i++)
            System.out.print(" " + ioa[i]);
        System.out.println();
        System.out.println("Integer homemade QS : " + (t2 - t1));
        return;
    }
    public static void test4(Integer[] ioa) {
        long t1 = System.currentTimeMillis();
        Arrays.sort(ioa);
        long t2 = System.currentTimeMillis();
        for (int i = 0; i < 10; i++)
            System.out.print(" " + ioa[i]);
        System.out.println();
        System.out.println("Integer Java builtin sort : " + (t2 - t1));
        return;
    }
    private static void qsint_help(int n1, int n2, int[] ia) {
        int tmp;
        int l = n1;
        int r = n2;
        int pivot = ia[(n1 + n2) / 2];
        do {
            while (ia[l] < pivot)
                l++;
            while (ia[r] > pivot)
                r--;
            if (l <= r) {
                tmp = ia[l];
                ia[l] = ia[r];
                ia[r] = tmp;
                l++;
                r--;
            }
        }
        while (l <= r);
        if (n1 < r)
            qsint_help(n1, r, ia);
        if (l < n2)
            qsint_help(l, n2, ia);
        return;
    }

    private static void qsint(int[] ia) {
        qsint_help(0, ia.length - 1, ia);
        return;
    }
    private static void qsobj_help(int n1, int n2, Comparable[] oa) {
        Comparable tmp;
        int l = n1;
        int r = n2;
        Comparable pivot = oa[(n1 + n2) / 2];
        do {
            while (oa[l].compareTo(pivot) < 0)
                l++;
            while (oa[r].compareTo(pivot) > 0)
                r--;
            if (l <= r) {
                tmp = oa[l];
                oa[l] = oa[r];
                oa[r] = tmp;
                l++;
                r--;
            }
        }
        while (l <= r);
        if (n1 < r)
            qsobj_help(n1, r, oa);
        if (l < n2)
            qsobj_help(l, n2, oa);
        return;
    }

    private static void qsobj(Comparable[] oa) {
        qsobj_help(0, oa.length - 1, oa);
        return;
    }
}

[SUN må iøvrigt have fundet et lille trick for objekt sorteringen - gad vide
om en af de andre algoritmer er hurtigere for objekter]

zerocool>

Har du fået nogle svar du kunen bruge ?

I fik hver 20 point for at prøve at løse problemet

ulrikm:
Jo du har ret det er O(n), quick sort har dog et problem, den kan ende om med O(n^2) hvis data ligger præcist omvendt af ønsket rækkefølge.

disky>

Hvis man tager det første eller sidste element som pivot
element vil sorterede eller omvendt sorterede data
degenerere til O(n^2).

Derfor bør man altid tage midterste element som pivot element.

Der er selvfølgelig også nogle worst case rækkefølger for det, men
sandsyneligheden for at rende ind i dem er meget meget lille.

Der er mange måder at ødelægger quicksort på, men jeg går ud fra at metoden er korrekt implementeret.

Og hvis data er omvendt, tager det O(N^2) tid.

Nej. Kun hvis man bruger første eller sidste element som pivot element.

Man kan ikke bare tage det midterste element og regne med at det er godt. Man kan sagtens være uheldig at det midterste element er eksempelvis det mindste. For at formindske chancen endnu mere, kan man tage det første, sidste og midterste tal og så vælge medianen af de 3 tal.

Der er ikke nogen der har påstået at det midterste tal er "godt".

Men det midterste tal har ikke problemer med data der er sorteret i forvejen.