Frage zu QuickSort

AlexD

Aktives Mitglied
Hallo zusammen,

ich hab folgendes Problem!


Ich muss eine Liste mit QuickSort sortieren. Die Liste die Ich anlege wird sortiert bis zu 5 Elementen, sobald ich ein 6 Element hinzufüge hängt sich der Quicksort auf :noe:

vielleicht kann mir da jemand nen Tipp geben was ich da noch ändern kann.


Code:

Java:
public class ListeAlgo {

	public static <T> void quickSort(Liste<T> liste, java.util.Comparator<T> comp){
        System.out.println("bin in erster Methode");
		quickSort(liste,comp,0,liste.size());
        
}
 
public static <T> void quickSort(Liste<T>liste, java.util.Comparator<T> comp, int il, int ir){
       System.out.println("bin in zweiter methode");
        if((ir-il)<=1){
                return;
         }
       
        System.out.println("bin vor ipiv");
        int ipiv=(il+ir)/2;
     
        T pivot= liste.get(ipiv);
       System.out.println("bin nach zuweisung T pivot");
       
        liste.swap(ipiv, ir-1);
       
        int l=il;
        int r=ir-2;
        
       
        do{
        
                while(comp.compare(liste.get(l),pivot)<0){
                        l++;}
                
                
                while(l<r&&comp.compare(liste.get(r), pivot)>0){
                r--;}
                
        }while(l<r);
        
        ipiv= l;
        liste.swap(ipiv,ir-1);
        quickSort(liste,comp, il,ipiv);
        quickSort(liste,comp, ipiv+1,ir);
       
       
}
	public static void main(String[] args) {
		AbstractListe<Integer> ws = new DVLListe<Integer>();
		IntegerComp com = new IntegerComp();
		
		ws.add(0,5);
		ws.add(1,2);
		ws.add(2,1);
		ws.add(3,4);
		ws.add(4,3);
		//ws.add(5,6);
	
		
		
		
		quickSort(ws,com);
		
		while(!ws.isEmpty()){
			System.out.print(ws.getFirst()+", ");
			ws.removeFirst();
			
		}
		
		
	}

}
 

malihini

Mitglied
eine Möglichkeit den Quicksort zu realisieren,
Ich hoffe, das hilft Dir.

Java:
	static void tausche(int[] array, int i1, int i2){
		int h = array[i1];
		array[i1] = array[i2];
		array[i2] = h;
	}
	
	static int part(int[] array, int u, int o, int p){ //Hilfsmethode
		int pn = u; int pv = array[p];
		tausche(array, p, o); //ans Ende verschieben
		for(int i = u; i < o; i++){
			if(array[i] <= pv){
				tausche(array, pn++, i);
			}
		}
		tausche(array, o, pn);
		return pn;
	}
	
	static void qsort(int[] array, int u, int o){
		int p = (u+o)/2;	//Pivotelement bestimmen
		if(u > o){
			int pn = part(array, u, o, p);
			qsort(array, u, pn-1);	// rekursives sortieren der Partitionen
			qsort(array, pn+1, o);
		}
	}
	
	static void quickSort(int array[]){
		qsort(array, 0, array.length);
	}
 

AlexD

Aktives Mitglied
Vielen Dank, leider hilft mir das nicht! ich muss das ganze mit einer Liste hinbekommen.

Mit einem Array kann ich das leider nicht gebrauchen.

Aber trotzdem Danke für die Mühe!
 

!GH!Budd

Mitglied
Wie ist denn die Fehlermeldung? Nullpointer Exception?

Eventuell liegt der Fehler hier: int ipiv=(il+ir)/2; Könnte ein Problem sein, wenn eine ungerade Anzahl drin ist. Probier mal mit noch nem Element mehr. Ansonsten hilft dir das mit dem Array ja vielleicht auch doch, wenn du deinen Algorithmus analog dazu aufbaust. Du arbeitest ja auch mit vertauschen.

Viel Erfolg!
 

malihini

