Not logged in. · Lost password · Register

SpeedyGonzalez
Member since Jul 2017
103 posts
Subject: 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
This post was edited 4 times, last on 2019-05-15, 09:09 by SpeedyGonzalez.
Rowy
Member since Jul 2016
73 posts
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.
SpeedyGonzalez
Member since Jul 2017
103 posts
Das hatte ich auch schon vermutet, allerdings wird nach dieser Änderung der Input unverändert ausgegeben
SpeedyGonzalez
Member since Jul 2017
103 posts
Habe es gelöst:
Das for-loop in radixSort(): Muss von 5 bis 1 runterzählen :)

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);
        }
    }

}
This post was edited 2 times, last on 2019-05-15, 09:23 by SpeedyGonzalez.
Close Smaller – Larger + Reply to this post:
Verification code: VeriCode Please enter the word from the image into the text field below. (Type the letters only, lower case is okay.)
Smileys: :-) ;-) :-D :-p :blush: :cool: :rolleyes: :huh: :-/ <_< :-( :'( :#: :scared: 8-( :nuts: :-O
Special characters:
Go to forum
Datenschutz | Kontakt
Powered by the Unclassified NewsBoard software, 20150713-dev, © 2003-2011 by Yves Goergen