Hackerboard WikiHaboBlog

[HaBo]

 
Code Kitchen Allgemeines Coder-Forum rund um das Programmieren eigenständiger, ausführbarer Programme.

[JAVA] quicksort sortiert nicht komplett

Diskussion: [JAVA] quicksort sortiert nicht komplett im Forum Code Kitchen, in der Kategorie Software Home; Hallo ich habe ein kleines großes Problem: Ich habe einen Quicksort-Algo, der zwar manchmal richtig sortiert, aber eben manchmal eine ...
Antwort
Themen-Optionen Ansicht
   
Alt 03.06.08, 16:47   #1 (permalink)
 
Registriert seit: 31.03.08
MrSpider Leistung: Facit NTK
Likes: 0
Standard [JAVA] quicksort sortiert nicht komplett


Hallo ich habe ein kleines großes Problem:
Ich habe einen Quicksort-Algo, der zwar manchmal richtig sortiert, aber eben manchmal eine Zahl nicht an der richtigen Stellle ist.

Hier mal der Code....

Quicksort   

Code:
package aufgabe3;

import java.util.Arrays;


public class Sort {
	
	private static void sort(int a[], int low0, int high0) {
		int low = low0;
		int high = high0;
		if (high-low < 1) {
			return;
		}// if
		int mid = pickPivot(a);
		
		while (low < high) {
			while (low < high && a[low] < mid) {
				low++;
			}// while
			while (low < high && a[high] >= mid) {
				high--;
			}// while
			if (low < high) {
				int temp = a[low];
				a[low] = a[high];
				a[high] = temp;
			}// if
		}// while
		if (high < low) {
			int temp = high;
			high = low;
			low = temp;
		}// if
		sort(a, low0, low);
		sort(a, (low == low0) ? (low + 1) : low, high0);
	}// sort
	
	public static void sort(int a[]) {
		sort(a, 0, a.length - 1);
	}// sort
	
	private static int pickPivot(int[] a) {
		int[] p = new int[3];
		p[0] = a[(int) (Math.random() * a.length)];
		p[1] = a[(int) (Math.random() * a.length)];
		p[2] = a[(int) (Math.random() * a.length)];
		
		bubbleSort(p);
		return p[1];
	}// pickPivot
	
	private static void bubbleSort(int[] a) {
		for (int i = 0; i < a.length - 1; i++) {
			for (int j = 1; j < a.length; j++) {
				if (a[j-1] > a[j]) {
					int temp = a[j-1];
					a[j-1] = a[j];
					a[j] = temp;
				}// if
			}// for j
		}// for i
	}// bubbleSort
	

	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int[] a = {78975,7798,46,77,1,2};
		sort(a);
		System.out.println(Arrays.toString(a));
	}// main
	
}// class


Ich wäre euch sehr dankbar, wenn ihr mir weiterhelfen könntet.
MrSpider

EDIT:
Ich hab den Algo von hier:
Quicksort-Algo
MrSpider ist offline   Mit Zitat antworten
Alt 03.06.08, 17:15   #2 (permalink)
Senior Member
 
Benutzerbild von sw33tlull4by
 
Registriert seit: 12.06.07
sw33tlull4by Leistung: Facit NTK
Likes: 0
Standard
Du machst da einiges falsch:
1.
Bubblesort hat hier nichts zu suchen, wenndu das Pivotelement an die vorderste stelle bringen willst , dann tausche einfach a[low] mit pivot.
du waehlst ueberigens das pivotelement zufaellig aus dem ganzen feld aus, und nicht aus dem aktuellen Feld segment, deswegen sortiert er wahrscheinlich manchmal nicht richtig.
random ist bei Sortieralgorithmen immer boese.
2.
lauf doch erst mit der Zahl low weiter und erst wenn du eine zahl groesser dem Pivotelement findest bewegst du high.
wenn high und low sich kreuzen dann muss das Pivotelement an die stelle a[high]
high und low brauchst du auch nicht ueber eine swapfunktion sichern.
du sagst dann einfach
low = 0 und high = high -1
und
low = low
und high =laenge des neuen Feldsegmentes.
mfg

sw33t
__________________
Nur die Schwachen klammern sich an die Moral.

Kill my daemons and my angels will follow them.
sw33tlull4by ist offline   Mit Zitat antworten
   
HaBOT
 

