정렬

선택 정렬

• 제자리 정렬 알고리즘 중 하나
• 가장 작은 것을 선택해 앞으로 보내는 과정을 N-1번 반복함
• 시간 복잡도 O(N²)
• 매우 비효율적

1. 주어진 데이터 중 작은 데이터 찾기

2. 맨 앞의 데이터와 교체

3. 맨 앞의 데이터를 뺀 나머지 데이터들을 같은 과정으로 교체

 

삽입 정렬

• 필요할 때만 위치를 바꿈
• 데이터가 정렬되어 있을 때 효율적
• 특정한 데이터를 적절한 위치에 삽입함
• 두 번째 데이터부터 시작 ( 첫 번째 데이터는 그 자체로 정렬되어 있다고 판단함)
• 정렬이 이뤄진 데이터는 항상 오름차순을 유지하고 있음
• 시간 복잡도 O(N²) (최선의 경우 O(N), 정렬이 거의 되어있는 경우 퀵 정렬보다 강력함)

1. 두 번째 데이터부터 앞에서부터 차례대로 비교하며 자신이 들어갈 부분을 찾음

2. 그 위치에 데이터 삽입하기 위해 한 칸씩 뒤로 이동시킴

3. 위의 과정을 반복

 

퀵 정렬

• 합병 정렬과 더불어 정렬 라이브러리의 근간이 되는 알고리즘임 (빨라서)
• 불안정 정렬, 비교 정렬에 속함
• 분할 정복 알고리즘의 하나 (합병 정렬과 달리 리스트를 비균등하게 분할함)
• 기준을 설정한 후 큰 수와 작은 수를 교환해 리스트를 반으로 나누는 방식으로 동작함
• 시간복잡도는 평균적으로 O(NlogN) (선택, 삽입 정렬보다 빠른 편)
• 이미 데이터가 정렬되어 있는 경우 매우 느리게 동작함 (최악의 경우 O(N²))

- 현재 배열의 데이터 개수가 1일 때 퀵 정렬이 끝남 (조건)

1. 맨 처음

1.  배열의 첫 번째 데이터를 피벗(기준)으로 설정함
2.  왼쪽에서부터 피벗보다 큰 데이터 선택, 오른쪽에서부터 피벗보다 작은 데이터 선택해 두 데이터의 위치 변경
3.  그 다음 피벗보다 큰 데이터, 작은 데이터 찾고 위치 변경
4.  반복하다가 왼쪽에서부터 찾는 값, 오른쪽에서부터 찾는 값 엇갈리는 경우 작은 데이터와 피벗의 위치를 변경
5.  피벗값을 기준으로 왼쪽 값은 모두 피벗보다 작은 값, 오른쪽은 큰 값으로 분할됨

2. 왼쪽 배열을 앞의 방법으로 정렬

3. 오른쪽 배열을 앞의 방법으로 정렬

 

합병 정렬

• 분할 정복 알고리즘의 하나
• 안정 정렬에 속함
• 분할, 정복, 결합 3 과정으로 이루어져 있음
• 두 개의 배열을 합치는 과정에서 실제 정렬이 이뤄짐
• 시간 복잡도 O(NlogN)

1. 분할 (Divide)

배열을 같은 크기의 2개의 배열로 분할함

2. 정복 (Conquer)

1. 배열 크기가 0이나 1이 아니면 분할 과정을 반복함 (재귀)
2. 분할한 배열을 정렬함

3. 결합 (Combine)

정렬된 배열을 하나로 합병함

 

계수 정렬

• 특정한 조건일 때만 사용 가능하지만 매우 빠름
• 데이터의 개수가 N, 최댓값이 K일 때 최악의 경우 시간 복잡도 O(N+K) 보장함
• 데이터의 크기 범위가 제한되어 있어 정수 형태로 표현 가능할 때에만 사용 가능
• 일반적으로 max와 min이 1,000,000을 넘지 않을 때 효과적 사용 가능
• 모든 범위를 담을 수 있는 크기의 배열을 선언해야 함
• 사용하는 대표적 경우는 알파벳으로 이뤄진 suffix array 구하기
  (접미사 배열 - 어떤 문자열의 접미사를 사전식 순서대로 나열한 배열)
• 공간 복잡도 O(N+K)

1. 배열의 각 데이터가 몇 번 등장했는지 횟수 저장함 (count)

2. 배열에 저장한 횟수를 누적 count로 바꿔줌

3. input 배열의 값을 누적 count 자리에 넣고 count--를 해줌 (다음 값은 count-1 자리에 넣어야 해서)

4. 3번을 반복함

 

- 이해하기 쉬운 애니메이션 링크

https://www.cs.miami.edu/home/burt/learning/Csc517.091/workbook/countingsort.html