[Java] 정렬

Comparable vs Comparator Interface

자바는 정렬을 돕기 위해 Comparable 그리고 Comparator 인터페이스를 제공합니다.

 

공통점

• 두 인터페이스 모두 public 접근 변경자로 선언하기 때문에 모든 자료형을 담을 수 있습니다.

 

차이점

특성	Comparable	Comparator
메서드	Comparable 인터페이스는 compareTo(Object a) 메서드를 사용 -> 개체가 하나 제공됨 (this)	Comparator 인터페이스는 compare(Object o1, Object o2) 메서드를 사용 -> 개체가 두개 제공됨
정렬 사용처	Collections.sort(List) 메서드는 Comparable 타입을 가지는 객체들을 정렬할 때 사용 -> 기본 정렬 규칙 설정	Collections.sort(List, Comparator) 메서드는 Comparator 타입을 가지는 객체들을 정렬할 때 사용 -> 정렬 규칙을 커스텀하고 싶을 때 사용
패키지	java.lang.package	java.util.package

 

Comparable 예제

 

 

 

Comparator 예제

 

 

 

* compare 메서드 같은 경우 두 번째 매개변수 앞에 첫 번째 매개변수가 오면 음수 값, 두 개의 매개변수 같을 경우 0, 두 번째 매개변수가 첫 번째 매개변수 앞에 오면 양수 값을 반환합니다.

 

버블 정렬 알고리즘

gif 이미지에서도 볼 수 있다시피 순차적으로 탐색하며 정렬을 진행하기 때문에 제일 간단하면서도 무식한 알고리즘입니다.

 

버블 정렬 시간 복잡도

 

• 배열 혹은 리스트가 역순으로 정렬되어있을 때, 최악의 성능을 발휘하며 이때 시간 복잡도는 무려 O(N^2)입니다.
• 반면, 이미 정렬되어있을 경우가 제일 좋은 경우이며 이때 시간 복잡도는 O(N)입니다.

 

버블 정렬 코드

 

 

삽입 정렬 알고리즘

버블 정렬보다 삽입 정렬이 좋은 이유

삽입 정렬 같은 경우 버블 정렬과 달리 새로운 리스트를 생성하고 해당 리스트에 정렬된 결과를 반환합니다.

여기서 반환되는 리스트는 LinkedList 클래스의 인스턴스이기 때문에 배열과 달리 중간에 원소를 삽입하는데 최적화되어 있습니다.

마지막으로, 삽입 정렬은 반환될 리스트가 구성되면 즉시 반환하기 때문에 대체로 버블 정렬보다 좋은 성능을 발휘합니다.

 

삽입 정렬 시간복잡도

• 배열 혹은 리스트가 이미 정렬되어있을 경우, 매번 원소를 삽입할 때마다 새 리스트의 끝까지 반복문을 실행하기 때문에 시간 복잡도는 O(N^2)입니다.
• 반면, 역순으로 정렬되어있을 경우가 제일 좋은 경우이며 이때 시간 복잡도는 O(N)입니다.

 

삽입 정렬 코드

 

 

 

퀵 정렬 알고리즘

기존 알고리즘과 달리 퀵 정렬 알고리즘의 경우 재귀적이며 임시 원소 pivot을 선정하여 해당 원소를 기준으로 정렬을 진행해나갑니다. (gif 사진에서 검은색으로 표시된 원소가 pivot입니다.)

정렬을 진행해나갈 때마다, pivot보다 크거나 같은 원소들, 그리고 pivot보다 작은 원소들로 구분이 됩니다.

 

퀵 정렬 시간 복잡도

• 기존의 정렬 알고리즘과 달리 평균적인 시간 복잡도는 O(NlogN)입니다. -> 두 개의 리스트로 분리하는 시간 복잡도가 O(N)이고, 각각의 재귀 호출은 각 리스트 숫자의 절반만큼의 횟수만 발생하므로 O(NlogN)
• 하지만, 퀵 정렬도 마찬가지로 pivot 선정에 따라 최악의 경우 시간 복잡도가 O(N^2) 일 수 있습니다. 보통 퀵 정렬의 예시 코드에는 pivot을 리스트 내 첫 번째 원소로 선정할 때가 많은데 이럴 경우 리스트가 역순으로 정렬되어 있을 때 최악의 성능을 보입니다. 

 

퀵 정렬 코드

 

 

 

병합 정렬 알고리즘

 

 

 

병합 정렬 알고리즘은 리스트를 두 개로 나누고 각 하위 리스트를 정렬한 후 각각을 하나로 합치는 알고리즘입니다.

즉, 병합 정렬 알고리즘은 분할 정복 (Divide and Conquer) 알고리즘을 적용했습니다.

또한, 퀵 정렬 알고리즘처럼 재귀적으로 구현한 알고리즘입니다.

 

* 자바 표준 라이브러리에 있는 정렬 알고리즘들은 대체로 리스트 크기에 따라 다른 알고리즘을 통해 정렬을 진행하는데 리스트 크기가 작을 경우 삽입 정렬 알고리즘을 사용하고, 리스트 크기가 클 경우 병합 정렬 알고리즘을 사용한다고 합니다.

 

병합 정렬 시간 복잡도

• 퀵 정렬과 달리 최악의 경우에도 시간 복잡도가 O(NlogN)이 나옵니다. -> 리스트 숫자의 절반만큼만 재귀 호출이 발생하고 각각의 리스트를 병합하는데 O(N)이므로 O(NlogN)

병합 정렬 공간 복잡도

• 퀵 정렬과 달리 병합 정렬은 공간 복잡도를 고려해야 합니다.
• 정렬을 하기 위해서는 데이터 전체 크기만 한 메모리가 더 필요한데, 사실 요즘 하드웨어가 워낙 좋기 때문에 더 이상 고려하지 않아도 되는 요소이지 않을까라고 생각합니다.

 

병합 정렬 코드

 

 

 

이진 탐색 알고리즘

 

이진 탐색 알고리즘은 정렬된 리스트 혹은 배열에 적용되는 알고리즘입니다.

 

이진 탐색 시간 복잡도

• 해당 알고리즘의 시간 복잡도는 O(logN)이며 이는 백만 개의 원소가 있을 때 단 20번 미만의 비교로 원하는 원소를 찾을 수 있다는 뜻입니다.

 

 

이진 탐색 코드

 

* 추가적으로, 힙 정렬, 쉘 정렬, 기수 정렬 등이 있는데 개인적인 경험으로는 쉘 정렬 혹은 기수 정렬까지 물어보는 경우는 없었던 것 같습니다. 힙 정렬의 경우 간혹 있었는데, jaimemin.tistory.com/277 를 참고하시길 바랍니다!

 

[출처]

JAVA 프로그래밍 면접 이렇게 준비한다 (한빛미디어)

 

commons.wikimedia.org/wiki/File:Merge-sort-example-300px.gif

File:Merge-sort-example-300px.gif - Wikimedia Commons