/*
 * クイックソートによるソート
 * DACCHO wrote this sample program.
 */

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

void output_array(int *ptr, int n);
void quick_sort(int *ptr, int left, int right);
void swap(int *ptr1, int *ptr2);

int main(void)
{
    int a[20];
    int i;

    srand((unsigned)time(NULL));
    for(i=0; i<20 ; i++)
        a[i] =rand() %100;

    printf("*** クイックソートによるソート ***\n");
    printf("ソート前のデータの並び\n");
    
    output_array(a, 20);

    printf("Press Enter Key\n");
    getchar();

    printf("ソート後のデータの並び\n");
    quick_sort(a, 0, 19);
    output_array(a, 20);

    printf("Press Enter Key\n");
    getchar();

    return 0;
}

void output_array(int *ptr, int n)
{
    int i;

    for(i=0; i<n; i++){
        printf("%2d : %d\n", i+1, *ptr);
        ptr++;
    }
}

void quick_sort(int *ptr, int left, int right)
{
    int i, j;
    
    if(left >= right)
        return;

    j = left;

    for(i=left+1; i <= right; i++)

        /* 以下の行の判定を「<」から「>」へ変更すると降順になります */
        if(*(ptr+i) < *(ptr+left))
            swap(ptr+(++j), ptr+i);

    swap(ptr+left, ptr+j);
    quick_sort(ptr, left, j-1);
    quick_sort(ptr, j+1, right);
}

void swap(int *ptr1, int *ptr2)
{
    int w;

    w     = *ptr1;
    *ptr1 = *ptr2;
    *ptr2 = w;
}