Frage zu Sortieralgorithmus

[Reality]

Hi,
kann mir bitte jemand sagen, warum bei diesem Sortiertalgorithmus der gleiche ArrayIndex einen anderen Wert aufweist?

50 0
55 2
80 4
96 4
98 5
31 6
39 6
53 6
49 7
60 7
67 7
91 7
77 9
84 9
31 13
53 15
82 15
37 16
78 17
82 18
86 18
61 19
32 20
64 20
83 20
80 22
54 23
65 24
95 24
57 25
36 26
46 26
52 27
81 27
49 28
57 28
58 28
94 30
46 31
98 31
51 32
63 32
45 33
50 33
84 33
84 35
100 37
73 39
52 40
87 40
68 41
85 41
79 42
81 42
84 42
68 43
100 43
82 45
87 45
86 47
94 47
67 49
82 49
97 50
100 50
82 51
72 52
88 52
87 53
88 55
92 55
82 57
83 58
85 58
89 58
79 59
85 59
80 61
88 61
93 61
94 62
99 62
91 63
88 64
89 65
96 65
88 67
99 67
93 68
95 68
96 68
93 69
99 69
95 70
100 72
97 75
99 75
100 75
99 79
100 79

import java.awt.*;
import java.awt.event.*;
import java.util.Random;

public class Minimum extends Frame {

    int h[] = new int[101];

    public Minimum() {
        int i;
        Random r = new Random();        
        for (i=1;i<=100;i++) {
            h[i]=(int)(r.nextDouble()*80);
        }
    }

    public void paint(Graphics g) {
        int i;
        int min;
        int j;
        int l;
        int hilfsvar;

        /*g.setColor(Color.black);
        for (l=1;l<=100;l++) { //total unnötig!
            g.fillRect(l,120-h[l],3,h[l]);
        }*/
        
        for (i=1;i<=100;i++) { // i ist das i schon deklariert wurde 
            min=i;
            for (j=i+1;j<=100;j++) {
                if (h[j]<h[min]) min=j; //Sortiert die Array-Adressen
            }
            System.out.println(min+" "+h[min]);
            
            g.setColor(Color.white);
            g.fillRect(min*5,20,5,100);
            g.fillRect(i*5,20,5,100);
            
            hilfsvar = h[min];
            h[min]=h[i];
            h[i]=hilfsvar;
            
            g.setColor(Color.black);
            g.fillRect(min*5,120-h[min],3,h[min]);
            g.fillRect(i*5,120-h[i],3,h[i]);
        }
    }

    public static void main (String [] args) {
        Minimum sprog = new Minimum();
        WindowListener wl = new WindowAdapter() {
                public void windowClosing(WindowEvent e) {
                    System.exit(0);
                }
            };
        sprog.addWindowListener(wl);
        sprog.setTitle("Sortieren durch Minimumsuche");
        sprog.setLocation(100,100);
        sprog.setSize(520,120);
        sprog.setVisible(true);
    }
}

Liebe Grüße
Reality

 

[bygones]

du vertauschst ja hier elemente:

hilfsvar = h[min];
            h[min]=h[i];
            h[i]=hilfsvar;

dadurch ändert sich natürlich auch der wert an einem Index....

ps: wenn es dir egal ist ob du den algorithmus selbst schreibst würde ich dir die Methode Arrays.sort empfehlen... der sortiert für dich ?!

 

[Reality]

Danke, bin ganz schön durcheinander gekommen, weil ich manchmal h[min] mit min gleichgesetzt habe.
Zu Arrays.sort(): Danke für den Tipp. Spart Code, aber schneller ist es nicht, hab´s gemessen. Aber ist natürlich trotzdem besser als das manuell zu machen (wenn man es kann).

Liebe Grüße
Reality

 

[Beni]

aber schneller ist es nicht, hab´s gemessen

Das glaub ich Dir schlicht und einfach nicht (das es schneller ist). Mit wieviel Einträgen hast du es versucht? Nimm mal so richtig viele, 100'000 oder so.

Wenn ich dein Algo richtig interpretiere dürfte das ein O(n^2)-Algo sein, die sort-Methode ist aber sicher einer der O(n*log n)-Algos -> ab einer gewissen Grenze wird er schneller sein.

 

[bygones]

ich stimme Beni zu....
dein Algorithmus ist ein einfacher 2 - schleifen durchlauf algorithmus (bubble sort glaub ich ?!).... und der hat eine quadratische Laufzeit. Arrays sort ist ein O(n*log n) algorithmus....

 

[Reality]

Ich habe gesagt, dass Arrays-sort nicht schneller sei und nicht langsamer. Aber das trifft leider zu:
Bei 10 000 Einträgen (getestet mit JDK 1.5 RC):

Bubblesortähnliche Methode: 381 Millisekunden
Arrays.sort : 4697 Millisekunden

