Sortering af int array

den sort er da indbygget i klassen java.util.Arrays
http://java.sun.com/j2se/1.3/docs/api/java/util/Arrays.html

mvh JakobA

Ups! Glemte at sige, at det skal fungere i JDK 1.1.8 :) Det skal altså laves manuelt...

- Jonas

OK. og du vil have en ny, sorteret version af det array. det er ikke nok at det array du giver som parameter bliver sorteret?

java.util.Arrays kræver 1.2 elle rhøjere.

Men prøv og kig på den kode her:

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((int[]) ia.clone());
        test4((Integer[]) ioa.clone());
        test5((Integer[]) ioa.clone());
      test6((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();
        for (int i = 0; i < 10; i++)
            System.out.print(" " + ia[N-10+i]);
        System.out.println();
      System.out.println("int homemade QS : " + (t2 - t1));
      return;
  }
    public static void test2(int[] ia) {
        long t1 = System.currentTimeMillis();
        hsint(ia);
        long t2 = System.currentTimeMillis();
        for (int i = 0; i < 10; i++)
            System.out.print(" " + ia[i]);
        System.out.println();
        for (int i = 0; i < 10; i++)
            System.out.print(" " + ia[N-10+i]);
        System.out.println();
        System.out.println("int homemade HS : " + (t2 - t1));
        return;
    }
  public static void test3(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();
        for (int i = 0; i < 10; i++)
            System.out.print(" " + ia[N-10+i]);
        System.out.println();
      System.out.println("int Java builtin sort: " + (t2 - t1));
      return;
  }
  public static void test4(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();
        for (int i = 0; i < 10; i++)
            System.out.print(" " + ioa[N-10+i]);
        System.out.println();
      System.out.println("Integer homemade QS : " + (t2 - t1));
      return;
  }
    public static void test5(Integer[] ioa) {
        long t1 = System.currentTimeMillis();
        hsobj(ioa);
        long t2 = System.currentTimeMillis();
        for (int i = 0; i < 10; i++)
            System.out.print(" " + ioa[i]);
        System.out.println();
        for (int i = 0; i < 10; i++)
            System.out.print(" " + ioa[N-10+i]);
        System.out.println();
        System.out.println("Integer homemade HS : " + (t2 - t1));
        return;
    }
  public static void test6(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();
        for (int i = 0; i < 10; i++)
            System.out.print(" " + ioa[N-10+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;
  }
  private static void hsint_help(int[] ia, int ix, int n) {
      int p = ix;
      int tmp = ia[p - 1];
      int c = 2 * p;
      boolean found = false;
      while ((c <= n) && !found) {
        if ((c < n) && (ia[c] > ia[c - 1])) {
            c++;
        }
        if (ia[c - 1] > tmp) {
            ia[p - 1] = ia[c - 1];
            p = c;
            c = 2 * p;
        } else {
            found = true;
        }
      }
      ia[p - 1] = tmp;
        return;
  }
    private static void hsint(int[] ia) {
        int ix1 = ia.length / 2;
        while(ix1 > 0) {
            hsint_help(ia, ix1, ia.length);
            ix1--;
        }
        int ix2 = ia.length;
        int tmp;
        while(ix2 > 1) {
            tmp = ia[0];
            ia[0] = ia[ix2 - 1];
            ia[ix2 - 1] = tmp;
            ix2--;
            hsint_help(ia, 1, ix2);
        }
        return;
    }
    private static void hsobj_help(Comparable[] oa, int ix, int n) {
        int p = ix;
        Comparable tmp = oa[p - 1];
        int c = 2 * p;
        boolean found = false;
        while ((c <= n) && !found) {
            if ((c < n) && (oa[c].compareTo(oa[c - 1]) > 0)) {
                c++;
            }
            if (oa[c - 1].compareTo(tmp) > 0) {
                oa[p - 1] = oa[c - 1];
                p = c;
                c = 2 * p;
            } else {
                found = true;
            }
        }
        oa[p - 1] = tmp;
        return;
    }
    private static void hsobj(Comparable[] oa) {
        int ix1 = oa.length / 2;
        while(ix1 > 0) {
            hsobj_help(oa, ix1, oa.length);
            ix1--;
        }
        int ix2 = oa.length;
        Comparable tmp;
        while(ix2 > 1) {
            tmp = oa[0];
            oa[0] = oa[ix2 - 1];
            oa[ix2 - 1] = tmp;
            ix2--;
            hsobj_help(oa, 1, ix2);
        }
        return;
    }
}

det får du ikke her. det er blot dit array der er sorteret bagefter:

public static sort(int[] a){
    int i, j, max, temp;
    for ( j=a.length-1; j>0; j-- ) {
        max = 0;
        for ( i=1; i<=j; i++ ) {
            if ( a[i] >= a[max] ) max = i;  // find index på største tal
        }
        if ( max != j ) {                // flyt største tal hen forenden
            temp = a[j];
            a[j] = a[max];
            a[max] = temp;
        }
    }
} //endfunction sort

// testkode:
int[] testarray = { 9, 8, 7, 6, 5, 1, 2, 3, 4 };
sort( testarray );
for ( int i=0; i<testarray.length; i++ ) {
    System.out.println( testarray[i] );
}

mvh JakobA

Den indeholder qsint (Quick Sort) og hsint (Heap Sort) som skulle kunne køre
på enhver Java version.

Hvis du vil beholde original data uændret så lav en clone ligesom
test programmet gør.

jakoba: Ja, jeg vil gerne ha' et nyt array...
arne_v: jeg kan desværre ikke bruge koden direkte, men hvis jeg får tid, vil jeg da prøve at kigge på det

Hvis du nu stjæler:

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;
  }
 
og laver en:

public static int[] sort(int[] a) {
  int[] res = (int[])a.clone();
  qsint(res);
  return res;
}

public static sort(int[] a){
    int[] res = new int[ a.length ]
    int i, j, max, temp;
    for ( j=a.length-1; j>0; j-- ) {
        max = 0;
        for ( i=0; i<=j; i++ ) {
            if ( a[i] >= a[max] ) max = i;  // find index på største tal
        }
                // flyt største tal op forenden
        res[j] = a[max];
        if ( max != j ) a[max] = a[j];
    }
    return res;
} //endfunction sort

Ups. jeg glemte at give funktionen en type (og forresten ødelægger jeg det oprindelige array)

public static int[] sort(int[] a){
    int i, j, max, temp;
    int[] res = new int[ a.length ]
    for ( i=0; i<a.length; i++ ) res[i] = a[i];  // kopier fra gammelt array
    for ( j=a.length-1; j>0; j-- ) {
        max = 0;
        for ( i=0; i<=j; i++ ) {
            if ( res[i] >= res[max] ) max = i;  // find index på største tal
        }
        if ( max != j ) {                // flyt største tal hen forenden
            temp = res[j];
            res[j] = res[max];
            res[max] = temp;
        }
    }
    return res;
} //endfunction sort

mvh JakobA

Det ser jo fornuftigt ud... Jeg deler pointene ligeligt.

- Jonas

Jakobs kode er god til at forstå logikken.

Quick sort er hurtigere hvis der skal sorteres rigtigt mange tal.