faecher:informatik:oberstufe:algorithmen:sorting:radixsort:start

Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.

Link zu der Vergleichsansicht

Beide Seiten, vorherige Überarbeitung Vorherige Überarbeitung
Nächste Überarbeitung		 Vorherige Überarbeitung
faecher:informatik:oberstufe:algorithmen:sorting:radixsort:start [01.07.2025 05:47] – Frank Schiebelfaecher:informatik:oberstufe:algorithmen:sorting:radixsort:start [07.07.2025 19:01] (aktuell) – Frank Schiebel
Zeile 5: Zeile 5:
 Radixsort sortiert die Elemente einer Liste, indem er sie nach einzelnen Ziffern (Stellenwerten) gruppiert, meistens beginnend mit der niederwertigsten Ziffer. Für jede Ziffer der zu sortierenden Zahlen wird ein sogenannter "Bucket" verwendet, in den die Zahlen einsortiert werden. Nachdem die Elemente auf die "Buckets" verteilt wurden, werden sie wieder eingesammelt, was dazu führt, dass die Sortierung für die betrachtete Stelle korrekt ist. Dieser Vorgang wird für die Ziffern jeder Stelle wiederholt, bis alle Stellen abgearbeitet sind, dann ist die Liste sortiert. Radixsort sortiert die Elemente einer Liste, indem er sie nach einzelnen Ziffern (Stellenwerten) gruppiert, meistens beginnend mit der niederwertigsten Ziffer. Für jede Ziffer der zu sortierenden Zahlen wird ein sogenannter "Bucket" verwendet, in den die Zahlen einsortiert werden. Nachdem die Elemente auf die "Buckets" verteilt wurden, werden sie wieder eingesammelt, was dazu führt, dass die Sortierung für die betrachtete Stelle korrekt ist. Dieser Vorgang wird für die Ziffern jeder Stelle wiederholt, bis alle Stellen abgearbeitet sind, dann ist die Liste sortiert.
  
-Wichtige Eigenschaften:+|In der Animation kann man das Prinzip von Radix-Sort sehen.\\ Zunächst werden die Elemente entsprechend ihrer Einerstelle in die Buckets sortiert und anschließend wieder in das ursprüngliche Array zurück übernommen, beginnend bei Bucket 9.\\ Jetzt befinden sich die Elemente in der korrekten Reihenfolge bezüglich der Einerstelle.\\ Anschließend verfährt man mit der Zehnerstelle entsprechend.\\ Wenn man darauf achtet, die Reihenfolge von Elementen mit gleichen Stellenwerten beizubehalten, sind diese entsprechend der Einerstelle vom vorigen Durchlauf an der korrekten Position.\\ Das Vorgehen wiederholt man für die weiteren Stellen der Elemente und erhält so eine sortierte Liste.|<html> 
 +<iframe src="https://tools.info-bw.de/radix/" frameBorder="0" width="370" height="400"></iframe> 
 +</html> | 
 + 
 +Radixsort stellt **besondere Anforderungen an die zu sortierenden Elemente** (es muss eine Stellenweise, lexikalische Ordnung für die Elemente existieren) - die zu Beginn dieses Kapitels eingeführte Verallgemeinerung mit Hilfe der ''compareTo''-Methode, beliebige Objekte "sortierbar zu machen", funktioniert für Radix-Sort nicht! Dafür hat Radixsort eine Zeitkomplexität von ca. O(n) - das lässt sich bei vergleichsbasierten Sortierverfahren nicht erreichen. 
 + 
 +**Weitere Wichtige Eigenschaften:**
  
   * Nicht-vergleichend: Radixsort vergleicht keine Elemente direkt miteinander, sondern nutzt die Ziffernpositionen.   * Nicht-vergleichend: Radixsort vergleicht keine Elemente direkt miteinander, sondern nutzt die Ziffernpositionen.
Zeile 12: Zeile 18:
   * Radixsort ist besonders effizient, wenn die Anzahl der Ziffern (bzw. die Schlüssellänge) im Vergleich zur Anzahl der Elemente klein ist   * Radixsort ist besonders effizient, wenn die Anzahl der Ziffern (bzw. die Schlüssellänge) im Vergleich zur Anzahl der Elemente klein ist
  
