Quicksort

[Daniel22]

Hallo Leute!

Der Algorithmus macht das was er soll aber in einer höheren Zeitkomplexität!
Ich gehe zwei verschachtelte Schleifen durch n * n -> O(n^2). Dann
sortiere ich: Arrays.sort das heißt, dass der erste Teil eine zu hohe Zeitkomplexität
hat! (er sollte eine Zeitkomplexität von O(n log n) haben) Es bietet sich wahrscheinlich an, erst Sortierungen durchzuführen
und dann gemeinsame Elemente zu suchen. Aber wie? Ne Idee?

int [] array1;
int [] array2;
Vector neu = new Vector();
for(int i=0; i<array1.length;i++)
{

          for(int j=0; j<array2.length;j++)
          {
                    if(array1[i] == array2[j])
                    {
                              neu.addElement(new Integer(array1[i]));
                    }     
          }

}

int [] finalArr = new int[neu.size()];

for(int i=0; i<neu.size();i++)
{
          finalArr[i] = Integer.parseInt(neu.get(i).toString());
}

Arrays.sort(finalArr);

Gruß
Daniel

 

[Timmah]

http://www.java-forum.org/de/viewtopic.php?t=33134

Warum eröffnest du einen neuen Thread?
Das, was ich dir in dem Thread als Code geliefert habe, hat mit dem Quicksort nichts zu tun... ???:L ???:L ???:L

 

[Daniel22]

Richitg Timmah!

Aber die Zeitkomplexität ist flasch und das ist eben das enscheidene. Ich muss erst Sortierungen durchzuführen
und dann gemeinsame Elemente zu suchen. Und das machen wir nicht mit unserem code Timmah.

Gruß
Daniel

 

[bygones]

bitte diskutiert im anderen thread weiter - wird sonst zu unübersichtlich