Ich habe das mehrmals getestet und es kam immer ungefähr dasselbe heraus.
Testet es doch selbst.

Liebe Grüße
Reality

 

[bygones]

tut mir leid ich habe eine völlig anderes ergebnis....

Ich fülle 10 mal einen 10.000 Element großen double Array. einmal messe ich die Durchschnitts zeit die er braucht mit deinem Algo (mit dem bubblesort) und einmal mit dem sort Algo von Arrays.

Ergebnis:
bubbleSort: avg. 800 ms
Arrays.sort: avg <10ms

getestet mit 1.5Beta

 

[Reality]

Ich habe das jetzt nocheinmal laufen lassen und es kommt zum selben Ergebnis.
Könnt ihr das mal bitte kompilieren?

import java.awt.*;
import java.awt.event.*;
import java.util.Random;
import java.util.*;
public class Minimum extends Frame {

    int h[] = new int[10001];

    public Minimum() {
        int i;
        Random r = new Random();        
        for (i=1;i<=10000;i++) {
            h[i]=(int)(r.nextDouble()*80);
        }
    }

    public void paint(Graphics g) {
        int i;
        int min;
        int j;
        int l;
        int hilfsvar;

        long start = System.currentTimeMillis();
        for (i=1;i<=10000;i++) { // i ist das i schon deklariert wurde 
            min=i;
            for (j=i+1;j<=10000;j++) {
                if (h[j]<h[min]) min=j; //Sortiert die Array-Adressen
            }
            
            g.setColor(Color.white);
            g.fillRect(min*5,20,5,100);
            g.fillRect(i*5,20,5,100);
            
            hilfsvar = h[min];
            h[min]=h[i];
            h[i]=hilfsvar; 
            //Arrays.sort(h);
            
            g.setColor(Color.black);
            g.fillRect(min*5,120-h[min],3,h[min]);
            g.fillRect(i*5,120-h[i],3,h[i]);
        }
        System.out.print(System.currentTimeMillis()-start);
    }

    public static void main (String [] args) {
        Minimum sprog = new Minimum();
        WindowListener wl = new WindowAdapter() {
                public void windowClosing(WindowEvent e) {
                    System.exit(0);
                }
            };
        sprog.addWindowListener(wl);
        sprog.setTitle("Sortieren durch Minimumsuche");
        sprog.setLocation(100,100);
        sprog.setSize(520,120);
        sprog.setVisible(true);
    }
}

Nach dem testen den Bubble-Sort-Code in Kommentaren schreiben und den Kommentar von Arrays.sort wegmachen.

Liebe Grüße
Reality

 

[bygones]

habs noch nicht ausprobiert - aber wenn du nur die kommentare bei Arrays.sort weglässt sortierst du n-mal !

in jedem schleifendurchlauf vertauschst du erst die Elemente und sortierst dann, in der nächsten schleife vertauschst du wieder und sortierst wieder den Array !!!

Arrays.sort muss nur einmal mit dem Array zum sortieren aufgerufen werden, du rufst es n-mal auf !!!!

Damit ist klar warum mit Arrays.sort es länger dauert

PS: Mein Code (ausm Kopf abgeschrieben)

public class Main {
  public static void main(String[] args) {
     List<Long> times = new ArrayList<Long>();
     
     boolean jreSort = false;    

    for(int i = 0; i < 10; i++) {
      double[] array = new double[100 * 100];
   
      for(int j = 0; j < array.length; j++) {
        array[j] = Math.random() * 5;
      }
  
       long time = System.currentMillis(); // oder so - weiß grad net wie die methode heißt

      if(jreSort) {
        Arrays.sort(array);
      }
      else {
        bubbleSort(array);
      }
   
      time = System.currentMillis() - time;
      times.add(new Long(time));

      // zeitausgaben
    }


     public static void bubbleSort(double[] array) {
        for(int i = 0; i < array.length; i++) {
          for(int j = i+1; j< array.length; j++) {
              if(array[j] < array[i]) {
                 double tmp = array[i];
                 array[i] = array[j];
                 array[j] = tmp;
              }
          }
        }
      }
}

 

[Reality]

OK, danke.

 

[Gast]

wie kann ich sortieralgorithmen wie zum beispiel quicksort einfach schreiben

 

[bygones]

wie kann ich sortieralgorithmen wie zum beispiel quicksort einfach schreiben

in dem du dir den Pseudocode der Algorithmen anschaust und dann implementierst...
man hätte auch antworten können: mit einem Computer...

 

[mic_checker]

Btw. intern werden doch modifizierte Versionen von Merge Sort und Quicksort verwendet oder (also von Arrays.sort) ? Abhängig davon welche sort Methode man aufruft, natürlich.

 

[bygones]

afaik sind alle sort methoden von Arrays modifizierte MergeSorts !