Selection- vs Insertion Sort ____ Vorteile/Nachteile?

Hallo,

ich würde gerne eine Applikation für ein privates Projekt programmieren und brauche für ein Sortierverfahren eine Methode. Nach ein wenig Recherche bin ich auf den Selection- u. Insertion Sort gestoßen.

Was sind die Vor- Nachteile der jeweiligen Swap Methoden? Bräuchte eine zweite Meinung...

4 Antworten

sebastian442

10.04.2021, 18:49

Es kommt halt auf den Fall den du Sortieren möchtest an. (Weitestgehend vorsortiert?, wenig RAM? etc.) Im Allgemein sind das beides meist eher langsame Algorithmen. Dafür einfach zu implementieren. Geschwindigkeit wird in den meist Fällen gleich sein. Wenn du was schnelleres suchst kannst du dir mal Heap Sort oder Quicksort anschauen.

Woher ich das weiß:Studium / Ausbildung – Ich studiere Informatik

Schachpapa

10.04.2021, 18:58

Selection Sort ist immer langsam. Insertion-Sort kann schnell sein, wenn das allermeiste bereits sortiert ist. Meistens fährst du in der Praxis mit den bereits in Bibliotheken vorhandenen Sortierverfahren besser.

Wenn deine Daten in einem Array meinArray vorliegen:

import java.util.Arrays;
...
Arrays.sort(meinArray);

Das funktioniert.

Nachteil: Du hast es nicht selbst gemacht und lernst nichts dabei.

Guckst du hier:

https://www.geeksforgeeks.org/arrays-sort-in-java-with-examples/

Mastermind498

10.04.2021, 18:45

nimm doch einfach ein schon vorsortiertes objekt. beispielsweise eine tree map oder so und wenn es ein custom type ist kann du für den einfach das comperator interface implementieren oder die compare to methode

Leonardo06

10.04.2021, 18:49

Das sind zwei sehr simple Algorithmen. Wenn du wirklich was schnelles willst, könntest du den Heap Sort oder einen Radix Sort verwenden.

Woher ich das weiß:Hobby – Dokumentationen und Artikel.

Deluxe57

10.04.2021, 18:51

Wie wärs mit Quicksort?

Leonardo06

10.04.2021, 19:00

@Deluxe57

Auch ein guter Algo.

Wasist der Unterschied zwischen Bubblesort und Selection-sort. Ich meine beides sind ja vergleichsbasierte Sortierverfahren.

...zur Frage

Was bedeutet Stabilität bei Algorithmen?

Hallo zusammen,

ich stehe kurz vor meiner ersten Klausur "Grundlagen der Wirtschaftsinformatik 1" und beschäftige mich momentan mit Sortieralgorithmen.

Wir haben eine Aufgabe bekommen, die lautet: "Analysieren Sie, welche der erarbeiteten Sortieralgorithmen (Bubble-, Insertion-, Selection-, Quick-, Merge- und Shell-Sort) stabil sind."

Was bedeutet in diesem Kontext "stabil". Ich kann mir leider nicht wirklich etwas drunter vorstellen. Ich vermute, es hat vielleicht etwas mit der vorliegenden Reihenfolge zu run?!

Vielen Dank schonmal und liebe Grüße :-)

...zur Frage

Directions, Elumen, Vor-und Nachteile, Andauern der Farbe?

Hallo. :) Ich möchte mir in den Weihnachtsferien die Haare in lila oder blau tönen. Sollte ich dafür Directions oder Elumen verwenden? Mit Elumen kenne ich mich überhaupt nicht aus... Meine Haare sind naturblond, mit teilweise leichtem dunkelblond und ich will sie auf keinen Fall heller färben ^^ Wie lange würde die Farbe denn halten, wenn man die Haare alle zwei Tage wäscht? Und welche Vor und Nachteile haben die jeweiligen Methoden? Bin für jede Antwort dankbar :) LG

...zur Frage

Sortieralgorithmus selection sort?

Hey, ich soll ein zweiseitiges Handout zu den Sortieralgorithmus selection sort erstellen, wobei ich

auf die grundlegende Vorgehensweise dieses Algorithmus eingehen soll
und ich brauche die Java- Methode zur Implementierung, wobei man davon ausgehen soll, dass ein Array von int- Werten zu sortieren ist.

