Selectionsort Verbesserung?
Wie kann man den unteren Programm so verbessern, dass die zu sortierende Menge pro Durchgang eingeschränkt oder verringert wird? Wie kann man die Verbesserung realisieren?
Danke im voraus!
3 Antworten
dass die zu sortierende Menge pro Durchgang eingeschränkt oder verringert wird
Wird sie doch bereits?
Die Innere Schleife startet jeden Durchgang bei i+1 statt bei 0
Das ist kein SelectionSort sondern BubbleSort.
BubbleSort vertauscht zwei benachbarte Elemente, sobald sie nicht in der richtigen Reihenfolge sind.
Selectionsort sucht den Index des kleinsten Elements und tauscht am Ende der Schleife.
InsertSort betrachtet nur das nächste Element und fügt es an der richtigen Stelle in die bereits sortierte Folge ein. Im besten Fall geht es die Folge nur einmal durch um festzustellen, dass schon alles sortiert ist. Von den drei genannten ist InsertSort am schnellsten. Aber alle drei haben im schlechten Fall "quadratisches Zeitverhalten", d.h. sie brauchen bei doppelter Eingabe viermal so lange, bei 10facher Eingabe 100 mal so lange.
ShellSort ist von den "einfachen" Algorithmen der beste. Es funktioniert wie InsertSort jedoch zunächst mit größerer, dann kleiner werdender Schrittweite.
Danach kommen die höheren Algorithemn QuickSort, HeapSort, MergeSort.
Viele moderne Programmiersprachen haben effiziente Sortierverfahren eingebaut. Dann ruft man nur noch .sort() auf und gut ist.
Statt Selection-Sort einen Sortieralgo mit besserer Laufzeit nehmen.
Quicksort ist doch häufig genau deshalb beliebt.
Gruß