반응형

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

    저번시간에 만들었던 Deque를 사용하여 버킷정렬을 연습해보기로 했다. 우선 버킷정렬이 무엇인지 알아보자. 버킷정렬(Bucket Sort) 이란?? n개의 데이터를 정렬할 때 같은 크기의 간격을 갖는 n개의 버켓에 데이터를 분배한다. 입력 데이터가 균일하게 분포되었다면 각 버켓에는 1개의 데이터가 있게 되지만, 균일하게 분포되지 않으면 다수의 데이터가 버켓에 들어 갈 수 있으며 각 버켓의 데이터는 정렬하여 저장한다. n개의 모든 데이터를 버켓에 분배하였다면 버켓 번호 순으로 스캔하여 출력하면 정렬된 데이터를 얻게 된다. [예제] 최대 2자리를 갖는 정수 (0부터 99까지의 정수) 10개를 버켓 정렬한다고 하자. 각 버켓은 같은 크기의 간격 (0-9, 10-19, 20-29,…, 90-99)을 갖는 10개..

    Deque를 직접 구현해보기

    큐는 삽입과 삭제가 리스트의 한쪽 방향에서만 이루어지지만 deque는 리스트의 양쪽 끝 모두에서 이루어질 수 있다. 따라서 양쪽 방향 모두 삽입과 삭제가 이루어질 수 있으므로 기존의 큐나 스택으로 사용할 수 있어 유연하게 사용할 수 있다. 사진출처 : https://dh00023.github.io/algorithm/ds/2018/04/25/algorithm-10/ 이런 Deque를 직접 구현해 보자. 우선 Deque의 기능을 정리한 인터페이스이다.1234567891011121314151617181920212223package practice3; public interface Deque { public void addFirst(T item); public void addLast(T item); public..

반응형