Dazu wurde uns auch Material gegeben, welches ich als Foto anhängen werde.

Ich freue mich auf Rückmeldungen!

...zur Frage

Warum sollte man Lineare Listen (arrays) als Datenstruktur verwenden?

Lineare Listen haben erstmal sehr viele Nachteile...

Die Datenstruktur ist nicht dynamisch (schwer zu erweitern)
Das Suchen in Arrays ist nur schwer in O(log(n)) möglich, da die binäre Suche sehr viel extraspeicher benötigt, und Sprungsuchen / Interpolationssuchen häufig nicht in O(log(n)) funktionieren
Sortierverfahren sind oftmals problematisch, da quicksort ggf. eine schlechte Worst-Case Komplexität hat.
Alle Elemente müssen nebeneinander im Speicher liegen, d.h. es gibt ein Limit wie groß ich ein Array machen kann.

Dagegen sind Bäume:

Dynamisch (sehr einfach zu erweitern, da man einfach nur Pointer hinzufügen muss)
Suche funktioniert aufbaubedingt IMMER in O(log(n))
Mit heapsort lässt sich immer im Worst-Case in O(n*log(n)) sortieren
Die Datenstruktur kann beliebig groß werden (man muss nur Pointer hinzufügen).

Meine Frage also, warum sollte man lineare Listen verwenden, und Warum lernt man x verschiedene Sortierverfahren von Insertion, Selection, Merge, Bubble & Quicksort für lineare Listen, wenn die einfachste Lösung ist einfach Bäume zu verwenden?

...zur Frage

Wie kann man Liste in Java sortieren?

Hey,

Ich muss eine Liste sortieren, die 15 Zahlen speichert. Am Ende sollen die Zahlen von klein nach groß geordnet sein.

Wie kann ich das machen?

Würde mich sehr über Hilfe freuen.

Liebe Grüße

...zur Frage

Korrektheitsbeweis Algorithmus?

Hallo liebe Community,

ich habe eine Aufgabe bekommen in welcher ich Pseudocode entwickeln soll. Meinem Algorithmus wird ein Array an Zahlen gegeben A[1, n] mit n Einträgen. Ich soll in diesem Array die Senken zählen. Eine Senke ist dabei eine Position i [2, n - 1] für die folgendes gilt: A[i - 1] > A[i] < A[i + 1].

Meiner Auffasung nach bedeutet das nun, dass z.B. das Array [1, 3, 2, 4, 3, 5] zwei Senken hat. Nämlich einmal der dritte Eintrag und der fünfte Eintrag.

Mein Pseudocode sieht folgendermaßen aus:

Input: A[1, n] mit n Einträgen
Output: Anzahl der Senken

counter := 0
for j := 2 to n - 1 do
  val := A[j]
  if val < A[j - 1] and val > A[j + 1] do
    counter := counter + 1

Mein Java Code dazu sieht folgendermaßen aus:

public static int countSenken(int[] arr) {
  int counter = 0;
  for (int i = 1; i < arr.length - 1; i++) {
    int val = arr[i];
    if (val < arr[i - 1] && val < arr[i + 1]) {
      counter++;
    }
  }
}

Nun soll ich die Korrektheit meines Algorithmus' beweisen. Wir haben das schonmal an dem Beispiel des Insertionsort Algorithmus' gemacht. Die herangehensweise ist ja eigentlich, dass man eine Schleifeninvariante aufstellt und diese dann mittels Induktion beweist. Mein Problem ist jetzt aber, dass ich diese Schleifeninvariante nicht aufstellen kann. Beim Insertionsort, da beweist man ja die Sortiertheit und da verändert sich ja das Array. Aber bei diesem Algorithmus jetzt da verändert sich das Array ja gar nicht.

Ich weiß halt, dass n >= 3 sein muss damit der Algorithmus überhaupt funktioniert. Kann mir vielleicht jemand einen Ansatz geben wie ich die Korrektheit beweise?

Ich wäre euch allen sehr dankbar :)

...zur Frage

Pivotwahl bei Quicksort und Quickselect?

Guten Abend,

