06ex

/*
Zur Abgabe einen branch `iprg-b06` erstellen und pushen, in dem als einzige Datei die `06ex.c` liegt.
*/

/*
Um die Tests für dieses Blatt zu kompilieren und zu starten, führen Sie den folgenden Befehl aus:
cc -std=c11 -g -Wall -Werror 06ex_test.c -o 06ex_test.o -lm && ./06ex_test.o

Wir empfehlen, mit möglichst streng eingestelltem valgrind zu testen, denn so testen wir auch auf dem Server:
cc -std=c11 -g -Wall -Werror 06ex_test.c -o 06ex_test.o -lm && valgrind --leak-check=full --show-leak-kinds=all --track-origins=yes ./06ex_test.o
*/

#include "array_visualizer.h"
#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>

/*
Aufgabe 1:
Machen Sie sich in dieser Aufgabe mit dem `Visualizer` (siehe array_visualizer.h) vertraut.
Nutzen Sie die `visualizer_append_array` Funktion damit die Tests durchlaufen.

Tipp 1: Die erste Zeile im erzeugten Bild stellt das Eingabearray dar.
*/
void warmup(Visualizer *v, uint8_t *arr, size_t len) {

    for(int i = 0; i < len; i++){
        visualizer_append_array(v,arr);
        uint8_t first = arr[0];
        for(int j = 0; j < len; j++){
            arr[j] = arr[j+1];
        }
        arr[len-1] = first;
    }

}

/*
Aufgabe 2:
Bringen Sie die Tests zum durchlaufen.

Tipp 1: Die erste Zeile im erzeugten Bild stellt das Eingabearray dar.
Tipp 2: Es handelt sich um eine Abwandlung von iterativem Mergesort.
Tipp 3: `len` ist immer eine Dreierpotenz, damit Sie sich nicht mit Rundungsdetails herumschlagen brauchen.
*/

void merge_3_arrays(uint8_t* arrA, uint8_t p, uint8_t r1, uint8_t r2, uint8_t r3){ //zusammenfuegen von arrays arrA[p, ... , r1], arrA[r1+1, ... , r2], arrA[r2+1, ... , r3]

    printf("\n start merge\n");

    int len = r3-p+1;

    uint8_t arrB[len]; //hilfsarray
    uint8_t i = p, j = r1+1, k = r2+1;
    int b = 0; //counter fuer array B

    uint8_t min; //hilfsvariable fuer die kleinste (von drei) zahl
    int min_pos; //zeigt an, aus welchem array teil diese zahl genommen wird (um in diesem arraysteil den counter zu erhoehen)

    while(i<=r1 && j<=r2 && k<=r3){ //solange eintraege af allen 3 seiten

        //erster vergleich
        if(arrA[i] <= arrA[j]){
            min = arrA[i];
            min_pos = 1; //aus dem ersten teil des arrays genommen
        }
        else{
            min = arrA[j];
            min_pos = 2; //aus dem zweiten teil des arrays genommen
        }

        //zweiter vergleich
        if(arrA[k] <= min){
            min = arrA[k];
            min_pos = 3; //aus dem dritten teil des arrays genommen
        }
        /*else{
            min = min;
            min_pos = min_pos;
        }
        */

        //kleinste zahl gefunden, nun in den hilfsarray hinschreiben

        arrB[b] = min;
        printf("schreibe in array: %d\n", min);
        b++; // counter fuer arrB erhoehen

        //welcher counter fuer arrA muss erhoeht werden?
        if(min_pos == 1) i++;
        else if(min_pos == 2) j++;
        else k++;

    }

    //wenn man aus der schleife austritt, kann das aus 3 gruenden passieren: i>r1, j>r2, k>r3 (oder kombi von diesen drei)
    //wir betrachten also (solange es sie noch gibt) die ungemergten arrays teile, die nun nicht 3 sondern maximal 2 sind
    //das ist gleich wie 2 arrays zu mergen und das koennen wir bereits

    // Situation (a) : i > r1
    while(j<=r2 && k<=r3){
        if(arrA[j] <= arrA[k]){
            arrB[b] = arrA[j];
            printf("schreibe in array: %d\n", arrA[j]);
            j++;
        }
        else{
            arrB[b] = arrA[k];
            printf("schreibe in array: %d\n", arrA[k]);

            k++;
        }
        b++;
    }

    // Situation (b) : j > r2
    while(i<=r1 && k<=r3){
        if(arrA[i] <= arrA[k]){
            arrB[b] = arrA[i];
            printf("schreibe in array: %d\n", arrA[i]);

            i++;
        }
        else{
            arrB[b] = arrA[k];
            printf("schreibe in array: %d\n", arrA[k]);

            k++;
        }
        b++;
    }

    // Situation (c) : k > r3
    while(i<=r1 && j<=r2){
        if(arrA[i] <= arrA[j]){
            arrB[b] = arrA[i];
            printf("schreibe in array: %d\n", arrA[i]);
            i++;
        }
        else{
            arrB[b] = arrA[j];
            printf("schreibe in array: %d\n", arrA[j]);
            j++;
        }
        b++;
    }

    //nach diesen manipulationen sind zumindest 2 arraysteile in den hilfsarray kopiert, es kann aber sein dass noch irwelche eintraege uebrig geblieben sind

    //Eintraege im ersten array teil
    while(i<=r1){
        arrB[b] = arrA[i];
        printf("schreibe in array: %d\n", arrA[i]);
        b++;
        i++;
    }

    //Eintraege im zweiten array teil
    while(j<=r2){
        arrB[b] = arrA[j];
        printf("schreibe in array: %d\n", arrA[j]);
        b++;
        j++;
    }

    //Eintraege im dritten array teil
    while(k<=r3){
        arrB[b] = arrA[k];
        printf("schreibe in array: %d\n", arrA[k]);
        b++;
        k++;
    }


    printf("\n array B:\n");
    for(int t = 0; t<len; t++){
        printf("B[%d] = %d\n", t, arrB[t]);
    }

    //nun sind alle eintraege nach arrB zugewiesen und arrB kann in arrA kopiert werden



    int help_counter = 0;
    for(int q = p; q<=r3; q++){

        arrA[q] = arrB[help_counter];
        help_counter++;
    }

    printf("\n array A :\n");
    for(int t = p; t<=r3; t++){
        printf("A[%d] = %d\n", t, arrA[t]);
    }

}

void sort_it(Visualizer *v, uint8_t *arr, size_t len) {

    visualizer_append_array(v,arr);

    int r1,r2,r3; //hilsvariablen fuer arraygrenzen
    int step = 1; //erstmal : drei arrays laenge 1 (step = 1), dann - 3 arrays laenge 3 (step = 3)
    while(step < len){
        int left = 0; //linke grenze initialisiert

        while(left <= len - step){ //sortieren

            r1 = left+step-1; // erste rechte grenze
            r2 = left+2*step-1; // zweite rechte grenze
            r3 = left+3*step-1; // dritte rechte grenze

            //nun muessen wir drei arrays laenge step zusammenfuegen
            merge_3_arrays(arr, left, r1, r2, r3);
            visualizer_append_array(v,arr);
            left = left+3*step; // linke grenze verschieben
        }

        step = step*3;
    }
}