Einführung in das Sortieren in C ++

Wenn eine Sammlung von Elementen sortiert werden muss, hilft das Sortieren beim Anordnen der Elemente im Datensatz basierend auf der Sortierbeziehung. Stellen Sie sich einen Dateidatensatz vor, der viele Informationen enthält. Um auf eine Liste aus dem Datensatz zuzugreifen, muss ein Schlüsselfeld vorhanden sein, das auf die aktuelle Position des Elements verweist. Betrachten Sie beispielsweise eine Liste mit Namen in der Datenbank, die alphabetisch sortiert sein kann. Die Sortierung spielte im Bereich Computer und Technik eine wichtige Rolle. Lassen Sie uns mehr in diesem Artikel sehen.

Was ist die Sortierung in C ++?

Sortieren ist das Grundkonzept, das der Programmierer oder Forscher verwendet, um die erforderlichen Eingaben zu sortieren. Die Reihenfolge der Komplexität ist durch 0 (N * log (N)) gegeben. Das Sortieren einer Eingabe erleichtert das Lösen vieler Probleme wie Suchen, Maximum und Minimum. Obwohl eine Sortierung Daten in der Reihenfolge anordnet, ist die Effizienz des Prozesses sehr wichtig, die auf zwei Kriterien basiert: - Zeit und Speicher, die für die Sortierung der angegebenen Daten erforderlich sind. Die Zeit wird durch Zählen der Vergleiche der verwendeten Schlüssel gemessen. Zum Sortieren stehen viele Algorithmen zur Verfügung. Im Allgemeinen unterscheidet man beim Sortieren in C ++ zwei Typen:

  1. Interne Sortierung
  2. Externe Sortierung

Syntax und Beispiel

Syntax:

C ++ verwendet die in sort () integrierte Funktion für ihre Algorithmen, um die Container wie Vektoren und Arrays zu sortieren.

Sortieren (Array, Array + Größe);

Beispiele:

#include
using namespace std;
int main ()
(
int ins(12) = ( 19, 13, 5, 27, 1, 26, 31, 16, 2, 9, 11, 21);
cout<<"\nInput list is \n";
for(int i=0;i<12;i++)
(
cout < )
for(int k=1; k<12; k++)
(
int t = ins(k);
int j= k-1;
while(j>=0 && t <= ins(j))
(
ins(j+1) = ins(j);
j = j-1;
)
ins(j+1) = t;
)
cout<<"\nSorted list is \n";
for(int i=0;i<12;i++)
(
cout < )
) #include
using namespace std;
int main ()
(
int ins(12) = ( 19, 13, 5, 27, 1, 26, 31, 16, 2, 9, 11, 21);
cout<<"\nInput list is \n";
for(int i=0;i<12;i++)
(
cout < )
for(int k=1; k<12; k++)
(
int t = ins(k);
int j= k-1;
while(j>=0 && t <= ins(j))
(
ins(j+1) = ins(j);
j = j-1;
)
ins(j+1) = t;
)
cout<<"\nSorted list is \n";
for(int i=0;i<12;i++)
(
cout < )
) #include
using namespace std;
int main ()
(
int ins(12) = ( 19, 13, 5, 27, 1, 26, 31, 16, 2, 9, 11, 21);
cout<<"\nInput list is \n";
for(int i=0;i<12;i++)
(
cout < )
for(int k=1; k<12; k++)
(
int t = ins(k);
int j= k-1;
while(j>=0 && t <= ins(j))
(
ins(j+1) = ins(j);
j = j-1;
)
ins(j+1) = t;
)
cout<<"\nSorted list is \n";
for(int i=0;i<12;i++)
(
cout < )
)

Ausgabe:

Wie funktioniert es?

Zunächst nehmen wir Quick Sort, eine wichtige Methode unter den verschiedenen Sortierungsarten. Die grundlegende Sortierung eines Arrays erfolgt nach einem Quicksort-Ansatz. Es gibt verschiedene Möglichkeiten, die Sortierung zu implementieren. Ziel jeder dieser Techniken ist es, zwei Elemente zu vergleichen und sie mit der temporären Variablen zu tauschen. In diesem Artikel werden wir die wichtigsten Sortierungen behandeln, die für die Implementierung verwendet werden. Folgende sind:

  1. Bubble Sort
  2. Sortieren durch Einfügen
  3. Schnelle Sorte
  4. Auswahl sortieren

Es gibt Merge-Sortierung, Radix-Sortierung und Bandsortierung, auf die wir später noch eingehen werden. Zuerst werden wir mit Bubble sort gehen.

1. Bubble Sort

Die Blasensortierung ist eine der einfachsten Sortiermethoden, die wir für Anwendungen verwenden können. Bei dieser Technik werden aufeinanderfolgende Auslagerungen durch die zu sortierenden Datensätze vorgenommen. Bei jedem Schritt wird der Schlüssel mit den Daten verglichen und die Elemente ausgetauscht, wenn nicht in der gewünschten Reihenfolge. Die Sortierung erfolgt mit den benachbarten Elementen, wenn nach einem Tausch nur ein Element an der sortierten Stelle platziert wird.

Beispiel: Betrachten wir ein unsortiertes Array A () = (6, 2, 4, 7, 1)

62471
A (0)A (1)A (2)A (3)A (4)

Schritt 1: Vergleichen Sie A (0)> A (1). Wenn die Bedingung erfüllt ist, tauschen Sie das Element (6> 2) aus, und setzen Sie 2 in A (0). In ähnlicher Weise sind alle Schritte gleich, bis das Array sortiert ist.