ich bräuchte mal kurz Hilfe bei folgenden Aufgaben, bitte. Es geht mir darum, dass ich einfach nicht versteh', was zu tun ist. Wir hatten in der Vorlesung den Quicksort-Algorithmus. Ich weiß, dass bei Quicksort das zu sortierende Array in immer kleiner Teilarrays eingeteilt wird, wobei das größere Array zuerst auf den Stack gelegt wird. Das Pivotelement ist entweder das linke oder das rechte und man setzt dann links und rechts einen Pointer am entsprechenden Teilarray. Ist das erste Element des zu sortierenden Teilarrays, welches größer als das Pivotelement ist, gefunden, und es findet sich vom rechten Pointer aus das erste Element, welches kleiner als das Pivotelement ist, so werden diese vertauscht. Bei Überkreuzungen tausche jenes Element auf dass der linke Pointer zeigt mit dem Pivotelement. So hatten wir's zumindest in der Vorlesung (Partitionswahl). Zu den Aufgaben

Aufgabe 1

Ein wichtiger Faktor für die Laufzeit von Quicksort und Quickselect (das Auswahlverfahren des k-kleinsten Elements analog zu Quicksort) ist die Wahl des Pivotelements. Das Pivotelement sollte die zu sortierende Folge in zwei möglichst gleich große Teilfolgen aufspalten.Gegeben sei eine unsortierte Folge mit n paarweise verschiedenen Elementen. Weiterhin sei r(x) die Position des Elements x in der sortierten Folge. Eine mögliche Strategie für die Pivotwahl ist:Wähle uniform zufällig 7 Elemente aus der Eingabefolge und gib das viertkleinste als Pivotelement aus. Dabei können Elemente in der Auswahl mehrmals vorkommen (Ziehen mit Zurücklegen)

.a) Berechne die Wahrscheinlichkeit für das Ereignis: n/4 < r(Pivot) ≤ 3n/4.

b) Nach wie vielen unabhängigen Wiederholungen der Pivotwahl ist zu erwarten, dass der Rang des Pivotelements das erste Mal außerhalb des Intervalls aus Aufgabenteil a) liegt? Hinweis: Du darfst annehmen, dass n= 4·kfür ein k∈N.

Aufgabe 2

Konstruiere eine Folge der Länge7, so dass Quickselect bei Verwendung der Pivotfunktionpivot(links, rechts) =⌈(links+rechts)/2⌉ auf der Suche nach dem viertgrößten Schlüssel die Problemgröße stets nur um 1verringert. Der Algorithmus soll insgesamt also sieben Schritte benötigen, bis er terminiert. Wende Quickselect auf Ihre Folge an, um die Korrektheit zu zeigen

Ansatz Ich verstehe hier nicht, wie n/4 gemeint ist. Wir hatten in der Vorlesung immer das Pivotelement ganz links oder ganz rechts. Jetzt steht hier "Pivot(links,rechts) = [(links+rechts)/2]. Greift man sich also da Element in der Mitte? Das ist bei einer Folge der Länge 7 doch nicht möglich, oder? WIe gehe ich allgemein vor um eine solche Folge zu finden.

Jensek81

...zur Frage

Themenbereiche Informatik - Eure Lieblingsthemen?

Es kann sein, dass ich nicht alles angegeben habe, aber dafür gibt es den Bereich "Anderes".

Danke Euch.

...zur Frage

LinkedList in Java sortieren beim Einfügen eines neuen Elements?

Ich habe hier den Code geschrieben, um ein neues Element einzufügen und danach die Liste zu sortieren.

Ich weiss, dass beides (Algorithmus für einfügen & Algorithmus fürs Sortieren) einzeln eigentlich funktionieren sollte. Aber die Kombination davon in einer Methode scheitert. Sieht jemand den Fehler.

Herzlichen Dank im Voraus!

...zur Frage

Wie begründet man die Anwendung der Sortieralgorithmen auf gegebene Beispiele?

Hallo liebes Forum,
ich versuche mich gerade etwas an dem Thema Sortieralgorithmen.
Die Theorie von Insertion Sort, Quicksort, Mergesort, Heapsort, Selection Sort, Bubblesort ist mir bekannt, habe auch jeden schon mal selbst programmiert und etwas getestet, nur war mir die Anwendung nie richtig klar.
Besser gesagt, wie und wann werden die außerhalb der Theorie verwendet.

Mir ist klar, dass man Insertion Sort und Selection Sort wegen ihrer mäßigen Worst Case Laufzeit nur für geringe Datenmengen einsetzt, bzw Insertion Sort auch, wenn die Daten schon vorher stark sortiert wurden.

