지정된 정렬 순서에 맞춰 특정 리스트를 재배열하는 건 흔히 있는 일이다. 리스트는 보통 작은 수에서 큰 수로 또는 알파멧 순서 등의 자연스러운 순서로 정렬된다. 하지만 정렬할 때는 다른 기준을 요구할 수도 있다. 자바는 정렬을 돕기 위해
Comparable과
Comparator라는 두 가지 인터페이스를 제공한다.
Comparable과 Comparator 인터페이스의 차이는 무엇인가?
두 인터페이스는 모두
public 접근 변경자로 선언하기 때문에 모든 용도의 자료를 담을 수 있다.
Comparable 인터페이스는 자연스러운 순서로 정렬할 때 사용하고,
Comparator는 원하는 순서대로 정렬 순서를 지정하고 싶은 곳에 사용한다.
배열을 정렬할 때는 일반적으로 Array나 Collection 클래스에 내장된 라이브러리를 이용한다. 하지만 면접 시에는 이런 알고리즘을 직접 작송해야 할 때가 많다.
Array와 Collection 클래스는 몇 가지 오버로딩된 정렬 메서드가 있다. 크게 배열을 매개변수로 받는 메서드와 배열과 Comparator 객체를 배개변수로 받는 메서드의 두 가지로 분류된다. 그리고 각각의 원시 타입
priomitive type과 참조 타입
reference type에 관한 객체를 오버로드한다.
Comparator 객체가 없는 구현체는 타입을 자연스런 순서롤 정렬한다. 코드 4-1은 작은 수부터 큰 수로 정렬한 int 타입의 배열 예다.
[코드4-1] int 타입 배열을 순서대로 정렬하기
@Test
public void sortInts() {
final int[] numbers = {-3, -5, 1, 7, 4, -2};
final int[] expected = {-5, -3, -2, 1, 4, 7};
Arrays.sort(number);
assertArrayEquals(expected, numbers);
}
객체 배열을 정렬하려면 코드 4-2 처럼 Comparable 인터페이스를 구현해야 한다.
[코드4-2]객체를 순서대로 정렬하기
@Test
public void sortObjects() {
final String[] strings = {"z", "x", "y", "abc", "zzz", "zazzy"};
final String[] expected = {"abc", "x", "y", "z", "zazzy", "zzz" };
Arrays.sort(strings);
assertArrayEquals(expected, strings);
}
String 클래스는 Comparable 인터페이스를 구현하므로 예상한 대로 정렬된다. 정렬해야 하는 타입이 Comparable 인터페이스를 구현하지 않으면 ClassCastException 예외가 발생한다. 따라서 클래스를 정의할 때는 코드 40-3처럼 Comparable 인터페이스를 구현해야 한다.
[코드4-3]Comparable 인터페이스 없이 정렬하기
@Test
public void sortNotComparable() {
final List<NotComparable> objects = new ArrayList<>();
for(int i = 0; i < 10; i++) {
objects.add(new NotiComparable(i));
}
try {
Arrays.sort(objects.toArray());
} catch (Exception e) {
// 정렬할 수 없음.
}
fail();
}
컴파일러는 매개변수의 자료형이 Comparable 인터페이스를 구현했을 거라고 생각하므로 Collection.sort() 메서드를 사용할 수 없다. 메서드 시그니처는 다음과 같다.
public static <T extends Comparable<? super T>> void sort(List<T> list)
지정한 순서대로 정렬하고 싶으면 sort 메서드에서 사용할 Comparator 인터페이스를 구현한 후 이를 sort 메서드에 제공해야 한다. 이를 위해 Comparator 인터페이스에는 자료형 T를 구현하는 int compare(T o1, T o2)와 boolean equals(Object o)라는 두 가지 메서드가 있다. Compare 메서드는 양수, 0, 음이라는 세 가지 상태 중 하나로 int 타입의 값을 반환한다. 구체적으로 살펴보면 두 번째 매개변수 앞에 첫 번째 매개변수가 오면 음수 값, 두 개의 매개변수가 같으면 0, 두 번째 매개변수가 첫 번째 매개변수보다 앞에 오면 양수 값을 반환한다.
Comparator 인터페이스를 이용해 역순으로 정렬하고 싶다면 코드 4-4 처럼 구현하면 된다.
[코드 4-4] Compaator 인터페이스 사용해 숫자를 역순으로 정렬하기
@Test
public class ReverseNumbericalOrder implements Comparator<Integer> {
@Overide
public int compare(Integer o1, Integer o2) {
return o2 - o1;
}
// 같은 부분은 생략함
}
코드 4-5는 Comparator 인터페이스를 적용한 예다.
[코드 4-5] 사용자가 지정한 순서로 정렬하기
@Test
public void customSorting() {
final List numbers = Arrays.asList(4, 7, 1, 6, 3, 5, 4);
final List expected = Arrays.asList(7, 6, 5, 4, 3, 2, 1);
Collections.sort(numbers, new ReverseNumericalOrder());
assertEquals(expected, numbers);
}
지금까지 소개한 예제들이 간단하고 자연스런 순서로 정렬될 것이다.
버블 정렬 알고리즘은 어떻게 구현하는가?
버블 정렬
bubble sort 알고리즘은 설명과 구현이 가장 쉬운 알고리즘이다. 예를 들어 배열이 0부터 시작된다고 가정했을 때 의사코드는 다음과 같다.
for i between 0 and (array length - 2):
if (array(i + 1) < array(i)):
switch array(i) and array(i + 1)
repeat until a complete iteration where no elements are switched.
이제 작은 리스트와 관계된 간단한 예제를 살펴보자.
6,4,9,5->4,6,9,5: When i = 0, the numbers 6 and 4 are switched
4,6,9,5->4,6,5,9: When i = 2, the numbers 9 and 5 are switched
4,6,5,9: The first iteration switched numbers, so iterate again
4,6,5,9->4,5,6,9: When i = 1, the numbers 6 and 5 are switched
4,5,6,9: The second iteration switched numbers, so iterate again
4,5,6,9: No more numbers to switch, so this is the sorted list.
코드 4-6은 자바로 구현한 버블 정렬의 예다
[코드 4-6] 버블 정렬 구현하기
public void bubbleSort(int[] numbers) {
boolean numbersSwitched;
do {
numbersSwitched = false;
for (int i = 0; i < numbers.length - 1; i++) {
if((numbers[i + 1] < numbers[i]) {
int tmp = numbers[i + 1];
numbers[i + 1] = numbers[i];
numbers[i] = tmp;
numbersSwitched = true;
}
}
}while (numbersSwitched);
}
위 예는 구현하기는 간단하지만 엄청나게 비효율적이다. 최악의 경우 역순으로 정렬되어 있는 리스트를 정렬하려고 할 때 앞에서 가장 비효율적이라고 설명했던 O(n
2)의 성능과 같은 성능을 내는데, 이는 순환할 때마다 하나의 원소만 변경하기 때문이다. 최선의 경우는 리스트가 이미 정렬되어 있을 때다. 원소의 위치가 변경되지 않으므로 원소의 위치를 변경하지 않아도 된다. 이때는 O(n)의 성능을 낸다.
삽입 정렬 알고리즘은 어떻게 구현하는가?
삽입 졍렬insert sort 알고리즘은 도 하나의 설명하기 쉬운 알고리즘이다.
Given a list l, and a new list nl
for each element originallistelm in list l:
for each element newlistemlm in list nl:
if (originallistelem < newlistelem):
insert originallistelem in nl before newlistelem
else move to the next element
if( originallistelem has not been inserted:
insert at the end of nl
코드 4-7은 삽입 정렬을 구현한 예다.
[코드 4-7] 삽입 정렬 구현하기
public static List insertSort(final List numbers) {
final List sortedList = new LinkedList<>();
originalList:for(Integer number : numbers) {
for(int i = 0; i < sortedList.size(); i++) {
if(number < sortedList.get(i)) {
sortedList.add(i, number);
continue originalList;
}
}
sortedList.add(sortedList.size(), number);
}
return sortedList;
}
코드 4-7 에는 살펴봐야 할 부분이 몇 군데 있다. 먼저 버블 정렬하고는 다르게 정렬된 원소들을 새로운 리스트에 담아서 반환한다는 것에 주목하자. 삽입 정렬을 선택한 주된 이유다. 즉, 삽입 정렬은 새로운 리스트를 생성하고 해당 리스트를 반환한다.
또한 삽입 정렬에서 반환하는 리스트는 LinkedList 클래스의 인스턴스다. 연결리스트는 리스트의 중간에 원소를 추가하는데 매우 효율적이다. 리스트의 노드들에 포인터를 재배열하는 작업을 간단하게 하기 때문이다. 오히려 ArrayList 클래스를 사용했다면 리스트 중간에 원소를 추가할 경우 처리 속도가 많이 느렸을 것이다. ArrayList 클래스는 배열을 이용하므로 리스트의 앞이나 중간에 원소를 삽입하면 그 뒤에 있는 모든 원소를 한 칸씩 뒤로 이동시키야 햔다. 몇 백만개의 원소가 있는 배열이라면 이런 부분은 더 큰 부담으로 다가올 것이다. 특히 리스트의 앞 부분에 원소를 삽입할 경우 부담은 가중된다.
배열 리스트나 연결 리스트 같은 리스트 데이터 구조 사이의 차이는 '5장 자료구조'에서 설명하는 구현 방법에서 더 자세히 설명한다.
마지막으로, originalList라고 이름 지은 바깥쪽 반목문(for (Integer number : numbers) 부분)을 살펴보자. 원소가 적절한 위치에 삽입될 때는 원래 배열의 다음 원소로 이동할 수 있다. 즉, 안쪽 반복문(for (int i = 0; i < sortedLIst.size(); i++) 부분)의 continue 문을 호출해 바깥쪽 반복문의 다음 실행 차례로 이동할 수 있다. 바깥쪽 반복문을 계속 실행하고 싶다면 바깥쪽 반복문 안에 continue 문을 지정해 호출해야 한다. 원소가 성공저그로 삽입되었다면 바깥쪽 반복문의 조건을 이용해 continue 문을 호출할 수 있으며, 알고리즘은 다음 원소로 이동한다.
이 부분이 버블 정렬보다 삽입 정령이 좋은 점이다. 일단 반환할 리스트가 구성되면 즉시 반환할 수 있다. 순서대로 리스트를 확인하느라 불필요한 연산을 할 필요가 없다.
물론 최악의 경우 이 알고리즘의 성능은 여전히 O(n
2)일 것이다. 이미 정렬된 리스트를 다시 정렬하는 경우라면 매번 원소를 삽입할 때마다 새 리스트의 끝까지 반복문을 실행해야 하기 때문이다. 반대로 역순으로 정렬된 리스트를 정렬하는 경우라면 해다 ㅇ리스트의 앞에 있는 원소를 새 리스트에 넣으므로 O(n)의 성능을 가진다.
이런 경우 삽입 정렬 알고리즘은 새로운 리스트를 반환하므로 정렬하려는 리스트의 두 배 정도 되는 저자 공간이 필요하다. 이와 비교해 버블 정렬은 스왑할 때 사용하는 임시 변수용으로 사용할 여분의 메모리 슬록 하나만 더 있으면 된다.
퀵 정렬 알고리즘은 어떻게 구현하는가?
퀵 정렬
quick sort 알고리즘은 다음처럼 설명할 수 있다.
method quicksort(list l):
if l.size < 2:
return l
let pivot = l(0)
let lower = new list
let higher = new list
for each element e in between l(0) and the end of the list:
if e<pivot:
add e to lower
else add e higher
let sortedlower = quicksort(lower)
let sortedhighter = quicksort(highter)
return sortedlower + pivot + sortedhigher
이 알고리즘은 재귀적
recursive이다. 기본적으로 리스트에 0 혹은 1이라는 원소를 제공한다. 리스트는 이미 정렬되었으므로 간단하게 반환할 수 있다.
알고리즘의 두 번째 부분을 살펴보면 리스트에서 pivot이라는 임시 원소를 하나 선택한다. 여기에서는 리스트의 첫 번째 원소를 사용하지만 아무 원소나 선택해도 상관없다. 남아 있는 원소들은 pivot보다 크거나 같은 것들과 작은 것의 두 가지로 구분된다. 그리고 각 리스트는 다시 스스로를 정렬하는 메서드를 호출한다. 결론적으로 리스트는 pivot에 의해 작은 원소들과 큰 원소들로 정렬된다.
[코드 4-8] 퀵 정렬 알고리즘 구현하기
public staic List<Integer> quicksort(List<Integer> numbers) {
if (numbers.size() < 2) {
return numbers;
}
final Integer pivot = numbers.get(0);
final LIst<Integer> lower = new ArrayList<>();
final List<Integer> highter = new ArrayList<>();
for (int i = 1; i < numbers.size(); i++) {
if (numbers.get(i) < pivot) {
lower.add(numbers.get(i));
} else {
higher.add(numbers.get(i));
}
}
final List<Integer> sorted = quicksort(lower);
sorted.add(pivot);
sorted.addAll(quicksort(higher));
return sorted;
}
재귀 알고리즘을 만들어본 적이 있다면 실행을 종료할 수 있는지 확인해야 한다는 사실도 알 것이다. 코드 4-8에 나오는 알고리즘은 실행 종료를 보장한다. 각 재귀 호출이 작은 리스트로 이루어졌으며 마지막은 원소가 없거나 하나인 리스트이기 때문이다.
코드 4-8은 버블 정렬이나 삽입 정렬 알고리즘보다 훨씬 더 효율적인 성능을 발휘한다. 원소들을 두 개의 리스트로 분리하는 시간 복잡도 O(n)이고, 각각의 재귀 호출은 각 리스트 숫자의 절반만큼의 횟수만 발생한다. 그래서 이 알고리즘의 복잡도는 O(n log n)이다. 이건 평균적인 성능이다.
하지만 최악의 경우에는 여전히 O(n
2)이다. pivot을 선택하는 방법에 따라 다를 수 있기 때문이다. 코드 4-8에서는 pivot으로 항상 첫 번째 원소를 사용한다. 하지만 리스트가 역순으로 정렬되어 있다면 재귀 단계에서는 단지 각 리스트로 분리하는 시간만 줄일 수 있다.
다라서 리스트의 각 부분마다 발생하는 재귀 호출은 다른 정렬과는 독립적이면서 병렬로 실행되는 것이 좋다.
병합 정렬 알고리즘은 어떻게 구현하는가?
4장에서 다루는 마지막 정렬 알고리즘은 병합 정렬
merge sort 알고리즘이다. 다음 의사코드는 이 재귀 알고리즘에 대한 설명이다.
method mergesort(list l):
if list.size < 2:
return l
let middleIndex = l.size / 2
let leftList = elements between l(0) and l(middleIndex - 1)
let rightList = elements between l(middleIndex) and l(size - 1)
let sortedLeft = mergesort(leftList)
let sortedRight = mergesort(rightList)
return merge(sortedLeft, sortedRight)
method merge(list l, list r):
let leftPtr = 0
let rightPtr = 0
let toReturn = new list
while (leftPtr < l.size and rightPtr < r.size):
if (l(leftPtr) < r(rightPtr))
toReturn.add(l(leftPtr))
leftPtr++;
else:
toReturn.add(r(rightPtr))
rightPtr++
while (leftPtr < l.size):
toReturn.add(l(leftPtr))
leftPtr++
while (rightPtr < r.size):
toReturn.add(r(rightPtr))
rightPtr++
return toReturn
이건 또 다른 분할 정복divide-and-conquer 알고리즘이다. 리스트를 두 개로 나누고 각 하위 리스트를 정렬한 후 각각을 하나로 합친다.
주 코드( method merge())는 두 개의 리스트를 효율적으로 병합한다. 의사코드는 각각의 하위 리스트에 대한 포인터가 있고, 포인터는 가장 작은 값을 추가한 후 적절히 해당 포인터를 증가시킨다. 일단 포인터 하나가 리스트의 마지막에 도달하면 다른 리스트에 남아있는 원소들을 모두 추가할 수 있다. 앞부분의 merge 메서드에 있는 두 번째, 세 번째 while 문에서 하나의 while문은 바로 false를 반환한다. 모든 원소가 첫 번째 while 문에서 하위 리스트로 사용되었기 때문이다.
코드 4-9는 자바로 구현한 병합 정렬 알고리즘 예이다.
[코드 4-9] 병합 정렬 알고리즘 구현하기
public static List<Integer> mergesort(final List<Integer> values) {
if (values.size() < 2) {
return values;
}
final List<Integer> leftHalf =
values.subList(0, values.size() / 2);
final List<Integer> rightHalf =
values.subList(values.size() / 2, values.size());
return merge(mergesort(leftHalf), mergesoft(rightHalf));
}
private static List<Integer> merge(final List<Integer> left, final List<Integer> right) {
int leftPtr = 0;
int rightPtr = 0;
final List<Integer> merged = new ArrayList<>(left.size() + right.size());
while(leftPtr < left.size() && rightPtr < right.size()) {
if (left.get(leftPtr) < right.get(rightPtr)) {
merged.add(left.get(leftPtr));
leftPtr++;
} else {
merged.add(right.get(rightPtr));
rightPtr++;
}
}
while (leftPtr < left.size()) {
merged.add(left.get(leftPtr));
leftPtr++;
}
while (rightPtr < right.size()) {
merged.add(right.get(rightPtr));
rightPtr++;
}
return merged;
}
의사코드와 매우 비슷하다고 놀랄 건 없다. List 인터페이스의 sublist 메서드는 fromIndex와 toIndex라는 매개변수 두 개를 받는다. fromIndex는 자기 자신을 포함하지만 toIndex는 자기 자신을 포함하지 않는다.
면접에서 자주 나오는 질문 중 하나는 앞에 나오는 merge 메서드처럼 두 개의 정렬된 리스트를 병합하라는 것이다.이때 병합 정렬의 성능은 O(n log n)이고 각각의 병합 시간은 O(n)이며 각 재귀 호출은 주어진 리스트 숫자의 절반만큼만 발생한다는 사실을 다시 한번 기억하자.
실제로 자바 표준 라이브러리에 있는 몇몇 정렬 알고리즘은 리스트의 크기에 따라 다르게 구현되어 있다. 작은 리스트는 삽입 정렬을 이용하지만 지정된 크기가 넘어가면 병합 정렬을 이용한다.
