OSTATNIE_QUICK_SORT_V-KSZTAŁTNIE

// An iterative implementation of quick sort
#include <stdio.h>
#include<time.h>
// A utility function to swap two elements
void swap(int* a, int* b)
{
    int t = *a;
    *a = *b;
    *b = t;
}

/* This function is same in both iterative and recursive*/
int partition(int arr[], int l, int h)
{
    int x = arr[h];
    int i = (l - 1);

    for (int j = l; j <= h - 1; j++) {
        if (arr[j] <= x) {
            i++;
            swap(&arr[i], &arr[j]);
        }
    }
    swap(&arr[i + 1], &arr[h]);
    return (i + 1);
}

/* A[] --> Array to be sorted,
l --> Starting index,
h --> Ending index */
void quickSortIterative(int arr[], int l, int h)
{
    // Create an auxiliary stack
    int stack[h - l + 1];

    // initialize top of stack
    int top = -1;

    // push initial values of l and h to stack
    stack[++top] = l;
    stack[++top] = h;

    // Keep popping from stack while is not empty
    while (top >= 0) {
        // Pop h and l
        h = stack[top--];
        l = stack[top--];

        // Set pivot element at its correct position
        // in sorted array
        int p = partition(arr, l, h);

        // If there are elements on left side of pivot,
        // then push left side to stack
        if (p - 1 > l) {
            stack[++top] = l;
            stack[++top] = p - 1;
        }

        // If there are elements on right side of pivot,
        // then push right side to stack
        if (p + 1 < h) {
            stack[++top] = p + 1;
            stack[++top] = h;
        }
    }
}

// A utility function to print contents of arr
void printArr(int arr[], int n)
{
    int i;
    for (i = 0; i < n; ++i)
        printf("%d ", arr[i]);
}

// Driver program to test above functions
clock_t start, stop;
double czas;
int main()
{
    int x=90000;
       int y=x/2;
       int j=x;
       int i=0;
       int arr[x+1];
       for (i=0;i<=y;i++)
       {
           arr[i]=j--;
           //printf("TABELA: %d\n",arr[i]);
       }
       for (i=y;i<=x;i++)//A-kształtna
       {
           arr[i]= i;
           //printf("TABELA: %d\n",arr[i]);

       }

    int n = sizeof(arr) / sizeof(*arr);
    start = clock();
    quickSortIterative(arr, 0, n - 1);
    printArr(arr, n);
    stop = clock();
     czas= (double) (stop-start)/CLOCKS_PER_SEC;
     printf("Czas QS: %f\n",czas);

    return 0;
}