selection sort java selection sort algorithm examples
In diesem Tutorial wird alles über die Auswahlsortierung in Java zusammen mit dem Auswahlsortierungsalgorithmus, dem Java-Code, der Implementierung in Java und Java-Beispielen erläutert:
Die Auswahlsortiertechnik ist eine Methode, bei der das kleinste Element im Array ausgewählt und gegen das erste Element des Arrays ausgetauscht wird. Als nächstes wird das zweitkleinste Element im Array mit dem zweiten Element ausgetauscht und umgekehrt.
=> Hier finden Sie A-Z der Java-Schulungsanleitungen.
Was du lernen wirst:
Auswahl In Java sortieren
Auf diese Weise wird das kleinste Element im Array wiederholt ausgewählt und an die richtige Position gebracht, bis das gesamte Array sortiert ist.
Für die Auswahlsortierung werden zwei Unterarrays verwaltet:
- Sortiertes Subarray: In jeder Iteration wird das minimale Element gefunden und an der richtigen Position platziert. Dieses Subarray ist sortiert.
- Unsortiertes Subarray: Die restlichen Elemente, die nicht sortiert sind.
Die Auswahlsortierung ist eine einfache und einfache Sortiertechnik. Bei dieser Technik wird nur das kleinste Element in jedem Durchgang gefunden und an der richtigen Position platziert. Die Auswahlsortierung ist ideal für kleinere Datensätze, da sie den kleineren Datensatz effizient sortiert.
Daher können wir sagen, dass eine Auswahlsortierung für größere Datenlisten nicht ratsam ist.
Auswahl-Sortier-Algorithmus
Der allgemeine Algorithmus für die Auswahlsortierung ist unten angegeben:
Auswahlsortierung (A, N)
Schritt 1 : Wiederholen Sie die Schritte 2 und 3 für K = 1 bis N-1
Schritt 2 : Routine kleinste aufrufen (A, K, N, POS)
Schritt 3 ::
Tauschen Sie A (K) gegen A (POS)
(Ende der Schleife)
Schritt 4 : AUSFAHRT
Routine kleinste (A, K, N, POS)
Schritt 1 : (initialisieren) set smallItem = A (K)
Schritt 2 : (initialisieren) setze POS = K.
Schritt 3 ::
für J = K + 1 bis N -1 wiederholen
wenn kleinstes Element> A (J)
setze kleinstes Element = A (J)
setze POS = J.
(wenn Ende)
(Ende der Schleife)
Schritt 4 : POS zurückgeben
Wie Sie sehen können, wird die Routine zum Finden der kleinsten Zahl beim Durchlaufen des Datensatzes aufgerufen. Sobald das kleinste Element gefunden ist, wird es in die gewünschte Position gebracht.
wie man eine jnlp-Datei öffnet
Pseudocode für Auswahlsortierung
Der Pseudocode für den Auswahlsortieralgorithmus ist unten angegeben.
Procedure selection_sort(array,N) array – array of items to be sorted N – size of array begin for I = 1 to N-1 begin set min = i for j = i+1 to N begin if array(j) Lassen Sie uns nun die Sortierung eines Arrays mithilfe der Auswahlsortierung veranschaulichen.
Beispiel für eine Auswahlsortierung
Betrachten Sie das folgende Array, das sortiert werden soll, als Beispiel für eine Auswahlsortierung.
Nachstehend finden Sie eine tabellarische Darstellung zur Veranschaulichung:
Unsortierte Liste Kleinstes Element Sortierte Liste {17,10,7,29,2} zwei {} {17,10,7,29} 7 {zwei} {17,10,29} 10 {2.7} {17.29} 17 {2,7,10) {29} 29 {2,7,10,17} {} {2,7,10,17,29}
Aus der Abbildung geht hervor, dass bei jedem Durchgang das nächstkleinere Element im sortierten Array an die richtige Position gebracht wird. Im Allgemeinen benötigen wir zum Sortieren eines Arrays von N Elementen insgesamt N-1 Durchgänge.
Implementierung der Auswahlsortierung in Java
Lassen Sie uns nun das Java-Programm zur Implementierung der Auswahlsortierung demonstrieren.
import java.util.*; class Main { static void sel_sort(int numArray()) { int n = numArray.length; // traverse unsorted array for (int i = 0; i Ausgabe:
Ursprüngliches Array: (7, 5, 2, 20, 42, 15, 23, 34, 10)
Sortiertes Array: (2, 5, 7, 10, 15, 20, 23, 34, 42)
Im obigen Java-Beispiel finden wir wiederholt das kleinste Element im Array und fügen es in das sortierte Array ein, bis das gesamte Array vollständig sortiert ist.
Auswahl Sortierte verknüpfte Liste In Java
Unten ist eine verknüpfte Liste angegeben, die wir mithilfe der Auswahlsortierung sortieren müssen. Dazu verwenden wir den rekursiven Ansatz der Auswahlsortierung. Anstatt den Datenteil des Knotens auszutauschen, werden wir die Knoten austauschen und die Zeiger neu ausrichten.
Wenn also die verknüpfte Liste wie folgt angegeben ist:
kostenlose Versionskontrollsoftware für Windows
Unten ist das Java-Programm angegeben, das die obige Sortierung implementiert.
// add a node to the beginning of the linked list static Node addNode( Node head_ref, int new_data) { // create a node Node newNode = new Node(); // assign data to node newNode.data = new_data; // link the node to linked list newNode.next = (head_ref); //head now points to new node (head_ref) = newNode; return head_ref; } // method to swap nodes static Node swapNodes( Node head_ref, Node curr_node1, Node curr_node2, Node prev_node) { // curr_node2 is new head head_ref = curr_node2; // realign links prev_node.next = curr_node1; // now swap next pointers of nodes Node temp = curr_node2.next; curr_node2.next = curr_node1.next; curr_node1.next = temp; return head_ref; } // sort the linked list using selection sort static Node Selection_Sort( Node head) { // only a single node in linked list if (head.next == null) return head; // minNode => node with minimum data value Node minNode = head; // prevMin => node previous to minNode Node prevMin = null; Node ptr; // traverse the list from head to last node for (ptr = head; ptr.next != null; ptr = ptr.next) { // check if current node is minimum if (ptr.next.data Ausgabe:
Ursprüngliche verknüpfte Liste:
7 9 3 5 1 11
Verknüpfte Liste nach dem Sortieren:
1 3 5 7 9 11
Beachten Sie, dass wir im obigen Programm die Verknüpfungen der Knoten neu ausgerichtet haben, anstatt nur die Datenkomponente des Knotens zu sortieren.
Häufig gestellte Fragen
F # 1) Wie funktioniert die Auswahlsortierung?
Antworten: Die Auswahlsortierung funktioniert durch Verwalten von zwei Unterarrays. Das minimale Element aus dem unsortierten Subarray wird in einem sortierten Subarray an der richtigen Position platziert. Dann wird das zweitniedrigste Element in die richtige Position gebracht. Auf diese Weise wird das gesamte Array sortiert, indem bei jeder Iteration ein Mindestelement ausgewählt wird.
Q # 2) Was ist die Komplexität der Auswahlsorte?
Antworten: Die Gesamtkomplexität der Auswahlsortierung ist O (nzwei), wodurch es zum Algorithmus wird, der bei größeren Datenmengen ineffizient ist. Andere Sortiertechniken sind effizienter.
Q # 3) Was sind die Vor- und Nachteile der Auswahlsorte?
Antworten: Die Auswahlsortierung ist die In-Place-Sortiertechnik und erfordert daher keinen zusätzlichen Speicher zum Speichern von Zwischenelementen.
Es arbeitet effizient mit kleineren Datenstrukturen sowie den Datensätzen, die fast sortiert sind.
Der Hauptnachteil der Auswahlsortiertechnik besteht darin, dass sie mit zunehmender Größe der Datenstruktur sehr schlecht funktioniert. Es wird nicht nur langsamer, sondern verringert auch die Effizienz.
Q # 4) Wie viele Swaps gibt es in der Auswahlsorte?
Antworten: Die Auswahlsortiertechnik erfordert die minimale Anzahl von Swaps. Wenn das Array sortiert ist, beträgt die Anzahl der Swaps in der Auswahlsortierung im besten Fall 0.
Q # 5) Ist die Auswahlsortierung schneller als die Einfügesortierung?
Antworten: Die Sortierung nach Einfügungen ist schneller und effizienter sowie stabiler. Die Auswahlsortierung ist nur für kleinere Datensätze und teilweise sortierte Strukturen schneller.
Fazit
Die Auswahlsortierung ist eine Technik, bei der das minimale Element beim Durchlaufen des Arrays ausgewählt wird. Für jeden Durchgang / jede Iteration wird das nächste minimale Element im Datensatz ausgewählt und an der richtigen Position platziert.
Die Auswahlsortiertechnik arbeitet effizient, wenn die Anzahl der Elemente im Datensatz kleiner ist, aber mit zunehmender Größe des Datensatzes beginnt sie eine schlechte Leistung zu erzielen. Es wird ineffizient im Vergleich zu anderen ähnlichen Techniken wie dem Einfügen.
In diesem Tutorial haben wir Beispiele implementiert, um Arrays und verknüpfte Listen mithilfe der Auswahlsortierung zu sortieren.
=> Besuchen Sie hier, um die Java-Schulungsreihe für alle zu sehen.
Literatur-Empfehlungen
- So sortieren Sie ein Array in Java - Tutorial mit Beispielen
- Auswahl In C ++ mit Beispielen sortieren
- Java Array Length Tutorial mit Codebeispielen
- MongoDB Sort () -Methode mit Beispielen
- Jagged Array In Java - Tutorial mit Beispielen
- Unix-Sortierbefehl mit Syntax, Optionen und Beispielen
- Ein Array in Java umkehren - 3 Methoden mit Beispielen
- JAVA-Tutorial für Anfänger: Über 100 praktische Java-Video-Tutorials
