/*
Selection Sort (naive sort)   Time complexity   O(n^2)

scorro lungo tutto l'array e ogni volta trovo il minimo e lo swappo con il numero alla posizione i
finche non ottengo tutto in ordine

*/

#include "stdio.h"

void SelectionSort(int *A, int n) {
    int i = 0;
    for (; i < n - 1;i++) {
        int iMin = i;
        for (int j = i+1; j < n ;j++) {
            if (A[j] < A[iMin]) {
                iMin = j;
            }
        }
            int temp = A[i];
                A[i] = A[iMin];
                A[iMin] = temp;
                printf("%d", A[i]);
    }
    printf("%d", A[i]);
}

int main() {
    int A[] = { 2,7,4,1,5,3 };
    SelectionSort(A, 6);
}


/* Bubble Sort  Time Complexity O(n^2)

confronto una coppia di numeri alla volta spostando di di volta in volta il numero piu grande verso destra.
il Flag serve per capire se la stringa era gia ordinata,
 in questo caso evita di rifare n volte il loop di riordinamento
diventando quindi nel caso miglione O(n).

*/

#include "stdio.h"
#define swap(type, i, j) {type t = i; i = j; j = t;}

void BubbleSort(int *A,int n) {
    for (int u = 1;u < n - 1;u++) {
        int flag = 0;
        for (int i = 0; i < n - 2;i++) {
            if (A[i] > A[i + 1]) {
                swap(int, A[i], A[i + 1]);
                flag = 1;
            }
        }
        if (flag == 0);
        break;
    }
}

int main() {
    int A[] = { 1,2,3,4,5,6,7,8 };
    int n = 8;
    BubbleSort(A, n);
    for (int i = 0; i < n;i++) {
        printf("%d", A[i]);
    }
    return 0;
}