-<html> +---- 
-<div id="vueApp2"> +{{:aufgabe.png?nolink  |}} 
-  <div v-bind:class="{ unstableClass: !stableBool }"> +=== (A1) ===
-  <p>Speed: <input v-model="inpVal" type="range" min="50" max="300"><!-- {{ delay }}--></p> +
-  <p>Stable sort? +
-    <label class="dsa_label"> +
-      <input type="checkbox" v-model="stableBool" :disabled="chbxDisabled"> +
-      {{ isStable }} +
-    </label> +
-  </p> +
-  <button @click="action" :disabled="btnIsDisabled">{{ buttonText }}</button> {{ msgDone }}<br> +
-  <div id="frameDiv3"> +
-    <div id="leftDiv"> +
-      <div v-for="(x, index) in count" class="countDivParent2" :key="index-1000"> +
-        <div class="numberDiv2" :key="index-3000"> +
-          {{ index }} +
-        </div> +
-        <transition-group name="v2"> +
-          <div v-for="y in count[index]" :key="y.keyNmbr"  +
-          class="diceDiv3"  +
-          :class="{  +
-            'diceDiv2-active': y.isActive,  +
-            'diceDiv2-finished': y.isFinished +
-          }"  +
-          :style="{ +
-            //width: 3+x.countValue*25 + 'px', +
-            transition: 'all ' + delay +
-          }"> +
-          <span v-for="(digit, dIndex) in y.digits"  +
-                :class="{ 'highlight2': dIndex === y.digits.length - 1 - currentDigitPosition }"> +
-            {{ digit }} +
-          </span> +
-          </div> +
-        </transition-group> +
-      </div> +
-    </div> +
-    <div id="rightDiv2"> +
-      <transition-group name="v4"> +
-        <div v-for="(x,index) in dice"  +
-          :key="x.keyNmbr" +
-          class="diceDiv3"  +
-          :class="{  +
-            'diceDiv2-active': x.isActive, +
-            'diceDiv2-finished': x.isFinished +
-          }"  +
-          :style="{ +
-            transition: 'all ' + delay +
-          }" +
-        > +
-        <span v-for="(digit, dIndex) in String(x.dieNmbr).split('')"  +
-              :class="{ 'highlight2': dIndex === String(x.dieNmbr).length - 1 - currentDigitPosition }"> +
-          {{ digit }} +
-        </span> +
-      </div> +
-      </transition-group> +
-    </div> +
-  </div> +
-  </div> +
-</div> +
-<script> +
-const app2 = Vue.createApp({ +
-  data() { +
-    return { +
-      btnIsDisabled: false, +
-      chbxDisabled: false, +
-      msgDone: '', +
-      inpVal: 200, +
-      count: [], +
-      dice: [], +
-      keyNumber: 0, +
-      keyNumber2: 0, +
-      currentDigitPosition: 0, +
-      buttonText: 'Radix Sort', +
-      stableBool: true +
-    } +
-  }, +
-  computed: { +
-    delay(){ +
-      return 350 - this.inpVal; +
-    }, +
-    isStable() { +
-      if(this.stableBool) { +
-        return 'Yes' +
-      } +
-      else { +
-        return 'No' +
-      } +
-    } +
-  }, +
-  watch: { +
-    delay: { +
-      immediate: true, +
-      handler() { +
-        this.updateMoveDuration(); +
-      }, +
-    } +
-  }, +
-  methods: { +
-    newKey(){ +
-      this.keyNumber2++; +
-      return this.keyNumber2; +
-    }, +
-    action(){ +
-      if(this.buttonText === "Radix Sort") { +
-        this.radixSort(); +
-      } +
-      else { +
-        this.addDie50(); +
-      } +
-    }, +
-    updateMoveDuration() { +
-      let stylesheets = document.styleSheets; +
-      for (let i = 0; i < stylesheets.length; i++) { +
-        let rules = stylesheets[i].cssRules || stylesheets[i].rules; +
-        for (let j = 0; j < rules.length; j++) { +
-          if (rules[j].selectorText === '.v2-move') { +
-            rules[j].style.transitionDuration = this.delay + 'ms'; +
-            break; +
-          } +
-        } +
-      } +
-    }, +
-    async radixSort() { +
-      this.btnIsDisabled = true; +
-      this.chbxDisabled = true; +
-      this.currentDigitPosition = 0; +
-      await new Promise(resolve => setTimeout(resolve, this.delay*4)); +
-      for(let k=0; k<3; k++){ +
-        while(this.dice.length > 0) { +
-          if(this.stableBool){ +
-            this.dice[0].isActive = true; +
-            await new Promise(resolve => setTimeout(resolve, this.delay)); +
-            let removedObj = this.dice.splice(0, 1)[0]; +
-            removedObj.digits = String(removedObj.dieNmbr).split('').map(Number); +
-            let n = this.currentDigitPosition+1; +
-            let digit = Math.floor(removedObj.dieNmbr / Math.pow(10, n - 1)) % 10; +
-            this.count[digit].push(removedObj); +
-            await new Promise(resolve => setTimeout(resolve, this.delay)); +
-            await new Promise(resolve => setTimeout(resolve, this.delay)); +
-            this.count[digit][this.count[digit].length-1].isActive = false; +
-          } +
-          else { +
-            this.dice[this.dice.length-1].isActive = true; +
-            await new Promise(resolve => setTimeout(resolve, this.delay)); +
-            let removedObj = this.dice.pop(); +
-            removedObj.digits = String(removedObj.dieNmbr).split('').map(Number); +
-            let n = this.currentDigitPosition+1; +
-            let digit = Math.floor(removedObj.dieNmbr / Math.pow(10, n - 1)) % 10; +
-            this.count[digit].push(removedObj); +
-            await new Promise(resolve => setTimeout(resolve, this.delay)); +
-            await new Promise(resolve => setTimeout(resolve, this.delay)); +
-            this.count[digit][this.count[digit].length-1].isActive = false; +
-          } +
-           +
-        } +
-        await new Promise(resolve => setTimeout(resolve, this.delay)); +
-        for(let i=this.count.length-1; i>=0; i--){ +
-          while(this.count[i].length>0){ +
-            this.count[i][this.count[i].length-1].isActive = true; +
-            await new Promise(resolve => setTimeout(resolve, this.delay)); +
-            let removedObj = this.count[i].pop(); +
-            await new Promise(resolve => setTimeout(resolve, this.delay)); +
-            this.dice.splice(0,0,removedObj); +
-            await new Promise(resolve => setTimeout(resolve, this.delay)); +
-            await new Promise(resolve => setTimeout(resolve, this.delay)); +
-            this.dice[0].isActive = false; +
-          } +
-        } +
-        this.currentDigitPosition++; +
-        await new Promise(resolve => setTimeout(resolve, this.delay*4)); +
-      } +
-      for(let i=0; i<this.dice.length; i++){ +
-        if(this.stableBool){ +
-          this.dice[i].isFinished = true; +
-        } +
-        else { +
-          this.dice[i].isActive = true; +
-        } +
-      } +
-      await new Promise(resolve => setTimeout(resolve, (this.delay))); +
-      if(this.stableBool){ +
-        this.msgDone = 'Done!'; +
-      } +
-      else { +
-        this.msgDone = 'Not sorted correctly!'; +
-      } +
-      this.buttonText = "New Values"; +
-      this.btnIsDisabled = false; +
-    }, +
-    addDie() { +
-      const newDie = { +
-        dieNmbr: Math.ceil(Math.random() * 500)+100, +
-        keyNmbr: this.keyNumber, +
-        isActive: false, +
-        isFinished: false +
-      }; +
-      this.dice.push(newDie); +
-      this.keyNumber++; +
-    }, +
-    addDie50() { +
-      this.chbxDisabled = false; +
-      this.count = [[],[],[],[],[],[],[],[],[],[]]; +
-      this.currentDigitPosition = 5; +
-      this.dice = []; +
-      for (let i = 0; i < 10; i++) { +
-        this.addDie(); +
-      } +
-      this.buttonText = "Radix Sort"; +
-      this.msgDone = ''; +
-      this.stableBool = true; +
-    } +
-  }, +
-  mounted() { +
-    this.addDie50(); +
-    this.updateMoveDuration(); +
-  } +
-}); +
-app2.mount('#vueApp2'); +
-</script>+
  
 +Überlege, welche Eigenschaften die Elemente einer Liste haben müssen, wenn man sie mit Radix-Sort sortieren möchte. Gib weitere Beispiele an, die Listen beinhalten die dich aus zahlen bestehen.
  
