Quicksort

Status
Nicht offen für weitere Antworten.

Merowinger

Mitglied
Hi ihr alle...

ich habe einen quicksort für mein jtable eingebaut und es läuft und läuft einfach nicht rund...

es handelt sich um ein filetable. das tableModel besitzt das attribut files und indexes. files und indexes sind beide vom typ "List". die reihenfolge der files ändert sich nie. über die indexes verwalte ich die zuordnung zw. files und angezeigter reihenfolge in der tabelle...

Code:
class XsFileTableSorter extends MouseAdapter implements TableModelListener  {

	List<Integer>  indexes = new ArrayList<Integer>();
	List<Integer> sortingColumns = new ArrayList<Integer>();
	List sortingDesc = new ArrayList();
	XsFileTable table;
	
	
	public XsFileTableSorter() {

	}
	
	public void mouseClicked(MouseEvent e) {
		TableColumnModel columnModel = table.getColumnModel();
	    int viewColumn = columnModel.getColumnIndexAtX(e.getX());
	    int sortColumn = table.convertColumnIndexToModel(viewColumn);
	    reallocateIndexes();
    
	    if (e.getClickCount() == 1 && sortColumn != -1) {
	        int shiftPressed = e.getModifiers()&InputEvent.SHIFT_MASK;

	        int sortedColumnIndex = sortingColumns.indexOf(sortColumn);
	        if(sortedColumnIndex == -1) {
		        if (shiftPressed == 0) {
		        	sortingColumns.clear();
		        	sortingDesc.clear();
		        }
	        	sortingColumns.add(sortColumn);
	        	sortingDesc.add(new Boolean(true));
	        } else {
		        if (shiftPressed == 0) {
		        	boolean tmp = !(Boolean) sortingDesc.get(sortedColumnIndex);
		        	sortingColumns.clear();
		        	sortingDesc.clear();
		        	sortingColumns.add(sortColumn);
		        	sortingDesc.add(tmp);		        	
		        } else {
		        	sortingDesc.set(sortedColumnIndex, (!(Boolean) sortingDesc.get(sortedColumnIndex)));
		        }
	        }
	        sortByColumns();
	    }
	}	
	
	public void tableChanged(TableModelEvent tableModelEvent) {
	    reallocateIndexes();
	    sortByColumns();
	    System.out.println("tableChanged");
	} 	
	
	public void setTable(JTable p_table) {
		table = (XsFileTable) p_table;
		reallocateIndexes();
	}
	
	public void sortByColumns() {
		for(int index=0;index<sortingColumns.size();index++) {
			quicksort((Integer) sortingColumns.get(index), (Boolean) sortingDesc.get(index), 0, this.indexes.size()-1);
		}

	}	
	
	public void reallocateIndexes() {
		int rowCount = table.getModel().getRowCount();

		this.indexes.clear();
		for (int row = 0; row < rowCount; row++) {
			this.indexes.add(row);
		}
	    ((FolderTableModel) table.getModel()).setIndexes(this.indexes);
	}

	private void quicksort(int column, boolean desc, int lo, int hi) {
	    int i = lo, j = hi;

	    while (i <= j) {
	    	if(desc)
	    		while (compareRowsByColumn(this.indexes.get(i), this.indexes.get((lo + hi) / 2), column) > 0) 
	    			i++;
	    	else
	    		while (compareRowsByColumn(this.indexes.get(i), this.indexes.get((lo + hi) / 2), column) < 0) 
	    			i++;
	    	if(desc)
	    		while (compareRowsByColumn(this.indexes.get(j), this.indexes.get((lo + hi) / 2), column) < 0)       
	    			j--;
	    	else
	    		while (compareRowsByColumn(this.indexes.get(j), this.indexes.get((lo + hi) / 2), column) > 0)       
	    			j--;
	    	//wenn i kleiner als j ist wird getauscht
	    	if (i <= j) {
		        swap(i, j);
		        i++;
		        j--;
	    	}
	    }
	    // Rekursion
	    if (lo < j)
	      quicksort(column, desc, lo, j);
	    if (i < hi)
	      quicksort(column, desc, i, hi);
	}
	
	public void swap(int i, int j) {
		int tmp = this.indexes.get(i);
		    this.indexes.set(i, this.indexes.get(j));
		    this.indexes.set(j, tmp);
		    ((FolderTableModel) table.getModel()).setIndexes(this.indexes);
	}
	  