Mitglied
Eigentlich brauchst Du doch nur die array durch Deine List ersetzen?
Und warum übergibst Du "ws.add(0,5) oder ws.add(1,2)"? Der erste Eintrag ist der Index? Das könntest Du Dir dann sparen, da ja jedes Listenelement über den Index angesprochen wird. Also z.B. ws.get(0) gibt Dir die 5 zurück. Vielleicht sehe ich das aber auch falsch.
 

AlexD

Aktives Mitglied
@ !GH!Budd : nein es fliegt keine NullPointer, das Programm hängt in einer EndlosSchleife fest.

@ malihini : Das hab ich ja eigentlich auch gemacht, nur leider geht es halt nur mit Listen bis zu 5 Elementen. Ab 6 geht es dann nicht mehr.

ws.add ( index, value)

Das ist in der Liste so implementiert.

Die DVLListe sieht so aus.


[Java]
import java.util.Collection;


public class DVLListe<T> extends AbstractListe<T> {
private class Item {
public Item prev;
public Item next;
public T value;
}

private Item first;
private Item last;
private int size;

public boolean isEmpty() {
return first == null;
}

private Item getItem(int pos) {
Item current = first;
for (int i = 0; i < pos; ++i) {
current = current.next;
}
return current;
}

public void add(int pos, T e) {
Item item = new Item();
item.value = e;
item.next = getItem(pos);

if (item.next == null) {
item.prev = last;
last = item;
}
else {
item.prev = item.next.prev;
item.next.prev = item;
}
if (item.prev == null) {
first = item;
}
else {
item.prev.next = item;
}

++size;
}

private T removeItem(Item item) {
if (item.prev == null) {
first = item.next;
}
else {
item.prev.next = item.next;
}
if (item.next == null) {
last = item.prev;
}
else {
item.next.prev = item.prev;
}
return item.value;
}

public T remove(int pos) {
if (isEmpty()) {
throw new java.util.NoSuchElementException();
}
--size;
return removeItem(getItem(pos));
}

public class Iterator implements java.util.Iterator<T> {
private Item current;

public Iterator() {
current = first;
}
public Iterator(int pos) {
current = getItem(pos);
}
public boolean hasNext() {
return current != null;
}
public T next() {
if (!hasNext()) {
throw new java.util.NoSuchElementException();
}
T e = current.value;
current = current.next;
return e;
}
public void remove() {
if (isEmpty() || current == first) {
throw new java.util.NoSuchElementException();
}
removeItem(current == null ? last : current.prev);
--size;
}
}

public Iterator iterator() {
return new Iterator();
}

public Iterator iterator(int pos) {
return new Iterator(pos);
}

@Override
public T get(int pos) {
if(isEmpty()){
throw new java.util.NoSuchElementException();

}
return getItem(pos).value;
}

@Override
public T set(int pos, T e) {
if(getItem(pos) == null){
throw new java.util.NoSuchElementException();

}
Item item = getItem(pos);
T e1 = item.value;
item.value = e;


return e1;
}

@Override
public int size() {

return size;
}

@Override
public void addFirst(T e) {
add(0,e);

}

@Override
public void addLast(T e) {
add(size(),e);

}

@Override
public T removeFirst() {
if(isEmpty()){
throw new java.util.NoSuchElementException();
}
T e = remove(0);

return e;
}

@Override
public T removeLast() {
if(isEmpty()){
throw new java.util.NoSuchElementException();
}
T e = remove(size()-1);

return e;
}

@Override
public T getFirst() {
if(isEmpty()){
throw new java.util.NoSuchElementException();
}
return getItem(0).value;
}

@Override
public T getLast() {
if(isEmpty()){
throw new java.util.NoSuchElementException();
}
return getItem(size()-1).value;
}

@Override
public T setFirst(T e) {
if(isEmpty()){
throw new java.util.NoSuchElementException();
}

Item item = getItem(0);
T e1 = item.value;
item.value = e;

return e1;
}

@Override
public T setLast(T e) {
if(isEmpty()){
throw new java.util.NoSuchElementException();
}

Item item = getItem(size()-1);
T e1 = item.value;
item.value = e;
return e1;
}

@Override
public boolean add(T e) {
// TODO Auto-generated method stub
return false;
}

@Override
public boolean contains(Object o) {
// TODO Auto-generated method stub
return false;
}

@Override
public java.util.Iterator<T> descendingIterator() {
// TODO Auto-generated method stub
return null;
}

@Override
public T element() {
// TODO Auto-generated method stub
return null;
}

@Override
public boolean offer(T e) {
// TODO Auto-generated method stub
return false;
}

@Override
public boolean offerFirst(T e) {
// TODO Auto-generated method stub
return false;
}

@Override
public boolean offerLast(T e) {
// TODO Auto-generated method stub
return false;
}

@Override
public T peek() {
// TODO Auto-generated method stub
return null;
}

@Override
public T peekFirst() {
// TODO Auto-generated method stub
return null;
}

@Override
public T peekLast() {
// TODO Auto-generated method stub
return null;
}

@Override
public T poll() {
// TODO Auto-generated method stub
return null;
}

@Override
public T pollFirst() {
// TODO Auto-generated method stub
return null;
}

@Override
public T pollLast() {
// TODO Auto-generated method stub
return null;
}

@Override
public T pop() {
// TODO Auto-generated method stub
return null;
}

@Override
public void push(T e) {
// TODO Auto-generated method stub

}

@Override
public T remove() {
// TODO Auto-generated method stub
return null;
}

@Override
public boolean remove(Object o) {
// TODO Auto-generated method stub
return false;
}

@Override
public boolean removeFirstOccurrence(Object o) {
// TODO Auto-generated method stub
return false;
}

@Override
public boolean removeLastOccurrence(Object o) {
// TODO Auto-generated method stub
return false;
}

@Override
public boolean addAll(Collection<? extends T> c) {
// TODO Auto-generated method stub
return false;
}

@Override
public void clear() {
// TODO Auto-generated method stub

}

@Override
public boolean containsAll(Collection<?> c) {
// TODO Auto-generated method stub
return false;
}

@Override
public boolean removeAll(Collection<?> c) {
// TODO Auto-generated method stub
return false;
}

@Override
public boolean retainAll(Collection<?> c) {
// TODO Auto-generated method stub
return false;
}

@Override
public Object[] toArray() {
// TODO Auto-generated method stub
return null;
}

@Override
public <T> T[] toArray(T[] a) {
// TODO Auto-generated method stub
return null;
}
}


