クイックソート

クイックソートをC言語で書いてみたら思いのほか書けなくてびっくりした。。そしてへんこんだ。でもまあ、リハビリだと思いつつがんばる。

あとあれ、マージソートとの違いは、分割前に並び替えちゃうのか、統治時に並び替えるのか、そこなのよね。

// qsort.c
#include "qsort.h"

void quick_sort(int *list, const size_t size)
{
    int l = 0, h = size - 1, tmp = 0;
    int pivot = *list;

    if (l < h) {
        while(1) {
            while(list[l] < pivot)
                l++;

            while(list[h] > pivot)
                h--;

            if (l <= h) {
                tmp = list[l];
                list[l] = list[h];
                list[h] = tmp;
            }
            else
                break;

            l++;
            h--;
        }

        quick_sort(list, l);
        quick_sort(&list[l], size - l);
    }
}

void print_r(const int list[], const size_t size)
{
    int i = 0;
    while(i < size) {
        printf("[%d] %d -> ", i, list[i]);
        i++;
    }
    printf("end \n");
}

// qsort.h
#include <stdio.h>
#include <stdlib.h>

void quick_sort(int*, const size_t);
void print_r(const int [], const size_t);

// qsort_test
#include "qsort.h"

int main()
{
    int test1[] = {2, 5, 3, 4, 8, 9, 7, 10, 2};

    quick_sort(test1, sizeof(test1)/sizeof(test1[0]));
    print_r(test1, sizeof(test1)/sizeof(test1[0]));

    return 0;
}

[0] 2 -> [1] 2 -> [2] 3 -> [3] 4 -> [4] 5 -> [5] 7 -> [6] 8 -> [7] 9 -> [8] 10 -> end