Werbung ist gerade online    
Alt 03.06.08, 18:21   #3 (permalink)
Senior Member
 
Benutzerbild von t3rr0r.bYt3
 
Registriert seit: 07.01.03
t3rr0r.bYt3 Leistung: Z3
Likes: 13
Standard
Jetzt kommt mal wieder ein Post ganz nach meinem Geschmack.

Erstens: Der Korinthenkacker.
Zitat:
random ist bei Sortieralgorithmen immer boese.
Mit der (pseudo)zufälligen Wahl des Pivot-Elements (aus der unsortierten Restfolge natürlich..) kann man dem Laufzeitproblem entgegenwirken, das man hat, wenn die Folge bereits verkehrt sortiert ist (O(n?)). Natürlich ist das nur eine statistische Korrektur, eine Garantie hat man nicht.

Zweitens: Off-Topic / Schleichwerbung
Ich halte das für eine gute Gelegenheit, dich zu funktionaler Programmierung zu bewegen. Vergleiche mal deinen Java-Code mit diesem Haskell-Code hier:
Code:
qsort :: Ord a => [a] -> [a]
qsort []       = []
qsort (x:xs) = qsort [y | y <- xs, y < x] ++ [x] ++ qsort [y | y <- xs, y >= x]
Quelle: http://de.wikipedia.org/wiki/Haskell...che)#QuickSort
t3rr0r.bYt3 ist offline   Mit Zitat antworten
Alt 03.06.08, 20:38   #4 (permalink)
 
Benutzerbild von _fux_
 
Registriert seit: 13.09.05
_fux_ Leistung: Abacus
Likes: 5
Standard
hier mal ein fertiger Quicksort in C++, vielleicht hilft dir's ja! die logik sollte ja ähnlich sein:

Code:
template <typename Type>
void quick_sort(vector<Type> &a);

template <typename Type>
void quick_sort(vector<Type> &a, int left, int right);

template <typename Type>
const Type & median3(vector<Type> &a, int left, int right);


/***************************************************/
/***************************************************/
/**********          QUICKSORT        **************/
/***************************************************/
/***************************************************/

template <typename Type>
void quick_sort(vector<Type> &a)
{
	// Starten des Quicksort-Algorithmus
	quick_sort(a, 0, (int) a.size()-1);
}

template <typename Type>
const Type & median3(vector<Type> &a, int left, int right)
{  // Median von 3 Werten berechnen
	int center = (left + right) / 2;

	if (a[center] < a[left])
		// STL-Funktion zum Vertauschen von Feldelementen
		swap(a[left], a[center]);  
	if (a[right] < a[left])
		swap(a[left], a[right]);
	if (a[right] < a[center])
		swap(a[center], a[right]);
	// Pivotelement zurückgeben
	return a[center];
}

template <typename Type>
void quick_sort(vector<Type> &a, int left, int right)
{
	int center = (left+right)/2;

	//_AUSGABE	cout << endl << "Quicksort: " << "(" << "a" << "," << left << "," << right << ")" << endl << endl;

	if (left < right)
	{
		Type pivot;
		if (right-left > 10)
		{   pivot = median3(a, left, right); }
		else
		{   pivot = a[center]; } 
		int i = left;
		int j = right;

		//_AUSGABE		cout << "pivot = a[" << center << "]" << " = " << a[center] << " " << endl;
		// AUSGABE

		//_AUSGABE		for(unsigned int i=0;i<a.size();i++){
		//_AUSGABE			cout << a.at(i) << " ";
		//_AUSGABE		}
		//_AUSGABE		cout << endl;

		while(i < j)
		{
			// hier nur 1 Vergleich und 1x in-/dekrementieren
			while(a[i] < pivot) {i = i+1;}
			while(pivot < a[j]) {j = j-1;}
			if (i < j)
				swap(a[i], a[j]);
		}

		// AUSGABE
		//_AUSGABE		for(unsigned int i=0;i<a.size();i++){
		//_AUSGABE			cout << a.at(i) << " ";
		//_AUSGABE		}

		// Rekursive Quicksort-Aufrufe: a[i] ist Pivotelement
		// Sortiere Teilmenge mit kleineren Elementen
		quick_sort(a, left, i-1); 
		// Sortiere Teilmenge mit größeren Elementen
		quick_sort(a, i+1, right); 
	}
}
__________________
und?
_fux_ ist offline   Mit Zitat antworten
Alt 03.06.08, 20:46   #5 (permalink)
Moderator
 