Quicksort, Mergesort und Heapsort, weißen für großen Datenmengen die besten Laufzeiten auf, wobei man bei Quicksort darauf achten muss, das die zu sortierenden Elemente nicht schon sortiert sind, denn sonst geht die Laufzeit im Worst Case katastrophal nach oben. Weiter ist wenn es um die Speicherkapazität des Systems geht, Heapsort und vielleicht auch Qicksort zu bevorzugen, denn dank des speicherns der Ergebnisse auf ein Hilfsarray ist Mergesort ziemlich Speicher verbrauchend.

Nun habe ich diese ehemalige Klausuraufgabe aus einer Uni gefunden wobei es natürlich keine richtige Musterlösungen gab, sondern nur ein Hinweis (steht in Klammern), ich aber gerne einmal wüsste, wie man es richtig lösen könnte.

Aufgabe:

"Wählen Sie den effizientesten Algorithmus um diese Probleme zu lösen, begründen Sie außerdem ihre Entscheidung mittels der Kriterien Laufzeit und Stabilität.
Eine kurze Begründung ist ausreichend! "

An einer Verkehrskreuzung wurde über 10 Tage hinweg die Anzahl der Autos gezählt, die links abbiegen. Die Tageswerte liegen zwischen 10 und 2000 Autos. (SelectionSort)
An hunderten Wetterstationen Weltweit werden seit 1950 Temperaturwerte gesammelt. Die Werte werden auf ganze Zahlen gerundet. Der niedrigste Wert ist -89°C und der höchste 70°C. Insgesamt sind es ca. 1 Mrd. Werte. (CountSort)
Im Sonnensystem des Sterns "Sonne" gibt es 8 Planeten. Ihr Abstand zur "Sonne" ist zwischen 58 Mio. Km und 4495 Mio. Km. Die Planeten sollen Danach sortiert werden. (BubbleSort)
Ein Online-Shop hat ein Bewertungssystem für Seine Produkte, auf der Startseite sollen alle Produkte absteigend nach der Anzahl ihrer Bewertungen angezeigt werden. Diese Anzahl liegt in einem Array von Structs als Wert vor. Die Startseite soll jede Minute aktualisiert werden, somit wird der Algorithmus 1x pro Minute laufen. Da der Shop noch sehr klein ist, kommen selten neue Bewertungen zu Produkten dazu. (InsertionSort)
Ein neuer Zufallsgenerator hat 1 Mrd. Zahlen mit max. 512 Bit generiert. Um zu prüfen, wie gleichmäßig die Zahlen verteilt sind, sollen sie sortiert werden. (MergeSort)

Über eure Hilfe wäre ich sehr Dankbar

Lara

...zur Frage

Was genau ist der Unterschied zwischen einer For und einer While bzw Do While Schleife?

Ich verstehe noch nicht ganz was genau der unterschied ist. Eigentich könnte man doch mit allen drei Methoden dasselbe programmieren?

Bzw. kann mir jemand Anwendungsgebiete für die jeweiligen Schleifen nennen? Wofür man was am besten nutzt...

...zur Frage

Kann mir jemand helfen?

Ich soll ein Struktogramm für diese Aufgabenstellung erstellen: Erstellen Sie einen Algorithmus, der den Benutzer nach zwei Zahlen Z1 und Z2 fragt und der anschließend ausgibt, ob

• Z1 größer als Z1 ist, oder

• Z1 kleiner als Z2 ist, oder

• beide Zahlen gleich sind.

Mein Struktogramm sieht so aus:

Bei der Auswertung im Programm bekomme ich immer Fehler und ich weiß nicht was an meinem Struktogramm falsch ist:

...zur Frage

Komplexität von Funktion bestimmen?

Das ist die Funktion. Leider gibts für die Aufgabe keine Lösung, aber ich hätte gesagt, dass die innere Schleife log_2(n) Höchstens log_2(n) Durchläufe hat, weil k ja immer mindestens halbiert wird. Zusammen mit der äußeren Schleife wäre das n * log n

Aber die äußere Schleife macht ja eigentlich nichts, wenn k = 0 ist. Muss das n dann trotzdem mitberechnet werden oder würde hier auch ein log n reichen, sodass es auf log^2 n rauslaufen würde?

...zur Frage

Was möchtest Du wissen?

Deine Frage stellen