Aufgabe 5

Schwierigkeitsgrad: Mittel

Themen: Programmausgabe Kontrollstrukturen Zeiger Arrays Rekursion

---

Aufgabenstellung

Erstellen Sie ein Array mit Zufallszahlen und sortieren Sie es mit verschiedenen Allgorithmen. Schreiben sie eine Funktion die das Array erstellt und initialisiert. Implementieren Sie eine Funktion, die das Array ausgibt. Alle Funktionen in dieser Aufgabe sollen den Rückgabetyp void haben, also nichts zurückgeben. Nutzen Sie Zeiger und dynamische Speicherverwaltung.

info

Hinweis: Nutzen Sie int a = rand() % 20 um ihr Array mit Zufallszahlen von 0 bis 19 zu initialisieren.

Implementieren Sie die folgenden Sortierallgorithmen in eigenen Funktionen und testen Sie diese:

1. Selection Sort (Erklärungen: Wikipedia,Studyflix) (manchmal auch Min-/Maxsort) ist ein Allgorithmus, der durch das Array läuft und das kleinste (bzw. größte) Element sucht. Dies tauscht er dann mit dem ersten Element. Dann wiederholt sich der Prozess für das Array ab dem zweiten Element und der Allgorithmus sucht das nächstkleinste Element und tauscht es an die zweite Stelle... Implementieren Sie das Tauschen in einer eigenen Funktion, übergeben Sie die Variablem mit Zeigern.
2. Insertion Sort (Erklärungen: Wikipedia, Studyflix) ist ein Algorithmus, der für jedes Element schaut, ob es kleiner ist als seine Vorgänger. Wenn ja, dann wandert das Element weiter vor, bis die Bedingung nicht mehr erfüllt ist. Jedes Element wird so an die richtige Stelle einsortiert. Der Allgorithmus startet mit dem zweiten Element.
3. Merge Sort (Erklärungen: Wikipedia, Studyflix) ist ein Algorithmus der das Array mittels Rekursion immer wieder in der Mitte teilt und dann die Teile in der Richtigen Reihenfolge wieder zusammensetzt.

Lösung

#include <iostream>
using std::cout, std::endl;

#define ARRAY_SIZE 20

void init(int **array)
{
    *array = new int[ARRAY_SIZE];
    for (int i = 0; i < ARRAY_SIZE; i++)
    {
        (*array)[i] = rand() % 20;
    }
}

void print_array(int *array)
{
    for (int i = 0; i < ARRAY_SIZE; i++)
    {
        cout << array[i] << " ";
    }
    cout << endl;
}

void swap(int *a, int *b)
{
    int tmp = *a;
    *a = *b;
    *b = tmp;
}

void selection_sort(int *array)
{
    for (int i = 0; i < ARRAY_SIZE; i++)
    {
        int min = i;
        for (int j = i; j < ARRAY_SIZE; j++)
        {
            if (array[j] < array[min])
                min = j;
        }
        swap(&array[i], &array[min]);
    }
}

void insertion_sort(int *array)
{
    for (int i = 1; i < ARRAY_SIZE; i++)
    {
        int key = array[i];
        int j = i - 1;
        while (j >= 0 && array[j] > key)
        {
            array[j + 1] = array[j];
            j--;
        }
        array[j + 1] = key;
    }
}

void merge_sort(int *array, int left = 0, int right = ARRAY_SIZE - 1)
{
    if (left >= right)
        return;
    int mid = left + (right - left) / 2;
    merge_sort(array, left, mid);
    merge_sort(array, mid + 1, right);

    int size_left = mid - left + 1;
    int size_right = right - mid;

    int *L = new int[size_left];
    int *R = new int[size_right];

    for (int i = 0; i < size_left; i++)
        L[i] = array[left + i];
    for (int j = 0; j < size_right; j++)
        R[j] = array[mid + 1 + j];

    int i = 0;
    int j = 0;
    int k = left;

    while (i < size_left && j < size_right)
    {
        if (L[i] <= R[j])
        {
            array[k] = L[i];
            i++;
        }
        else
        {
            array[k] = R[j];
            j++;
        }
        k++;
    }

    while (i < size_left)
    {
        array[k] = L[i];
        i++;
        k++;
    }

    while (j < size_right)
    {
        array[k] = R[j];
        j++;
        k++;
    }

    delete[] L;
    delete[] R;
}

int main()
{
    int *array = nullptr;
    cout << "Selection Sort " << endl;
    init(&array);
    print_array(array);
    selection_sort(array);
    print_array(array);
    cout << "Insertion Sort " << endl;
    init(&array);
    print_array(array);
    insertion_sort(array);
    print_array(array);
    cout << "Merge Sort " << endl;
    init(&array);
    print_array(array);
    merge_sort(array);
    print_array(array);
}

---