[/Java]
 

AlexD

Aktives Mitglied
Was ich jetzt rausgefunden habe!

an dieser Stelle

[Java]

do{

while(comp.compare(liste.get(l),pivot)<0){
l++;}

while(l<r&&comp.compare(liste.get(r), pivot)>0){
r--;}

}while(l<r);
[/Java]

wird bei mehr als 5 Elementen weder l inkrementiert noch r dekrementiert :/
 

AlexD

Aktives Mitglied
Klar, sorry


es fehlte eine If Abfrage!

[Java]

do{

while(comp.compare(liste.get(l),pivot) < 0){
l++ ;}


while(l < r && comp.compare(liste.get(r), pivot) > 0){
r-- ;}
if(l < r){
liste.swap(l++, r);
}
}while(l < r);

[/Java]
 
Zuletzt bearbeitet:
Ähnliche Java Themen
  Titel Forum Antworten Datum
K Eine Frage zum Quicksort Java Basics - Anfänger-Themen 11
G Frage zu Quicksort Java Basics - Anfänger-Themen 18
J QuickSort - kurze Frage Java Basics - Anfänger-Themen 9
Zrebna Frage zu Test-Driven Development (TDD) Java Basics - Anfänger-Themen 3
I Frage Thymeleaf -> Fehler ignorieren und mit "" ersetzen? Java Basics - Anfänger-Themen 15
I Frage Thymeleaf -> Prefix / Suffix ändern? Java Basics - Anfänger-Themen 11
D Rekursions Probleme / frage Java Basics - Anfänger-Themen 4
T Frage zu Parse Java Basics - Anfänger-Themen 2
H Frage an die Profis Java Basics - Anfänger-Themen 4
J Eine konzeptionelle Frage zu OOP Java Basics - Anfänger-Themen 3
P Frage zu Rekursion und Backtracking Java Basics - Anfänger-Themen 2
H Frage zur Ausgabe Java Basics - Anfänger-Themen 4
H Frage zu arithmetischen Operationen Java Basics - Anfänger-Themen 20
F Kurze Frage zu replace() Java Basics - Anfänger-Themen 19
JavaSchmecktLecker Polymorphie Frage zur Methodenüberschreibung Java Basics - Anfänger-Themen 21
J Frage zu einem "Taschenrechner" code Java Basics - Anfänger-Themen 9
B Erste Schritte Frage zu Instanzierung und Referenzen Java Basics - Anfänger-Themen 8
DoubleM Runtime.getRuntime().exec Frage Java Basics - Anfänger-Themen 2
J Eine theoretische Frage zur Praxis - JPanel oder Canvas Java Basics - Anfänger-Themen 5
O Frage: Formaler Typbezeichner? Java Basics - Anfänger-Themen 3
I BlueJ Queue Frage für Klausur Java Basics - Anfänger-Themen 2
N Verständnis Frage zu Variablen Java Basics - Anfänger-Themen 3
N Spezielle frage zum Comparator Java Basics - Anfänger-Themen 6
L Frage zum Array Java Basics - Anfänger-Themen 1
A Frage zum UML Design Java Basics - Anfänger-Themen 1
I Hilfe bei Klausur Frage Java Basics - Anfänger-Themen 8
izoards Drucken Frage zu FAQ Beitrag Java Basics - Anfänger-Themen 2
J Frage zu meinem Code (OOP) Java Basics - Anfänger-Themen 4
sserio Split() -> Regex Frage. Java Basics - Anfänger-Themen 7
A OCA Study Guide: 2. Frage aus Kapitel 3 Java Basics - Anfänger-Themen 9
sserio Date Library Frage Java Basics - Anfänger-Themen 9
Max246Sch Frage zu Währungsrechner Code Java Basics - Anfänger-Themen 2
sserio Frage zu HashMaps Java Basics - Anfänger-Themen 20
sserio Frage zu Threading - Multithreading Java Basics - Anfänger-Themen 2
sserio Frage zu Lambda Ausdrücken Java Basics - Anfänger-Themen 7
sserio Frage zu BigInteger Java Basics - Anfänger-Themen 1
D Frage bzgl. Enum-Handhabung Java Basics - Anfänger-Themen 16
xxx12 Frage Java Basics - Anfänger-Themen 2
I Generelle Frage zu Mikroservices (Spring Boot?), Docker... Java Basics - Anfänger-Themen 7
R Frage zu Methoden (Rückgabewert u. ohne.) Java Basics - Anfänger-Themen 2
A Frage zur programmierung Java Basics - Anfänger-Themen 12
M Frage zur Methode split der Klasse String Java Basics - Anfänger-Themen 32
R Input/Output Frage zu Java IO Java Basics - Anfänger-Themen 6
M Frage zu printWriter Java Basics - Anfänger-Themen 5
C Frage zu OLSMultipleLinearRegression Java Basics - Anfänger-Themen 31
KogoroMori21 Frage zum Euklidischen Algorithmus Java Basics - Anfänger-Themen 11
S Verständnis-Frage zu einer HÜ? Java Basics - Anfänger-Themen 1
F Frage betreff Programm mit dem man C++-Code in JAVA-Code übersetzen lassen kann Java Basics - Anfänger-Themen 2
L Frage zur Ticket Maschine Java Basics - Anfänger-Themen 1
J Frage zu OOP-Klassendiagramm Java Basics - Anfänger-Themen 8
OSchriever Frage zu Compiler Java Basics - Anfänger-Themen 8
H Frage zu Throw Exception Java Basics - Anfänger-Themen 2
TimoN11 Frage zu Java-Vererbung (Cast) Java Basics - Anfänger-Themen 5
Bademeister007 Hallo Leute ich hab eine Frage zur ArrayList Java Basics - Anfänger-Themen 8
F Frage betreff Programmierbücher zu Lagerverwaltung als Konsolenprogramm Java Basics - Anfänger-Themen 3
dieter000 Kurze Frage kann mir ejmand kurz diesen Code erklären, bzw wie man die zeilen erklärt und so Java Basics - Anfänger-Themen 1
I String.split regex Frage Java Basics - Anfänger-Themen 2
N Best Practice Frage zum MVC-Pattern Java Basics - Anfänger-Themen 2
dieter000 Frage zu einem Beispiel... Java Basics - Anfänger-Themen 5
J Frage zum Loggen Java Basics - Anfänger-Themen 18
J Methoden Frage: Array-Werte in anderer Methode ändern Java Basics - Anfänger-Themen 4
Zrebna Frage zum "Referenzen-konzept" in Java Java Basics - Anfänger-Themen 8
JD_1998 Array-Position aus einer Methode in einer anderen ausgeben (Kurze Frage) Java Basics - Anfänger-Themen 2
marcooooo Frage zu bestimmten Beispiel Java Basics - Anfänger-Themen 31
NeoLexx equals()-Methode Verständnis Frage anhand Code Beispiel Java Basics - Anfänger-Themen 22
N Input/Output Eine Frage über system.out.println. Java Basics - Anfänger-Themen 10
B Erste Schritte Learning Coding (!) Frage an erfahrene Programmierer. Java Basics - Anfänger-Themen 23
M konzeptuelle Frage: In welcher Klasse definiert man am Besten Methoden, die die Kommunikation mit dem User regeln? Java Basics - Anfänger-Themen 8
B Frage zum Code verständnis im Resultat Java Basics - Anfänger-Themen 10
C Exception-Frage Java Basics - Anfänger-Themen 3
J Eine Frage zur Schreibweise == ? : Java Basics - Anfänger-Themen 3
S Frage des Designs Java Basics - Anfänger-Themen 1
JavaTalksToMe Extends/Implements Frage Java Basics - Anfänger-Themen 3
pkm Frage zu Servletfunktion Java Basics - Anfänger-Themen 0
B Frage zur Währungsumrechnung Java Basics - Anfänger-Themen 3
S Allgemeine Frage über Generics und Vererbungen Java Basics - Anfänger-Themen 5
Kirby.exe Frage zur Verwendung von Interfaces Java Basics - Anfänger-Themen 6
D Frage zu Strings einer Exception Java Basics - Anfänger-Themen 4
L Wie frage ich ab, ob in einem Array, Werte doppelt vorkommen? Java Basics - Anfänger-Themen 4
D Frage zur IDE IntelliJ IDEA Java Basics - Anfänger-Themen 6
H Frage zum 2d Array Java Basics - Anfänger-Themen 1
N Frage zum Newton-Fraktal Java Basics - Anfänger-Themen 1
H Frage zu interfaces Java Basics - Anfänger-Themen 1
J Frage dazu Variablen klassenübergreifend zu verändern Java Basics - Anfänger-Themen 22
I Frage zu SkipList Java Basics - Anfänger-Themen 4
G Frage zu JScrollPane Java Basics - Anfänger-Themen 12
Kirby.exe Allgemeine Frage Java Basics - Anfänger-Themen 3
W Frage zu anonymen Klassen Java Basics - Anfänger-Themen 4
J Kleine Frage zu OOP Java Basics - Anfänger-Themen 371
S Frage Klasse und Objekte Java Basics - Anfänger-Themen 2
F Frage zu Iteratoren Java Basics - Anfänger-Themen 2
C Erste Schritte Frage zur ArrayList Java Basics - Anfänger-Themen 15
J Frage zur Vererbung Java Basics - Anfänger-Themen 1
H Frage zur ermittlung eines doppelte Paars aus Sotieralgorithmus Java Basics - Anfänger-Themen 4
H Frage zum Array Java Basics - Anfänger-Themen 17
G Schach -Frage 2- Maussteuerung Java Basics - Anfänger-Themen 7
G Schach in Java - Allgemeine Frage zur Architektur Java Basics - Anfänger-Themen 7
B Fachliche Frage bei Rechnungen Java Basics - Anfänger-Themen 16
B Frage zu: String... strings -> Ungleiche Anzahl an Parameter? Java Basics - Anfänger-Themen 4
B Frage zu Datenbank Design - Rechnungen, Angebote... und deren Positionen Java Basics - Anfänger-Themen 4

Ähnliche Java Themen

Neue Themen


Oben