Deque를 통해 버킷정렬(Bucket Sort)을 해보자.

저번시간에 만들었던 Deque를 사용하여 버킷정렬을 연습해보기로 했다.

우선 버킷정렬이 무엇인지 알아보자.

버킷정렬(Bucket Sort) 이란??

n개의 데이터를 정렬할 때 같은 크기의 간격을 갖는 n개의 버켓에 데이터를 분배한다. 입력 데이터가 균일하게 분포되었다면 각 버켓에는 1개의 데이터가 있게 되지만, 균일하게 분포되지 않으면 다수의 데이터가 버켓에 들어 갈 수 있으며 각 버켓의 데이터는 정렬하여 저장한다. n개의 모든 데이터를 버켓에 분배하였다면 버켓 번호 순으로 스캔하여 출력하면 정렬된 데이터를 얻게 된다.

[예제] 최대 2자리를 갖는 정수 (0부터 99까지의 정수) 10개를 버켓 정렬한다고 하자. 각 버켓은 같은 크기의 간격 (0-9, 10-19, 20-29,…, 90-99)을 갖는 10개의 버켓을 만들어 데이터를 해당 버켓에 분배한다. 각 버켓에 분배된 데이터는 정렬한다. 다음 버켓 번호 순으로 데이터를 모으면 정렬된 데이터가 된다. 다음은 배열에 10개의 정수 [22, 43, 27, 31, 83, 7, 92, 69, 36, 25]를 버켓 정렬한 것을 도식으로 표현하였다. 

그럼 이 버킷정렬을 deque를 통해 어떤 방식으로 이루어질지 알아보자.

우선 정렬이 되지 않은 데이터를 담고 있는 Deque를 만든다. 그리고 그 데이터의 개수만큼의 Deque 배열을 만든다. 그리고 정렬되지 않은 데이터를 담고 있는 Deque에서 하나씩 데이터를 꺼낸다. 그리고 그 데이터에서 배열 인덱스를 구하고 그 인덱스 위치에 있는 Deque에 데이터를 삽입한다.

이때 데이터를 삽입할 때 Deque에 정렬해서 데이터를 삽입해야 나중에 데이터를 정렬되어서 가져올 수 있다. 인덱스에 위치한 Deque가 데이터가 없는경우 addFirstItem메서드를 통해서 데이터를 집어넣는다. 만약 데이터가 있다면 기존에 데이터의 front에 있는 데이터와 비교하여 순서에 맞게 삽입한다. 이때 순서를 찾기위해서 임시 Deque를 사용하는데 이부분은 단순하여 코드를 보면 쉽게 이해할 수 있다.

이렇게 정렬되지 않은 Deque의 데이터를 버킷에 다 집어 넣고 나서 버킷을 순회하면서 정렬된 데이터를 기존 Deque에 삽입한다.

그럼 정렬이 끝난다.

완성된 코드와 실행화면은 아래와 같다.

Deque에서 사용할 인터페이스

package practice3;
 
public interface Deque<T> {
    public void addFirst(T item);
 
    public void addLast(T item);
 
    public T removeFirst();
 
    public T removeLast();
 
    public T peekFirst();
 
    public T peekLast();
 
    public boolean isEmpty();
 
    public int size();
 
    public String toString();
 
}
 

기존에 만든 Deque

package practice3;
 
import java.util.ArrayList;
import java.util.List;
 
public class LinkedDeque<T> implements Deque<T>{
    private static class Node<T> {
        private T item;
        private Node<T> next;
        private Node<T> prev;
 
        private Node() {
            next = null;
            prev = null;
        }
 
        private Node(T item) {
            this.item = item;
            next = null;
            prev = null;
        }
    }
 
    private Node<T> front;
    private Node<T> rear;
    private int size;
 
    public LinkedDeque() {
        front = null;
        rear = null;
        size = 0;
    }
 
    @Override
    public void addLast(T item) {
        Node<T> node = new Node<>(item);
        
        if (front == null && rear == null) {
            addFirstItem(node);
        } else {
            rear.next = node;
            node.prev = rear;
            rear = node;
            size++;
        }
    }
 
    @Override
    public void addFirst(T item) {
        Node<T> node = new Node<>(item);
        
        if (front == null && rear == null) {
            addFirstItem(node);
        } else {
            front.prev = node;
            node.next = front;
            front = node;
            size++;
        }
    }
    
    private void addFirstItem(Node<T> item) {
        front = item;
        rear = item;
        size = 1;
    }
 
    @Override
    public boolean isEmpty() {
        return size == 0;
    }
 
    @Override
    public T removeFirst() {
        T item = null;
        if (size == 0) {
            throw new java.util.NoSuchElementException("peek(): deque empty");
        } else if (size == 1) {
            item = front.item;
            front = null;
            rear = null;
            size = 0;
        } else {
            item = front.item;
            front = front.next;
            front.prev = null;
            size--;
        }
        
        return item;
    }
 
    @Override
    public T removeLast() {
        T item = null;
 
        if (size == 0) {
            throw new java.util.NoSuchElementException("peek(): deque empty");
        } else if (size == 1) {
            item = rear.item;
            front = null;
            rear = null;
            size = 0;
        } else {
            item = rear.item;
            rear = rear.prev;
            rear.next = null;
            size--;
        }
        
        return item;
    }
 