-</html>+---- 
 +{{:aufgabe.png?nolink  |}} 
 +=== (A2) ===
  
 +Implementiere Radix-Sort im Programmgerüst der entsprechenden Klasse in der Bluej-Vorlage von https://codeberg.org/qg-info-unterricht/algs4-sort-bluej. 
 +
 +**A2.1** Betrachte zunächst den Konstruktor: Notiere dir die Bedeutung von $n$, $digits$ und $a$ im Kontext von Radix-Sort. Welche Aufgabe hat die for-Schleife?
 +
 +Kontrolliere deine Überlegung mit Hilfe entsprechender Eingaben, indem du das erzeugte Objekt untersuchst.
 +
 +**A2.2** Als "Buckets" verwenden wir ein "Array aus ArrayLists":
 +
 +<code java>
 +// Buckets als Array aus ArrayLists erzeugen
 +ArrayList<Integer>[] bucket = new ArrayList[10]; 
 +for(int i=0; i<10; i++) {
 +     bucket[i] = new ArrayList<>();
 +}
 +</code>
 +
 +''bucket[7]'' ist die ArrayList, die alle Elemente mit der betrachteten Ziffer ''7'' aufnimmt. Analog für alle anderen Ziffern, die in den Zahlen vorkommen können (0-9).
 +
 +**A2.3** Implementiere die beiden Abschnitte "Verteilen" und "Einsammeln" so, dass die eingegebenen Zahlen anschließend nach ihrer Einer-Ziffer sortiert sind. Beachte die Anmerkungen in der Vorlage!
 +
 +**A2.4** Wiederhole den Verteilen/Einsammeln-Zyklus nun für jede Stelle der Zahlen, indem du eine Schleife um diese Abschnitte herum erzeugst - beachte die Kommentare im Code. 
 +
 +Du musst dir noch überlegen, wie du der Reihe nach Einer-, Zehner, Hunderter-Stelle ermitteln kannst, um bei jedem neuen Durchlauf in die passenden Buckets zu sortieren. 
 +
 +Außerdem musst du festlegen, wie oft diese äußere Schleife durchlaufen werden soll - ''digits'' hilft hier weiter.
 +
 +
 +++++ Lösungsvorschlag |
 +<code java>
 +    // Radixsort sortiert die ArrayList 
 +    public void sort(ArrayList<Integer> a) {
 +
 +        // Unsortiertes Array ausgeben
 +        System.out.println(Arrays.toString(a.toArray()));
 +
 +        // Buckets als Array aus ArrayLists erzeugen
 +        ArrayList<Integer>[] bucket = new ArrayList[10]; 
 +        for(int i=0; i<10; i++) {
 +            bucket[i] = new ArrayList<>();
 +        }
 +
 +        for(int d=0 ; d<digits; d++) {
 +            int q=1;
 +            for(int i=0; i<d; i++) {
 +                q=q*10;
 +            }
 +            // Verteilen
 +            for(int z=0; z<a.size(); z++) {
 +                int ziel_bucket = (a.get(z)/q)%10;
 +                bucket[ziel_bucket].add(a.get(z));
 +            }
 +            // Einsammeln
 +            int pos = a.size()-1;
 +            for(int b=9; b>=0; b--) {
 +                while(!bucket[b].isEmpty()) {
 +                    a.set(pos, bucket[b].removeLast());
 +                    pos--;
 +                }
 +            }
 +            // Zwischen/Endergebnis
 +            System.out.println(Arrays.toString(a.toArray()));
 +        }        
 +     
 +    }
 +</code>
 +++++
  • faecher/informatik/oberstufe/algorithmen/sorting/radixsort/start.1751348831.txt.gz
  • Zuletzt geändert: 01.07.2025 05:47
  • von Frank Schiebel