	 public int compareRowsByColumn(int row1, int row2, int column) {
		Class type = table.getModel().getColumnClass(column);
		 TableModel data = table.getModel();

		Object o1 = data.getValueAt(row1, column);
		Object o2 = data.getValueAt(row2, column);

		if (o1 == null && o2 == null) {
		      return 0;
		} else if (o1 == null) { // Define null less than everything.
		     return -1;
		} else if (o2 == null) {
		      return 1;
		}

		if (type == String.class) {
		      String s1 = (String)data.getValueAt(row1, column);
		      String s2  = (String)data.getValueAt(row2, column);
		      int result = s1.compareTo(s2);
		      return result;
		}
        }

ich kann leider nicht genau sagen wo der fehler liegt...es ist mir aber allerdings aufgefallen, dass wenn die sortierung von z -> a vorliegt der untere teil (also der bei der ersten aufteilung im quicksort) stimmt. der obere teil stimmt eigentlich auch, nur ist der in die andere richtung sortiert...

d.h. bei einer liste 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
würde bei mir quasi folgendes rauskommen wenn ich absteigend sortiere:
6, 7, 8, 9, 10, 5, 4, 3, 2, 1
es kann eigentlich nur eine kleinigkeit sein...aber ich finds nicht...sitze wohl schon zu lange davor


lg dennis
 

Merowinger

Mitglied
Ah, also es liegt wohl an der rekursion. es wird nur immer die erste ausgeführt, es stimmt also nicht, was ich zuvor geschrieben habe es muss heißen:
10, 9, 8, 7, 6, 1, 2, 3, 4, 5

wenn man die erste
Code:
if(i<hi) {
quicksort(column, desc, i, hi);
weglässt wird nämlich der untere teil sortiert und das ergebniss wäre
6, 7, 8, 9, 10, 5, 4, 3, 2, 1
 
S

SlaterB

Gast
mit deiner Vermischung mit dem unbekannten TableModel und sonstigen eigenen Klassen tust du dir keinen Gefallen,
so kann das niemand testen,

programmiere erstmal Quicksort für eine einfache Liste oder ähnliches,
wenn das funktioniert, dann kann man das vielleicht übertragen
 

JavaFred

Aktives Mitglied
Sehe ich das richtig, dass Du erst einen kompletten Quicksort anhand der ersten Sortierspalte machst, dann über die zweite etc.? Falls gewisse Kriterien gleich sind kann das so nicht funktionieren, weil Quicksort nicht stabil ist.
 
Status
Nicht offen für weitere Antworten.
Ähnliche Java Themen
  Titel Forum Antworten Datum
I Java Quicksort PAP Java Basics - Anfänger-Themen 2
B Quicksort in Verbindung mit einem Projekt Java Basics - Anfänger-Themen 1
M QuickSort und Liste Java Basics - Anfänger-Themen 6
S Laufzeit Quicksort wenn alle Elemente gleich sind Java Basics - Anfänger-Themen 4
G Quicksort Algorithmus Java Basics - Anfänger-Themen 12
Hanschyo Quicksort sortiert von groß nach klein Java Basics - Anfänger-Themen 3
R Quicksort mit Interface Comparable Java Basics - Anfänger-Themen 6
L Quicksort verstehen Java Basics - Anfänger-Themen 3
M Quicksort Laufzeit langsam Java Basics - Anfänger-Themen 5
M Quicksort Laufzeit langsam Java Basics - Anfänger-Themen 0
J Quicksort mit Stack Java Basics - Anfänger-Themen 4
Liondary Quicksort Java Basics - Anfänger-Themen 20
K Quicksort Fehler in der Implementierung Java Basics - Anfänger-Themen 2
S Quicksort Algorithmus Java Basics - Anfänger-Themen 2
D Java Quicksort Java Basics - Anfänger-Themen 5
A Frage zu QuickSort Java Basics - Anfänger-Themen 9
B Quicksort mit Durchschnitt als Pivot Java Basics - Anfänger-Themen 1
K Quicksort Java Basics - Anfänger-Themen 3
M Quicksort - Probleme Java Basics - Anfänger-Themen 5
T QuickSort implementieren Java Basics - Anfänger-Themen 5
R QuickSort Verständis Problem (?) Java Basics - Anfänger-Themen 2
M Quicksort implementierung Java Basics - Anfänger-Themen 23
E Quicksort Java Basics - Anfänger-Themen 8
Xendarii Quicksort gibt kein Ergebnis aus Java Basics - Anfänger-Themen 13
E QuickSort: Ergebniss speichern Java Basics - Anfänger-Themen 2
P quickSort eines Objekt-Arrays geht nicht! Java Basics - Anfänger-Themen 11
F Stackoverflow bei Quicksort Java Basics - Anfänger-Themen 2
F Quicksort Java Basics - Anfänger-Themen 22
C Quicksort Invariante Java Basics - Anfänger-Themen 2
C QuickSort - Pivot in der Mitte Java Basics - Anfänger-Themen 5
P QuickSort iterativ Java Basics - Anfänger-Themen 5
K Eine Frage zum Quicksort Java Basics - Anfänger-Themen 11
B Quicksort --> Methodenaufruf Java Basics - Anfänger-Themen 10
B QuickSort - Fehler nicht zu finden Java Basics - Anfänger-Themen 2
W Quicksort Problem Java Basics - Anfänger-Themen 3
A Quicksort, #Vergleiche zählen klappt nicht Java Basics - Anfänger-Themen 3
J Quicksort Implementierung-- Exception ArrayOutOfBounds Java Basics - Anfänger-Themen 6
M Fehler in meinem Quicksort! Java Basics - Anfänger-Themen 21
B Quicksort Struktogramm Java Basics - Anfänger-Themen 9
G Frage zu Quicksort Java Basics - Anfänger-Themen 18
0 Quicksort bsp Java Basics - Anfänger-Themen 5
B Quicksort Problem Java Basics - Anfänger-Themen 6
S Mein Quicksort Problem: he method quickSort(int[], int, int) Java Basics - Anfänger-Themen 2
M Quicksort Java Basics - Anfänger-Themen 2
C Quicksort raten Java Basics - Anfänger-Themen 2
K ArrayList sortieren mit Quicksort Java Basics - Anfänger-Themen 3
J Quicksort programmieren Probleme Java Basics - Anfänger-Themen 9
S Quicksort Programm Java Basics - Anfänger-Themen 7
D Quicksort Java Basics - Anfänger-Themen 3
K Parameterübergabe bei quickSort Java Basics - Anfänger-Themen 6
S QuickSort will mir nicht in den Kopf (an einer Stelle) Java Basics - Anfänger-Themen 14
0 Quicksort Java Basics - Anfänger-Themen 2
M QuickSort Java Basics - Anfänger-Themen 4
J QuickSort - kurze Frage Java Basics - Anfänger-Themen 9
H Quicksort und Rekursiv: Türme von Hanoi Java Basics - Anfänger-Themen 9

Ähnliche Java Themen

Neue Themen


Oben