버킷정렬 구현

1 개요

버킷정렬 구현

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

추후 보완 필요

2 C

C언어 버킷정렬 구현 문서를 참고하십시오.

#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++ 버킷정렬 구현 문서를 참고하십시오.

#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샵 버킷정렬 구현 문서를 참고하십시오.

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 버킷정렬 구현 문서를 참고하십시오.

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 버킷정렬 구현 문서를 참고하십시오.

<?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 버킷정렬 구현 문서를 참고하십시오.

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 버킷정렬 구현 문서를 참고하십시오.

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 같이 보기

• 버킷정렬
• 정렬 구현