quicksort

// quickSort.c
#include <stdio.h>

void quickSort( int[], int, int);
int partition( int[], int, int);


void main()
{
	int a[] = { 7, 12, 1, -2, 0, 15, 4, 11, 9};

	int i;
	printf("\n\nUnsorted array is:  ");
	for(i = 0; i < 9; ++i)
		printf(" %d ", a[i]);

	quickSort( a, 0, 8);

	printf("\n\nSorted array is:  ");
	for(i = 0; i < 9; ++i)
		printf(" %d ", a[i]);

}



void quickSort( int a[], int inizio, int fine)
{
   int i_partiz;
   printf("\ninizio= %d",inizio);

   if( inizio < fine )
   {
   	// divide and conquer
        i_partiz = partition( a, inizio, fine);
       quickSort( a, inizio, i_partiz-1);
       quickSort( a, i_partiz+1, fine);
   }

}



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

int partition (int arr[], int low, int high)
{
    int pivot = arr[high];    // pivot
    int i = (low - 1);  ///il muro
    int j;///l'elem minore
    for (j = low; j < high; j++)
    {
        if (arr[j] < pivot)
        {
            i++; ///il muro si incrementa
            swap(&arr[i], &arr[j]); ///scambia il muro con l'elem attuale
        }
    }
    swap(&arr[i + 1], &arr[high]);
    return (i+1);
}