クイックソート（C言語、Go言語）

クイックソートを C言語と Go言語で実装してみました。クイックソートは、配列の中からひとつ任意にサンプルを取ってきます。これを「ピボット」といいます。あとは、配列からピボットを除いたものを、その値がピボットより大きいか小さいかで二つの配列に分け、さらにその二つを再帰的にクイックソートします。最後はそれらを「小、ピボット、大」の順に連結します。これだけです。

C言語。じつは最初は自力で実装しようとしたのですが、うまい方法がどうしても思いつきませんでした。で、アルゴリズムの教科書を参照してみたのですが、配列の分割にとても巧みな方法が採用されていて、びっくりしました。下の partition() ですね。クイックソートは C でこんなに簡単に実装できるのだな。いや、まいりました。
quick_sort.c

#include <stdio.h>

int partiton(int ar[], int p, int r) {
    int x, i, j, tmp;
    
    x = ar[r];
    i = p - 1;
    for (j = p; j < r; j++) {
        if (ar[j] <= x) {
            i++;
            tmp = ar[i]; ar[i] = ar[j]; ar[j] = tmp;
        }
    }
    ar[r] = ar[i + 1];
    ar[i + 1] = x;
    
    return i + 1;
}

void quick_sort(int ar[], int p, int r) {
    if (p < r) {
        int q = partiton(ar, p, r);
        quick_sort(ar, p, q - 1);
        quick_sort(ar, q + 1, r);
    }
}

int main() {
    int ar[] = {3, 1, 5, 2, 9, 7, 0};
    int len = sizeof ar / sizeof(int);
    
    quick_sort(ar, 0, len - 1);
    
    printf("[");
    for (int i = 0; i < len; i++) {
        printf("%d, ", ar[i]);
    }
    printf("\b\b]\n");
    
    return 0;
}

　
Go言語。Cとはまったくちがう実装ですが、これも大変にシンプルに実装できます。クイックソートは優秀なソート法として知られますが、実装も簡単なのがすばらしいですね。
Go は append() 関数があるのがラクでいいですね。Go でスライスを扱うには、append() の挙動を正確に理解しておくことが重要だと思います。
quick_sort.go

package main
import "fmt"

func quick_sort(ar []int) []int {
    var left, right []int
    if len(ar) > 1 {
        x := ar[0]
        for _, a := range ar[1:] {
            if a < x {
                left  = append(left , a)
            } else {
                right = append(right, a)
            }
        }
        left  = quick_sort(left)
        right = quick_sort(right)
        ar = append(append(left, x), right...)
    }
    return ar
}

func main() {
    ar := quick_sort([]int{3, 1, 5, 10, 2, 9, 7, 0})
    fmt.Println(ar)
}

ちなみに Ruby だとこんな感じです。実質 3行。Go言語版とやっていることは同じです。何というか、アルゴリズムがそのままコードになっているという印象ですね。

class Array
  def quick_sort
    return [] if empty?
    x, xs = first, drop(1)
    xs.select{|i| i < x}.quick_sort + [x] + xs.select{|i| i >= x}.quick_sort
  end
end