バケツソートの実装

この記事は「大分高専 Advent Calendar 2024」9日目の記事です．

はじめに

絶賛テスト期間中の高専生，S2108です．アルゴリズムのテストにバケットソートの穴埋め問題が出てきたので，復習の意味も込めてC言語で実装してみました．バケツソートとも呼ぶらしいです．どんなソートかの説明は省略します．勝手に調べてください．
初記事です！

C言語での実装

main.c

#include<stdio.h>
#define MAX 10

void bucket_sort(int number[], int num_of_item){
  int i,buckets[MAX];

  for (i = 0; i < MAX; i++)
  { // バケツを用意する
    buckets[i] = 0;
  }

  for (i = 0; i < num_of_item; i++)
  { // 元のデータをバケツに入れる
    buckets[number[i]] = number[i];
  }

  int j=0;
  for (i = 0; i < MAX; i++)
  { // バケツから元の配列に戻す
    if (0 < buckets[i]) number[j++] = buckets[i];
  }
  
}
int main(void) {
  int numbers[] = {3,5,6,2,7,1};
  int length = sizeof(numbers)/sizeof(numbers[0]);
  // length : 配列の長さ
  
  printf("before : ");
  for (int i = 0; i < length; i++) printf("%d ",numbers[i]);
  printf("\n");
  
  bucket_sort(numbers,length);

  printf("after : ");
  for (int i = 0; i < length; i++) printf("%d ",numbers[i]);

  printf("\n");
  return 0;
}

bucket_sort関数には，配列と配列の要素数を渡す．

出力

$ gcc main.c 
$ ./a.out 
before : 3 5 6 2 7 1 
after : 1 2 3 5 6 7 

終わりに

以上バケツソートの実装でした．すごく直感的でわかりやすいソートで，データの個数が少なくて，値が被らない保証がある時には役に立ちそうだなと思いました．
残りのテスト頑張るぞー！

おまけ 〜Goでの実装〜

最近Go言語に興味があるので，Goでも実装してみました．C言語に似てるらしい．

main.go

package main

import (
    "fmt"
)
var MAX = 10

func bucket_sort(number []int) []int{
	var num_of_item = len(number)
	var buckets = make([]int,MAX)
	//make(型，大きさ)

	for i := 0; i < MAX; i++ {
		// バケツを用意する
		buckets[i] = 0
	}
	
	for i := 0; i < num_of_item; i++{
		// 元のデータをバケツに入れる
		buckets[number[i]] = number[i]
	}
  
	var j = 0
	for i := 0; i < MAX; i++ {
		if 0 < buckets[i]{
			number[j] = buckets[i]
			j++
		}
	}
	return number
}
func main() {
	var numbers = []int{3,5,6,2,7,1}

	fmt.Printf("before : ")
	for _, v := range numbers {
		fmt.Printf("%d,",v)
	}
	fmt.Printf("\n")

	numbers = bucket_sort(numbers)
	fmt.Printf("after : ")
	for _, v := range numbers {
		fmt.Printf("%d,",v)
	}
	fmt.Printf("\n")
}

出力

$ go run main.go 
before : 3,5,6,2,7,1,
after : 1,2,3,5,6,7,

C言語に似てるって言われてるけど，変数の宣言とか若干違ってややこしい．勉強します..