    @Override
    public T peekFirst() {
        if (size == 0)
            throw new java.util.NoSuchElementException("peek(): deque empty");
        return front.item;
    }
 
    @Override
    public T peekLast() {
        if (size == 0)
            throw new java.util.NoSuchElementException("peek(): deque empty");
        return rear.item;
    }
 
    @Override
    public int size() { return size; }
 
    @Override
    public String toString() {
        if (0 == size) {
            return "";
        } else {
            List<String> result = new ArrayList<>();
            Node<T> current;
            current = front;
            if (1 == size) {
                return current.item.toString();
            } else {
                while (current != null) {
                    result.add(current.item.toString());
                    current = current.next;
                }
                
                return String.join(",", result);
            }
            
        }
    }
 
    public String reverse() { // 역순으로 출력
        if (0 == size) {
            return "";
        } else {
            List<String> result = new ArrayList<>();
            Node<T> current;
            current = rear;
            if (1 == size) {
                return current.item.toString();
            } else {
                while (current != null) {
                    result.add(current.item.toString());
                    current = current.prev;
                }
                
                return String.join(",", result);
            }
            
        }
    }
 
}
 

Deque를 정렬하는 Bucket Sort 클래스 (이번 문제의 핵심 클래스)

package practice3;
 
public class BucketSort {
    
    public BucketSort() {}
 
    // 들어온 Deque에 데이터를 버킷정렬을 이용하여 정렬 
    public void bucketSort(LinkedDeque<Integer> data) {
        int bucketIdx;
        int value;
        int size = data.size();
        LinkedDeque<Integer>[] bucketArray = new LinkedDeque[data.size()];
        
        // 들어온 덱에 있는 데이터를 버켓으로 정렬 
        while (!data.isEmpty()) {
            value = data.removeFirst();
            
            bucketIdx = (int) (size * (value / Math.pow(10, getNumCnt(value))));
            if (bucketArray[bucketIdx] == null || bucketArray[bucketIdx].isEmpty()) {
                bucketArray[bucketIdx] = new LinkedDeque<Integer>();
                bucketArray[bucketIdx].addFirst(value);
            } else {
                LinkedDeque<Integer> temp = new LinkedDeque<>();
                while (bucketArray[bucketIdx] != null && !bucketArray[bucketIdx].isEmpty() && bucketArray[bucketIdx].peekFirst() < value) {
                    temp.addFirst(bucketArray[bucketIdx].removeFirst());
                }
                bucketArray[bucketIdx].addFirst(value);
                
                while(!temp.isEmpty()) {
                    bucketArray[bucketIdx].addFirst(temp.removeFirst());
                }
            }
        }
        
        // 버켓에 정렬된 데이터를 다시 덱으로 옮기는 작업 
        for (int i = 0; i < size; i++) {
            while (bucketArray[i] != null && !bucketArray[i].isEmpty()) {
                data.addLast(bucketArray[i].removeFirst());
            }
        }
    }
    
    /**
     * 자리수를 구하는 메소드 
     * 
     * @param value
     * @return
     */
    private int getNumCnt(int value) {
        return (int) Math.log10(value) + 1 ;
    }
}
 

각 Deque의 기능을 호출하는 메인 클래스

package practice3;
 
import java.util.Scanner;
 
public class Main {
    public static void main(String[] args) {
        System.out.println("Enter a command: af(addFirst), al(addLast),\n"
                + "rf(removeFirst), rl(removeLast), pf(peekFirst), pl(peekLast),\n" + "p(rint), r(verse), or q(uit)");
        System.out.print("> ");
 
        Scanner input = new Scanner(System.in);
        String command = input.next();
        LinkedDeque<Integer> deque = new LinkedDeque<Integer>();
        BucketSort bSort = new BucketSort();
        int item;
 
        while (!command.equals("q")) {
            if (command.equals("af")) {
                item = input.nextInt();
                deque.addFirst(item);
            } else if (command.equals("al")) {
                item = input.nextInt();
                deque.addLast(item);
            } else if (command.equals("rf"))
                deque.removeFirst();
            else if (command.equals("rl"))
                deque.removeLast();
            else if (command.equals("s"))
                System.out.println("size: " + deque.size());
            else if (command.equals("pf"))
                System.out.println("Front of the deque: " + deque.peekFirst());
            else if (command.equals("pl"))
                System.out.println("Rear of the deque: " + deque.peekLast());
            else if (command.equals("r"))
                System.out.println(deque.reverse());
            else if (command.equals("p"))
                System.out.println(deque);
            else if (command.equals("bsort"))
                bSort.bucketSort(deque);
            System.out.print("> ");
            command = input.next();
        }
        System.out.println("Commands Terminated.");
        input.close();
    }
}
 

실행결과

Enter a command: af(addFirst), al(addLast),

rf(removeFirst), rl(removeLast), pf(peekFirst), pl(peekLast),

p(rint), r(verse), or q(uit)

> af 45

af 18

af 35

af 43

af 47

af 39

af 64

af 11

af 15

af 90> > > > > > > > > 

> p

90,15,11,64,39,47,43,35,18,45

> bsort

> p

11,15,18,35,39,43,45,47,64,90

>