1 개요[ | ]
- 버킷정렬 구현
- 0 ≤ x < 1 인 실수값들을 정렬하는 예제이다.
- 처음에 size 개수의 통을 만들고 x*size 번 통에 담고 각 통들을 내부적으로 정렬하고 전체 통들을 수합한다.
- 각 통의 내부 정렬에는 언어별 내장된 sort 기능[1] 사용한다.
- ※ 버킷의 수를 지정할 수 있어야 하는데, 아래 소스코드에서는 자료의 개수를 버킷의 개수로 적용하였다.
- 추후 보완 필요
2 C[ | ]

C
Copy
#include <stdio.h>
void quick_sort(float a[], int L, int R) {
int left, right;
float pivot = a[L];
for(left=L,right=R; left<right; right--) {
while( a[right]>=pivot && left<right ) right--;
if( left<right ) a[left] = a[right];
while( a[left]<=pivot && left<right ) left++;
if( left>=right ) break;
a[right] = a[left];
}
a[left]=pivot;
if(left>L) quick_sort(a, L, left-1);
if(left<R) quick_sort(a, left+1, R);
}
void bucket_sort(float a[], int size) {
float buckets[size][size];
int i, j, pos, bi, buckets_size[size];
for(i=0; i<size; i++) {
buckets_size[i] = 0;
for(j=0; j<size; j++) buckets[i][j] = 9999;
}
for(i=0; i<size; i++) {
bi = (int)(size*a[i]);
buckets[bi][buckets_size[bi]] = a[i];
buckets_size[bi]++;
}
for(i=0; i<size; i++) {
quick_sort(buckets[i], 0, buckets_size[i]-1);
}
pos = 0;
for(i=0; i<size; i++) {
for(j=0; j<buckets_size[i]; j++) {
a[pos++]=buckets[i][j];
}
}
}
int main() {
float arr[] = {0.9, 0.1, 0.22, 0.99, 0.0, 0.4, 0.22};
int size = sizeof(arr)/sizeof(int);
bucket_sort(arr, size);
for(int i=0; i<size; i++) printf("%.2f ", arr[i]);
// 0.00 0.10 0.22 0.22 0.40 0.90 0.99
}
3 C++[ | ]

C++
Copy
#include <iostream>
#include <vector>
#include <algorithm>
void bucket_sort(float a[], int size) {
std::vector<float> b[size];
int i, j, pos=0;
for(i=0; i<size; i++) b[int(size*a[i])].push_back(a[i]);
for(i=0; i<size; i++) sort(b[i].begin(), b[i].end());
for(i=0; i<size; i++) {
for(j=0; j<b[i].size(); j++) a[pos++]=b[i][j];
}
}
int main() {
float arr[] = {0.9, 0.1, 0.22, 0.99, 0.0, 0.4, 0.22};
int size = sizeof(arr)/sizeof(float);
bucket_sort(arr, size);
for(int i=0; i<size; i++) std::cout << arr[i] << " ";
// 0 0.1 0.22 0.22 0.4 0.9 0.99
}
4 C#[ | ]

C#
Copy
using System;
using System.Collections;
class Program {
static void bucketSort(double[] a) {
int i, size=a.Length;
ArrayList[] buckets = new ArrayList[size];
for(i=0; i<size; i++) buckets[i] = new ArrayList();
foreach(double x in a) { buckets[(int)x*size].Add(x); }
foreach(ArrayList bucket in buckets) bucket.Sort();
int pos = 0;
foreach(ArrayList bucket in buckets) {
for(i=0; i<bucket.Count; i++) a[pos++]=(double)bucket[i];
}
}
static void Main() {
double[] arr = {0.9, 0.1, 0.22, 0.99, 0.0, 0.4, 0.22};
bucketSort( arr );
Console.Write(string.Join(", ",arr));
// 0, 0.1, 0.22, 0.22, 0.4, 0.9, 0.99
}
}
5 Java[ | ]

Java
Copy
import java.util.ArrayList;
import java.util.Collections;
public class MyClass {
static void bucketSort(double[] a) {
int i, size=a.length;
ArrayList[] buckets = new ArrayList[size];
for(i=0; i<size; i++) buckets[i] = new ArrayList();
for(double x: a) { buckets[(int)x*size].add(x); }
for(ArrayList bucket: buckets) Collections.sort(bucket);
int pos = 0;
for(ArrayList bucket: buckets) {
for(i=0; i<bucket.size(); i++) a[pos++]=(double)bucket.get(i);
}
}
public static void main(String args[]) {
double[] arr = {0.9, 0.1, 0.22, 0.99, 0.0, 0.4, 0.22};
bucketSort(arr);
for(double x: arr) System.out.format( "%s ", java.math.BigDecimal.valueOf(x).stripTrailingZeros() );
// 0 0.1 0.22 0.22 0.4 0.9 0.99
}
}
6 PHP[ | ]

PHP
Copy
<?php
function bucket_sort(&$a) {
$size = count($a);
$b=array_fill(0,$size,[]);
foreach($a as $x) $b[intval($x*$size)][] = $x;
foreach($b as &$b1) sort($b1);
$pos=0;
for($i=0; $i<$size; $i++) {
for($j=0; $j<count($b[$i]); $j++) $a[$pos++]=$b[$i][$j];
}
}
$arr = [0.44, 0.1, 0.99, 0.9, 0.0, 0.1, 0.43];
bucket_sort($arr);
echo implode(', ', $arr);
# 0, 0.1, 0.1, 0.43, 0.44, 0.9, 0.99
7 Python[ | ]

Python
Copy
def bucket_sort(a):
size = len(a)
buckets = [[] for _ in range(size)]
for x in a: buckets[int(x*size)].append(x)
for b in buckets: b.sort()
pos = 0
for b in buckets:
bsize = len(b)
a[pos:pos+bsize] = b
pos += bsize
arr = [0.44, 0.1, 0.99, 0.9, 0.0, 0.1, 0.43]
bucket_sort( arr )
print( arr )
# [0.0, 0.1, 0.1, 0.43, 0.44, 0.9, 0.99]
8 Ruby[ | ]

Ruby
Copy
def bucket_sort(a)
size=a.size
buckets=[]
size.times{ buckets.push([]) }
for x in a; buckets[(x*size).floor].push(x); end
for b in buckets; b.sort!; end
pos=0
for b in buckets
a[pos,b.size] = b
pos += b.size
end
end
arr = [0.0, 0.1, 0.1, 0.43, 0.44, 0.9, 0.99]
bucket_sort( arr )
print( arr )
# [0.0, 0.1, 0.1, 0.43, 0.44, 0.9, 0.99]
9 같이 보기[ | ]
- ↑ 아마도 퀵정렬인 경우가 많을 것이다