/*
    46__quick_sort.c
    -----
    Program generirani niz slucajnih brojeva sortira quick sort algoritmom
    za sortiranje.
*/
 
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
 
#define MAX 100
/* definicija macro naredbe za zamjenu vrijednosti dvaju int varijabli */
#define SWAP(a, b) { int t; t=a; a=b; b=t; }
 
/* globalno polje koje ce sadrzavati niz slucajnih brojeva */
int a[MAX];
 
void quick(int lijevi, int desni)
{
    int j, k, x;
    if(lijevi < desni) {
        if(a[lijevi] > a[desni])
            SWAP(a[lijevi], a[desni]);
        j=lijevi;
        k=desni;
        do {
            do { j++; } while(a[j] < a[lijevi]);
            do { k--; } while(a[k] > a[lijevi]);
            if(j < k)
                SWAP(a[j], a[k]);
        } while(j <= k);
        SWAP(a[lijevi], a[k]);
        quick(lijevi, k-1);
        quick(k+1, desni);
    }
}
 
int main()
{
    int n, k;
 
    srand((unsigned)time(NULL));
 
    printf("Unesite zeljenu velicinu niza brojeva: ");
    scanf("%d", &n);
    printf("Niz slucajnih brojeva [1-100]:\n");
    for (k = 0; k < n; k++) {
        a[k] = rand() % 100 + 1;
        printf("%d ", a[k]);
    }
    printf("\n");
 
    quick(0, n-1);
 
    printf("\nNiz brojeva nakon provodjenja quick sort algoritma:\n");
    for(k = 0; k < n; k++)
        printf("%d ", a[k]);
    printf("\n");   
 
    return 0;
}