Partition sort

Een ander beroemd sorteeralgoritme heet Partition Sort. Het werkt zo:

Namen zijn niet gesorteerd voor of na het draaipunt. Voor Geen Afbeelding, is dit de status na de eerste splitsing: het draaipunt is Emma, de lijst voor het draaipunt is {Ava, Abigail} en de lijst na het draaipunt is {Olivia, Sophia, Isabella, Mia, Emily}. Het sorteerproces gaat door voor deze twee kleinere lijsten.
  1. Probeer eerst Partition Sort helemaal te snappen voordat je code gaat schrijven. Sta op en vorm een lijn met je klas. Volg daarna het algoritme van Partition Sort om iedereen te sorteren op naam.
  2. Waarom is Partition Sort een voorbeeld van recursie? Wat is het basisgeval?

Om een Partition Sortblok in Snap! te schrijven heb je code nodig voor het basisgeval en code die Partition Sort volgt.

  1. Geen Afbeelding
    Bekijk dit nieuwe project dat het verbindblok bevat (in het Variabelenmenu). Geen Afbeelding
  2. Beschrijf wat het verbindblok doet.
  3. Je moet uitvogelen hoe je elementen in drie categorieën plaatst en hoe je de uiteindelijke lijst maakt die je rapporteert.
    Bouw de recursieve rapporteur Partition Sort. De uitvoer hiervan moet gelijk zijn aan die van Selection Sort.
Stel dat je gisteren een grote gesorteerde lijst had en vandaag een paar nieuwe elementen toevoegt. Je moet nu de lijst hersorteren. Een algemeent sorteeralgoritme zal geen voordeel hebben aan het feit dat de lijst al bijna helemaal gesorteerd is. Maar Insertion Sort, een sorteeralgoritme dat over het algemeen heel langzaam is, is juist heel goed in dit speciale geval.

Waarom zijn er verschillende sorteeralgoritmes? Sommige sorteeralgoritmes doen er langer over dan andere, maar zelfs een algoritme dat over het algemeen langzaam is, kan soms heel snel zijn.

  1. Je kan hier ook een lange lijst van namen gebruiken.
    Maak een lijst met 500 willekeurige getallen en sorteer de lijst met de drie verschillende sorteeralgoritmes die je deze Les gemaakt hebt. Houd bij hoe lang ze erover doen:
    Geen Afbeelding
  2. Wat was het snelste algoritme? Waarom zou dit algoritme het snelst zijn geweest?<
Terug Volgende