SS09 Aufgabe 4 Radixsort - Warum nicht stabil?

Bachelor Algorithmen und Datenstrukturen
1

Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.

2

SS09 Aufgabe 4 Radixsort - Warum nicht stabil?
Hallo allerseits,

zum besseren Verständnis, habe ich versucht die FSI-Lösung zur oben genannten Aufgabe in Eclipse zu implementieren.
Leider erhalte ich einen falsch sortierten Array. So wie es aussieht ist meine Lösung nicht stabil, oder?
Was kann ich tun um sie stabil zu machen?

Input:
99999 | 34567 | 90600 | 12345 | 69696 |

Output:
12345 | 34567 | 69696 | 99999 | 90600 |
90600 | 12345 | 34567 | 69696 | 99999 |
12345 | 34567 | 90600 | 69696 | 99999 |
90600 | 12345 | 34567 | 69696 | 99999 |
90600 | 12345 | 69696 | 34567 | 99999 |

Expected Output:
90600 | 12345 | 69696 | 34567 | 99999 |
90600 | 12345 | 34567 | 69696 | 99999 |
12345 | 34567 | 69696 | 90600 | 99999 |
12345 | 34567 | 69696 | 90600 | 99999 |
12345 | 34567 | 69696 | 90600 | 99999 |

Aufgabenstellung:
In der folgenden Aufgabe sollen Sie 5-stellige Postleitzahlen (aufsteigend) mittels Radix- Sort sortieren. Gehen Sie dabei davon aus, dass die Methode getDigit(int n, int pos) die Stelle pos der Zahl n (von links nach rechts gelesen) zurückliefert. Implementieren Sie die Methode sortPos(int array[], int from, int to, int pos), die eine Reihung von Postleitzahlen nach der Stelle pos sortiert; from bzw. to geben das Intervall [from;to[ von array an, das sortiert wird. Achten Sie darauf, dass Ihr Sor- tierung stabil ist.
Implementieren Sie weiterhin die Methode radixSort(int array[]), die eine Reihung von 5-stelligen Postleitzahlen mittels Radix-Sort sortieren soll. Verwenden Sie dabei die eben implementierte Methode sortPos().

Link zum FSI-Lösungsvorschlag
https://fsi.cs.fau.de/dw/pruefungen/bachelor/aud/loesungss09

Mein Code

import java.util.LinkedList;

public class Radix {

	public static void main(String[] args) {
		// TODO Auto-generated method stub

	
		int[] plzs = new int[] {  99999, 34567, 90600, 12345, 69696};
		printArray(plzs);
		System.out.println();
		
		radixSort(plzs);
		System.out.println();
		
		printArray(plzs);
	}
	
	public static void printArray(int[] arr) {
		for(int i=0; i<arr.length; i++) {
			System.out.print(arr[i]+" | ");
		}
		System.out.println();
	}
	
	public static int intlength(int n) {
		return (int)(Math.log10(n)+1);
	}
	
	public static int getDigit(int n, int pos) {
		int length = intlength(n);
		pos=length-pos;
		int res = (int) ((n/Math.pow(10, pos))%10);
		return res;
	}
	
	
	public static void sortPos(int array[], int from, int to, int pos) {
		LinkedList<Integer>[] buckets = new LinkedList[10];
		
		for(int i=0; i< buckets.length; i++) {
			buckets[i]= new LinkedList();
		}
		
		for(int i=from; i< to; i++) {
			int b = getDigit(array[i], pos);
			buckets[b].addLast(array[i]);
		}
		
		LinkedList<Integer> master = new LinkedList<>();
		
		for(int i = 0; i < buckets.length; i++) {
			master.addAll(buckets[i]);
		}
		
		for(int i = 0; i<array.length; i++) {
			array[i]=master.removeFirst();
		}
	}
	
	public static void radixSort(int array[]) {
		for (int i = 1; i <= 5; i++) {
			sortPos(array, 0, array.length, i);
			printArray(array);
		}
	}

}

Liebe Grüße
Speedy

3

Es sieht für mich so aus, als würden die Stellen der PLZ in der falschen Reihenfolge abgearbeitet werden. Demnach müsste die Schleife in radixSort() von 4 bis 0 gehen, statt von 0 bis 4.

4

Das hatte ich auch schon vermutet, allerdings wird nach dieser Änderung der Input unverändert ausgegeben

5

Habe es gelöst:
Das for-loop in radixSort(): Muss von 5 bis 1 runterzählen :slight_smile:

import java.util.LinkedList;

public class Radix {

	public static void main(String[] args) {
		// TODO Auto-generated method stub

	
		int[] plzs = new int[] {  99999, 34567, 90600, 12345, 69696};
		printArray(plzs);
		System.out.println();
		
		radixSort(plzs);
		System.out.println();
		
		printArray(plzs);
	}
	
	public static void printArray(int[] arr) {
		for(int i=0; i<arr.length; i++) {
			System.out.print(arr[i]+" | ");
		}
		System.out.println();
	}
	
	public static int intlength(int n) {
		return (int)(Math.log10(n)+1);
	}
	
	public static int getDigit(int n, int pos) {
		int length = intlength(n);
//		System.out.println(length);
		pos=length-pos;
		int res = (int) ((n/Math.pow(10, pos))%10);
		return res;
	}
	
	
	public static void sortPos(int array[], int from, int to, int pos) {
		LinkedList<Integer>[] buckets = new LinkedList[10];
		
		for(int i=0; i< buckets.length; i++) {
			buckets[i]= new LinkedList();
		}
		
		for(int i=from; i< to; i++) {
			int b = getDigit(array[i], pos);
			buckets[b].addLast(array[i]);
		}
		
		LinkedList<Integer> master = new LinkedList<>();
		
		for(int i = 0; i < buckets.length; i++) {
			master.addAll(buckets[i]);
		}
		
		for(int i = 0; i<array.length; i++) {
			array[i]=master.removeFirst();
		}
	}
	
	public static void radixSort(int array[]) {
		for (int i = 5; i >= 1; i--) {
			sortPos(array, 0, array.length, i);
			printArray(array);
		}
	}

}