[코딩테스트] Java - 정렬(Sort)

정렬

- 정렬(sort): 사용자가 정의한 순서로 데이터를 나열하는 것

- 정렬이 필요한 이유: 원하는 데이터를 쉽게 찾기 위함

- 정렬의 분류: 비교 정렬(comparison sort)와 비비교 정렬(non-comparison sort)

 

(버블 정렬)

- 버블 정렬(bubble sort): 

- 시간복잡도: 

 

(선택 정렬)

- 선택 정렬(selection sort): 

- 시간복잡도: 

 

(삽입 정렬)

- 삽입 정렬(insertion sort): 데이터의 전체 영역에서 정렬된 영역과 정렬되지 않은 영역을 나누고 정렬되지 않은 영역의 값을 정렬된 위치로 놓으면서 정렬

- 시간복잡도: 최악 O(N^2) 최선 O(N)

1. 최초에 정렬된 영역은 왼쪽 1개, 정렬되지 않는 영역을 나머지로 함. 현재 위치는 0으로 설정

2. 현재 위치의 값과 이후 값들을 모두 비교하며 가장 작은 값을 현재 위치와 교환. 현재 위치는 1 증가

3. 정렬이 마무리될 때까지 과정2를 반복

 

(병합 정렬)

- 병합 정렬(merge sort): 정렬되지 않은 영역을 쪼개서 각각의 영역을 정렬하고 이를 합치며 정렬. divide and conquer 

- 시간복잡도: O(NlogN)

 

(퀵 정렬)

- 퀵 정렬(quick sort):

- 시간복잡도: 

 

(힙 정렬)

- 힙 정렬(heap sort): 힙 자료구조를 사용하여 정렬

- 힙(heap): 특정한 규칙이 있는 이진 트리. 최대힙은 부모 노드가 자식 노드보다 크고, 최소힙은 부모 노드가 자식 노드보다 작음

- 시간복잡도: O(NlogN)

 

(계수 정렬)

- 계수 정렬(counting sort): 데이터에 의존하는 정렬. 데이터의 빈도수로 정렬

- 시간복잡도: O(N + K). K는 최댓값 - 최솟값(범위)

 

(위상 정렬)

- 위상 정렬(topological sort): 특정 그래프에서 방문 순서를 결정하는 알고리즘. 간선 방향이 있는 방향 비순환 그래프(DAG)에서만 사용

- 진입차수: 자신을 향한 화살표의 개수

- 시간복잡도: O(|V| + |E|)

1. 

 

예시

(버블 정렬)

 

(계수 정렬)

 

(병합 정렬)