우아한테크코스 테코톡
아스피의 정렬 알고리즘
카테고리 : 우아한테크코스 테코톡
아스피의 정렬 알고리즘
정렬
- 정렬이란?
- 데이터를 기준에 맞게 순서대로 배열하는 작업
- 정렬을 하는 이유
- 탐색에 용이하기 위해서
탐색에 용이?
- 정렬된 리스트가 있다면 순차 탐색이 아닌 이분 탐색을 사용할 수 있게 된다.
정렬 알고리즘의 종류
- 선택 정렬(Selection Sort)
- 삽입 정렬(Insertion Sort)
- 버블 정렬(Bubble Sort)
- 병합 정렬(Merge Sort)
- 힙 정렬(Heap Sort)
- 퀵 정렬(Quick Sort)
Insertion Sort
- 개념
- 요소를 이미 정렬된 앞 부분 배열에서 자리를 찾아 삽입하는 정렬
- 방식
- 매 매순서마다 해당 요소를 앞의 정렬된 배열에서 삽입할 수 있는 위치를 찾아 해당 위치에 넣는다.
- 해당 위치에 있던 요소부터 뒤의 요소들은 한 칸씩 밀리다.
- 장점
- 안정한 알고리즘
- 이미 정렬이 많이 되어 있는 상황에서 유리
- 데이터 수가 적을수록 방식이 간단해서 유리
- 단점
- 데이터 수가 많다면 비효율적
- 삽입하려면 그 뒤에 있는 데이터들을 전부 밀어야하기 때문에 이동이 많음
- 시간 복잡도
- 최선: O(n) -> 이미 모든 데이터가 정렬되어 있는 경우
- 평균, 최악: O(n^2)
Merge Sort
- 개념
- 분할 정복(Divide And Conquer) 알고리즘
- 배열을 가운데 기준으로 분할한 뒤 병합 시에 정렬
- 방식
- 배열이 더 이상 쪼개지지 않을 때(요소가 하나일 때)까지 반으로 분할한다.
- 분할되 부분 배열들은 분할한 순서에 맞게 병합한다. 이 과정에서 정렬이 이루어진다.
- 최종적으로 병합이 완료되면 배열이 정렬되어 있다.
- 장점
- 안정한 알고리즘
- 성능이 데이터 분포에 영향을 덜 받음(어떤 데이터가 들어와도 시간복잡도가 같다)
- Linked List 를 이용하면 제자리 정렬이 가능
- 단점
- 배열을 이용해서 구현하면 데이터의 크기만큼 임시 배열이 필요
- 시간 복잡도
- 최선, 평균, 최악: O(n*logn)
Quick Sort
- 개념
- 분할 정복 알고리즘
- 임의의 Pivot 을 정하고 해당 값보다 작은 값은 왼쪽, 큰 값은 오른쪽 분할
- 비균등 분할
- 방식
- 배열에서 Pivot 을 정한다.
- Pivot 보다 작은 값은 Pivot 의 왼쪽으로 몰고, 큰 값은 오른쪽으로 몬다.
- Pivot 을 기준으로 양쪽으로 분할된 배열들을 1~2 과정을 반복한다.
- 분할할 수 없으면 정렬이 완료된다.
- 장점
- 일반적으로 가장 빠른 정렬 알고리즘
- 교환에 있어서 공간이 따로 필요없기 때문에 공간복잡도가 우수함
- 단점
- 불안정한 정렬 알고리즘
- 이미 정렬된 배열에 적용할 경우, 최악 O(n^2) 의 시간복잡도가 나온다.
- 시간 복잡도
- 최선, 평균: O(n*logn)
- 최악: O(n^2)
JAVA 에서의 Sort
- Dual Pivot Quick Sort
- primitive 타입을 정렬할 때, Dual Pivot Quick Sort 를 사용한다.
- 피복을 하나만 쓰는 것보다 일반적으로 빠르다.
- Tim Sort
- Object 타입을 정렬할 때, Tim Sort 를 사용한다.
- 앞에서 봤던 Insertion Sort 와 Merge Sort 의 하이브리드한 형태
- Binary Insertion Sort 를 사용한다.
- Merge Sort 와 같이 분할을 진행하다가 특정한 기준보다 작은 사이즈가 되면 분할을 멈추 후, Binary Insertion Sort 를 이용한다.
- 특정 변합 조건에 맞게 병합