Jetzt ist das Array A () = (2, 6, 4, 7, 1)

Schritt 2: 6 wird mit 4 verglichen. Da 6 größer als 4 ist, werden 6 und 4 getauscht.

Jetzt ist das Array A () = (2, 4, 6, 7, 1)

Schritt 3: Element 6 wird mit 7 verglichen. Da 6 <2 und die Elemente in aufsteigender Reihenfolge sind, werden die Elemente nicht ausgetauscht.

Das sortierte Array ist A () = (2, 4, 6, 7, 1).

Setzen Sie den Vorgang fort, bis das Array sortiert ist.

2. Insertion Sort

Bei dieser Technik beginnen wir mit dem zweiten Datenelement, indem wir davon ausgehen, dass das erste Element bereits sortiert ist und der Vergleich mit dem zweiten Element erfolgt und der Schritt mit dem anderen nachfolgenden Element fortgesetzt wird. In einem Array von N Elementen ist es erforderlich, N-1 Durchgänge zu haben, um ein sortiertes Element zu haben.

Betrachten Sie ein Array A () = (8, 3, 6, 1)

8361

Schritt 1: Das erste Element sucht nach dem größten auszutauschenden Element im Array. Wenn es größer ist, bleibt es gleich und wird zum zweiten Element verschoben, hier ist 8 größer als alles, es wird kein Swap durchgeführt.

8361

Schritt 2: Mit dem zweiten Element tauschen

3861

Schritt 3: Mit dem dritten Element tauschen

3681

Schritt 4: Tauschen Sie mit dem vierten Element

1368

3. Schnelle Sortierung

Diese Technik folgt dem Divisions- und Eroberungsalgorithmus und wird für große Arrays als sehr effizient und schneller angesehen. Sie sind in drei Unterabschnitte unterteilt: einen linken, einen rechten und den mittleren. Das mittlere Element hat einen einzelnen Wert und wird als Drehpunkt bezeichnet. Der Mechanismus funktioniert folgendermaßen: Das Element im linken Segment sollte keinen Schlüssel haben, der größer als das mittlere Element ist, und das Element no im rechten Segment sollte einen Schlüssel haben, der kleiner als der des mittleren Elements ist. Beginnen wir nun mit einer Illustration des Sortierprozesses. Quicksort verwendet ein rekursives Konzept beim Sortieren von Unterteilen. Das Array ist in Unterteile unterteilt, wobei wiederum das linke und das rechte Segment durch Eroberung aufgeteilt werden. Hier in diesem Beispiel unter Berücksichtigung, dass das letzte Element einen Drehpunkt hat und das erste Element als niedrig angenommen wird. Betrachten Sie ein Array-Element

492211165630

Wenn Sie das Element ganz rechts nehmen, ist das Pivot-Element = 30

162211305649

Das Element, das größer als der Drehpunkt ist, wird nach links und rechts kleiner platziert.

1622115649

Der Zeiger befindet sich am Drehpunkt und ist um einen Drehpunkt herum unterteilt.

1122165649

Die Unterteile sind einzeln sortiert.

111622304956

Schließlich haben wir ein sortiertes Array.

4. Auswahl sortieren

Diese Technik wird auch als Austauschsortierung bezeichnet und führt eine Suche und Sortierung mit zwei Operationen durch. Die Implementierung nimmt eine direkte Auswahlsortierung vor, wie unten definiert. Hier ist es erforderlich, das kleinste im Array vorhandene Element zu identifizieren, und dieses Element wird an der ersten i-ten Position sortiert. Als nächstes wird das zweitkleinste Element identifiziert und es wird an der zweiten Position sortiert. Die Auswahlsortierung verlässt ihre Schleife, wenn der unsortierte Unterabschnitt leer wird. Die Zeitkomplexität wird als O (n 2 ) angegeben.

Betrachten Sie das folgende Array:

6326132312

1. Finden Sie das kleinste Element und platzieren Sie es am Anfang und es wird mit der Position vertauscht.

1226132363

2. Das zweite Element a (1) wird identifiziert, mit dem minimalen Element verglichen und in die zweite Position gebracht. In ähnlicher Weise wird der Durchgang fortgesetzt.

1213262364

Endgültige sortierte Ausgabe

1213232664

Fazit

Abschließend ging es in diesem Artikel um Sortierkonzepte und deren Funktionsweise. Alle diese Sortiertechniken verwenden Parallelverarbeitungskonzepte. Die Sortierung bildet einen zentralen Baustein bei der Strukturierung von Algorithmen, um die Probleme der Daten in der realen Welt zu lösen, indem die Wertemenge nach den Anforderungen sortiert wird.

Empfohlene Artikel

Dies ist eine Anleitung zum Sortieren in C ++. Hier diskutieren wir die Einführung und Syntax mit Beispielen und wie es funktioniert. Sie können auch unsere anderen Artikelvorschläge durchgehen, um mehr zu erfahren.

  1. Sortieren in Tableau
  2. Iterator in C ++
  3. Array-Funktionen in C
  4. Heap-Sortierung in C
  5. Wie wird in PHP sortiert?
  6. Heap-Sortierung in Python
  7. Iterator in Java
  8. Top 11 Features und Vorteile von C ++
  9. Iterator in Python | Vorteile und Beispiele von Python

Kategorie:

Software-Entwicklung