Benutzerbild von lightsaver
 
Registriert seit: 19.06.06
lightsaver Leistung: Pentium Ilightsaver Leistung: Pentium Ilightsaver Leistung: Pentium I
Likes: 42
Standard
da muss ich t3rr0r.bYt3 recht geben, random ist bei verschiedenen sortieralgorithmen nicht nur nicht eine schlechte idee sondern sogar eine gute. gerade beim quicksort mit nicht absolut zufälligen folgen kann man da doch erheblich schneller werden.

bubblesort kann übrigens auch eine gute idee sein. gut, in der uni haben wir insertsort gewählt aber das ist jetzt mal egal. der grund ist der große aufwand bei kurzen listen, da kannst du mit anderen sortieralgorithmen auch noch einiges rausholen. du musst nur die grenze finden, ab der sich dann quicksort lohnt.
wir mussten das ganze in höhere algorithmen analysieren, was keinen spaß gemacht hat, aber da konnte man ganz gut sehen, dass (natürlich bei sehr großen listen) solche optimierungen einen erheblichen vorteil bringen können.

es stimmt aber auch, dass bubblesort hier seltsam angewendet wird und ich auch noch nicht so ganz verstanden habe, wieso 3 elemente gewählt werden und davon dann eines genommen wird. mittels random sollte ja schon das zufallsprinzip erfüllt sein.
lightsaver ist offline   Mit Zitat antworten
Alt 03.06.08, 21:25   #6 (permalink)
Senior Member
 
Benutzerbild von sw33tlull4by
 
Registriert seit: 12.06.07
sw33tlull4by Leistung: Facit NTK
Likes: 0
Standard
Naja,den
Meridian verwenden denke ich, aber ich bleibe trotzdem bei meiner meinung
das man Random nicht verwenen sollte.
Zugegeben. auf speziellen listen, z.b. solche fuer welche QS pessimale Laufzeiten zeigt, ist das evtl ein Vorteil, aber das ist nichts, was man nicht z.b. mit einer Wahlstrategie fuer den Meridian erreichen koennte.
Darueber hinaus ist Random unberechenbar und wiso sollte ich bubblesort anwenden wenn ich nur das Pivotelement nach vorne bringen soll, das Feld was ich mit BubbleSort umgrabe wird doch sowiso durch QS komplett neu geordnet.
Aber egal, ist nur uebung und jeder baut code anders.
Viele Wege fuehren nach ROM.
BTW:
Das Algorithmenwiki ist aber sehr schon->Bookmark.
mfg

sw33t

P.s.:schon ausprobiert ob es daran lag das du random auf das gesamte Feld und nicht nur auf das Feldsegment angewandt hast?
Nur so, eine rekursive Variante frisst zwar speicher wie verrueckt ist aber leichter zu implementieren und zu verstehen als eine iterative, zur Not also mal rekursiv Programmieren und das ganze dann zur iterativen Variante umbauen.
__________________
Nur die Schwachen klammern sich an die Moral.

Kill my daemons and my angels will follow them.
sw33tlull4by ist offline   Mit Zitat antworten
Alt 04.06.08, 12:46   #7 (permalink)
 
Benutzerbild von _fux_
 
Registriert seit: 13.09.05
_fux_ Leistung: Abacus
Likes: 5
Standard
ja der code ist auch nicht direkt von mir ;-)
ich bin eh mehr der iterative mensch, aber ich hatte noch keine lust gehabt selber so ein teil zu bauen

werde ich aber demnächst tun und dann die algo's soriteren und benchen (einfache zeitmessung) ^^
__________________
und?
_fux_ ist offline   Mit Zitat antworten
Alt 04.06.08, 16:36   #8 (permalink)
Themenstarter
 
Registriert seit: 31.03.08
MrSpider Leistung: Facit NTK
Likes: 0
Standard
Hallo,
erst einmal vielen Dank für die zahlreichen schnellen Antworten.
Ich werde jetzt nochmal die posts durchgehen und das eine oder andere auf mein Programm anwenden.

