C-Sortieralgorithmus
Blasensortierung
Blasensortierung (englisch: Bubble Sort) ist ein einfacher Sortieralgorithmus. Er durchläuft die zu sortierende Liste wiederholt, vergleicht jeweils zwei Elemente und vertauscht sie, wenn sie in der falschen Reihenfolge sind (z. B. vom größten zum kleinsten oder beim ersten Buchstaben von A bis Z).
Ablaufdemonstration:
Beispiel
#include <stdio.h>
void bubble_sort(int arr[], int len);
int main() {
int arr[] = { 22, 34, 3, 32, 82, 55, 89, 50, 37, 5, 64, 35, 9, 70 };
int len = sizeof(arr) / sizeof(arr[0]);
bubble_sort(arr, len);
for (int i = 0; i < len; i++) {
printf("%d ", arr[i]);
}
return 0;
}
void bubble_sort(int arr[], int len) {
for (int i = 0; i < len - 1; i++) {
for (int j = 0; j < len - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
Auswahlsortierung
Die Auswahlsortierung ist ein einfacher und intuitiver Sortieralgorithmus. Ihr Funktionsprinzip ist wie folgt: Zuerst findet man das kleinste (oder größte) Element in der unsortierten Sequenz und platziert es an den Anfang der sortierten Sequenz. Dann sucht man weiter das kleinste (oder größte) Element aus den verbleibenden unsortierten Elementen und platziert es an das Ende der sortierten Sequenz. Und so weiter, bis alle Elemente sortiert sind.
Ablaufdemonstration:
Beispiel
#include <stdio.h>
void selection_sort(int a[], int len);
int main() {
int arr[] = { 22, 34, 3, 32, 82, 55, 89, 50, 37, 5, 64, 35, 9, 70 };
int len = sizeof(arr) / sizeof(arr[0]);
selection_sort(arr, len);
for (int i = 0; i < len; i++) {
printf("%d ", arr[i]);
}
return 0;
}
void selection_sort(int a[], int len) {
for (int i = 0; i < len - 1; i++) {
int min = i;
for (int j = i + 1; j < len; j++) {
if (a[j] < a[min]) {
min = j;
}
}
if (min != i) {
int temp = a[min];
a[min] = a[i];
a[i] = temp;
}
}
}
Insertionssortierung
Insertionssortierung (Englisch: Insertion Sort) ist ein einfacher und intuitiver Sortieralgorithmus. Ihr Funktionsprinzip besteht darin, eine geordnete Sequenz aufzubauen. Für unsortierte Daten wird in der sortierten Sequenz von hinten nach vorne gesucht, die passende Position gefunden und die Daten dort eingefügt. In der Implementierung verwendet die Insertionssortierung üblicherweise In-Place-Sortierung (das heißt, eine Sortierung, die nur {\displaystyle O(1)} {\displaystyle O(1)} zusätzlichen Speicherplatz benötigt). Daher ist es während des von hinten nach vorne verlaufenden Scanvorgangs erforderlich, die sortierten Elemente schrittweise wiederholt nach hinten zu verschieben.
Verschieben, um Platz für das neueste Element zu schaffen.
Ablaufdemonstration:
Beispiel
#include <stdio.h>
void insertion_sort(int arr[], int len);
int main() {
int arr[] = { 22, 34, 3, 32, 82, 55, 89, 50, 37, 5, 64, 35, 9, 70 };
int len = sizeof(arr) / sizeof(arr[0]);
insertion_sort(arr, len);
for (int i = 0; i < len; i++) {
printf("%d ", arr[i]);
}
return 0;
}
void insertion_sort(int arr[], int len) {
for (int i = 1; i < len; i++) {
int temp = arr[i];
int j = i;
while (j > 0 && arr[j - 1] > temp) {
arr[j] = arr[j - 1];
j--;
}
arr[j] = temp;
}
}
Shell-Sortierung
Die Shell-Sortierung, auch bekannt als Sortieralgorithmus mit abnehmendem Inkrement, ist eine effizientere verbesserte Version der Insertionssortierung. Die Shell-Sortierung ist ein instabiler Sortieralgorithmus.
Die Shell-Sortierung schlägt Verbesserungen basierend auf den folgenden zwei Eigenschaften der Insertionssortierung vor:
- Die Insertionssortierung ist hocheffizient, wenn sie auf Daten arbeitet, die fast schon sortiert sind, und kann die Effizienz der linearen Sortierung erreichen.
- Aber die Insertionssortierung ist im Allgemeinen ineffizient, weil die Insertionssortierung Daten nur um eine Position auf einmal bewegen kann.
Ablaufdemonstration:
Beispiel
#include <stdio.h>
void shell_sort(int arr[], int len);
int main() {
int arr[] = { 22, 34, 3, 32, 82, 55, 89, 50, 37, 5, 64, 35, 9, 70 };
int len = sizeof(arr) / sizeof(arr[0]);
shell_sort(arr, len);
for (int i = 0; i < len; i++) {
printf("%d ", arr[i]);
}
return 0;
}
void shell_sort(int arr[], int len) {
for (int gap = len / 2; gap > 0; gap /= 2) {
for (int i = gap; i < len; i++) {
int temp = arr[i];
int j = i;
while (j >= gap && arr[j - gap] > temp) {
arr[j] = arr[j - gap];
j -= gap;
}
arr[j] = temp;
}
}
}
Mergesort
Teile die Daten in zwei Segmente auf und wähle aus den beiden Segmenten nacheinander das kleinste Element aus und verschiebe es an das Ende des neuen Datensegments.
Kann von oben nach unten oder von unten nach oben durchgeführt werden.
Ablaufdemonstration:
Iterative Methode
#include <stdio.h>
#include <stdlib.h>
int min(int x, int y);
void merge_sort(int arr[], int len);
int main() {
int arr[] = { 22, 34, 3, 32, 82, 55, 89, 50, 37, 5, 64, 35, 9, 70 };
int len = sizeof(arr) / sizeof(arr[0]);
merge_sort(arr, len);
for (int i = 0; i < len; i++) {
printf("%d ", arr[i]);
}
return 0;
}
int min(int x, int y) {
return x < y ? x : y;
}
void merge_sort(int arr[], int len) {
int* a = arr;
int* b = (int*) malloc(len * sizeof(int));
if (b == NULL) {
fprintf(stderr, "Speicherzuweisung fehlgeschlagen\n");
exit(EXIT_FAILURE);
}
for (int seg = 1; seg < len; seg += seg) {
for (int start = 0; start < len; start += seg + seg) {
int low = start;
int mid = min(start + seg, len);
int high = min(start + seg + seg, len);
int k = low;
int start1 = low, end1 = mid;
int start2 = mid, end2 = high;
while (start1 < end1 && start2 < end2) {
b[k++] = a[start1] < a[start2] ? a[start1++] : a[start2++];
}
while (start1 < end1) {
b[k++] = a[start1++];
}
while (start2 < end2) {
b[k++] = a[start2++];
}
}
int* temp = a;
a = b;
b = temp;
}
if (a != arr) {
for (int i = 0; i < len; i++) {
b[i] = a[i];
}
b = a;
}
free(b);
}
Rekursive Methode
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
void merge_sort_recursive(int arr[], int reg[], int start, int end);
void merge_sort(int arr[], const int len);
int main() {
int arr[] = { 22, 34, 3, 32, 82, 55, 89, 50, 37, 5, 64, 35, 9, 70 };
int len = sizeof(arr) / sizeof(arr[0]);
merge_sort(arr, len);
for (int i = 0; i < len; i++) {
printf("%d ", arr[i]);
}
return 0;
}
void merge_sort_recursive(int arr[], int reg[], int start, int end) {
if (start >= end)
return;
int mid = start + (end - start) / 2;
int start1 = start, end1 = mid;
int start2 = mid + 1, end2 = end;
merge_sort_recursive(arr, reg, start1, end1);
merge_sort_recursive(arr, reg, start2, end2);
int k = start;
while (start1 <= end1 && start2 <= end2) {
reg[k++] = arr[start1] < arr[start2] ? arr[start1++] : arr[start2++];
}
while (start1 <= end1) {
reg[k++] = arr[start1++];
}
while (start2 <= end2) {
reg[k++] = arr[start2++];
}
memcpy(arr + start, reg + start, (end - start + 1) * sizeof(int));
}
void merge_sort(int arr[], const int len) {
int* reg = (int*)malloc(len * sizeof(int));
if (reg == NULL) {
fprintf(stderr, "Speicherzuweisung fehlgeschlagen\n");
exit(EXIT_FAILURE);
}
merge_sort_recursive(arr, reg, 0, len - 1);
free(reg);
}
Quicksort
Wähle zufällig ein Element im Intervall als Pivot, platziere Elemente kleiner als der Pivot vor dem Pivot und Elemente größer als der Pivot nach dem Pivot, sortiere dann den Bereich der kleinen Elemente und den Bereich der großen Elemente getrennt.
Ablaufdemonstration:
Iterative Methode
#include <stdio.h>
typedef struct _Range {
int start, end;
} Range;
Range new_Range(int s, int e) {
Range r;
r.start = s;
r.end = e;
return r;
}
void swap(int *x, int *y) {
int t = *x;
*x = *y;
*y = t;
}
void quick_sort(int arr[], const int len) {
if (len <= 0)
return;
Range r[len];
int p = 0;
r[p++] = new_Range(0, len - 1);
while (p > 0) {
Range range = r[--p];
if (range.start >= range.end)
continue;
int mid = arr[(range.start + range.end) / 2];
int left = range.start, right = range.end;
do {
while (arr[left] < mid) ++left;
while (arr[right] > mid) --right;
if (left <= right) {
swap(&arr[left], &arr[right]);
left++;
right--;
}
} while (left <= right);
if (range.start < right) r[p++] = new_Range(range.start, right);
if (range.end > left) r[p++] = new_Range(left, range.end);
}
}
int main() {
int arr[] = {22, 34, 3, 32, 82, 55, 89, 50, 37, 5, 64, 35, 9, 70};
int len = sizeof(arr) / sizeof(arr[0]);
quick_sort(arr, len);
for (int i = 0; i < len; i++) {
printf("%d ", arr[i]);
}
return 0;
}
Rekursive Methode
#include <stdio.h>
void swap(int *x, int *y) {
int t = *x;
*x = *y;
*y = t;
}
void quick_sort_recursive(int arr[], int start, int end) {
if (start >= end)
return;
int mid = arr[end];
int left = start, right = end - 1;
while (left < right) {
while (left < right && arr[left] < mid)
left++;
while (left < right && arr[right] >= mid)
right--;
swap(&arr[left], &arr[right]);
}
if (arr[left] >= arr[end])
swap(&arr[left], &arr[end]);
else
left++;
quick_sort_recursive(arr, start, left - 1);
quick_sort_recursive(arr, left + 1, end);
}
void quick_sort(int arr[], int len) {
quick_sort_recursive(arr, 0, len - 1);
}
int main() {
int arr[] = {22, 34, 3, 32, 82, 55, 89, 50, 37, 5, 64, 35, 9, 70};
int len = sizeof(arr) / sizeof(arr[0]);
quick_sort(arr, len);
for (int i = 0; i < len; i++) {
printf("%d ", arr[i]);
}
return 0;
}
Weitere Erweiterungen