Wegen dem Random:
Es ist so das ich ein Schülerstudium mache und es eine best. Aufgabenstellun ist:
...Die tatsächliche Laufzeit von Quicksort hängt
stark von einer guten Wahl der Pivot-Elemente ab[...]. Wählen Sie aus dem aktuellen Bereich [start; end] drei Positionen pos1,
pos2 und pos3 zufällig aus. Das Pivot-Element ist dann der Median von a[pos1], a[pos2] und a[pos3]...

Edit:
Ich versteh das nicht....
Es funktioniert ja eigentl.,
aber es kommt immer wieder mal ein falsches Ergebniss raus(ca. jedes 30. Mal)
Hier der Code:
Titel   

Code:
package aufgabe3;

import java.util.Arrays;

public class CopyOfSort {
	
	private static void sort(int a[], int low0, int high0) {
		int low = low0;
		int high = high0;
		if (high - low < 1) {
			return;
		}// if
		int mid = pickPivot(a);
		
		while (low < high) {
			while (low < high && a[low] < mid) {
				low++;
			}// while
			while (low < high && a[high] > mid) {
				high--;
			}// while
			if (low < high) {
				int temp = a[low];
				a[low] = a[high];
				a[high] = temp;
			}// if
		}// while
		if (high < low) {
			int temp = high;
			high = low;
			low = temp;
		}// if
		sort(a, low0, low);
		sort(a, (low == low0) ? (low + 1) : low, high0); // der Fehler ist hier denk ich                     
                                                                                             // mal
	}// sort
	
	public static void sort(int a[]) {
		sort(a, 0, a.length - 1);
	}// sort
	
	private static int pickPivot(int[] a) {
		int[] p = new int[3];
		p[0] = a[(int) (Math.random() * a.length)];
		p[1] = a[(int) (Math.random() * a.length)];
		p[2] = a[(int) (Math.random() * a.length)];
		
		bubbleSort(p);
		return p[1];
	}// pickPivot
	
	private static void bubbleSort(int[] a) {
		for (int i = 0; i < a.length - 1; i++) {
			for (int j = 1; j < a.length; j++) {
				if (a[j - 1] > a[j]) {
					int temp = a[j - 1];
					a[j - 1] = a[j];
					a[j] = temp;
				}// if
			}// for j
		}// for i
	}// bubbleSort
	
	public static void main(String[] args) {
		int b = 0;
		for (int i = 0; i < 100000; i++) {
			// TODO Auto-generated method stub
			int[] a = { 78975, 7798, 46, 77, 1, 2 };
			sort(a);
			if(!Arrays.toString(a).equals("[1, 2, 46, 77, 7798, 78975]")) {
				b++;
			}
			// System.out.println(Arrays.toString(a));
			
		}
		System.out.println(b);
	}// main
	
}// class
MrSpider ist offline   Mit Zitat antworten
Antwort
   

Werbung ist gerade online    

[HaBo] » Software Home » Code Kitchen » [JAVA] quicksort sortiert nicht komplett
« Vorheriges Thema | Nächstes Thema »
Themen-Optionen
Ansicht
Linear-Darstellung Linear-Darstellung

Forumregeln
Es ist Ihnen nicht erlaubt, neue Themen zu verfassen.
Es ist Ihnen nicht erlaubt, auf Beiträge zu antworten.
Es ist Ihnen nicht erlaubt, Anhänge hochzuladen.
Es ist Ihnen nicht erlaubt, Ihre Beiträge zu bearbeiten.
BB-Code ist an.
Smileys sind an.
[IMG] Code ist an.
HTML-Code ist aus.
Trackbacks sind aus
Pingbacks sind aus
Refbacks sind aus

Ähnliche Themen
Thema Autor Forum Antworten Letzter Beitrag
InsertSort sortiert nicht komplett weau Code Kitchen 5 19.06.09 12:02
Internetseiten werden nicht komplett geladen schmitti81 Internet Allgemein 4 01.04.09 14:40
Quicksort Burgess Code Kitchen 6 11.03.09 19:24
Array nicht komplett ausgeben weau (Web-) Design und webbasierte Sprachen 7 20.03.08 19:55
google listet page nicht komplett psyhead (Web-) Design und webbasierte Sprachen 3 08.08.05 00:01

Alle Zeitangaben in WEZ +1. Es ist jetzt 10:20 Uhr.
vBulletin® v3.8.7, Copyright ©2000-2012, vBulletin Solutions, Inc.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61