[CS] 정렬 sort

O(n^2)

버블 정렬

0번가 1번 / 1번과 2번 / 3번과 4번 계속 비교하며 가장 큰 수를 우측으로 이동시킨다.
다시 0번 부터 n - 1 까지 2번째로 큰 수를 우측으로 이동시킨다.

왜 버블인가?

- 원소들이 거품처럼 올라오는 것처럼 보여서 버블 정렬

선택 정렬

전체를 훑어서 가장 작은 수를 처음에 넣는다.
다시 전체를 훑어서 그 다음으로 작은 수를 그 다음에 넣는다.
마지막까지 수행해서 모든 수를 정렬한다.

왜 선택 정렬인가?

- 위치를 선택해서 어울리는 수를 찾는 거라서 선택 정렬

삽입 정렬

정렬된 배열을 점차 늘려가는 방향으로 배열한다.
0 ~ k 번째까지 정렬된 배열이고 k + 1 번째 수를 정렬해야한다면
0 ~ k 사이에서 k + 1 번째 수의 위치를 찾아 삽입한다.

왜 삽입 정렬인가?

- 새로운 수가 삽입 되는 형태의 정렬이라서

** Swift에서 정렬 알고리즘은 modified Timsort를 사용하고 있다. 

이 때 사용되는 알고리즘 중 하나가 이진 삽입 정렬(Binary Insertion Sort) 이다. 자세히 알고 싶음 더보기를 통해 알아보자

 

삽입 정렬에서 새로운 숫자를 삽입 해야 할 때 이미 정렬된 배열을 모두 훑어야 했다.

이 때 이진 삽입 정렬은 모두 훑는 것이 아니라 이진 탐색을 통해 새로운 숫자 넣는 곳을 찾는 것이다.

이를 통해서 O( n log n )이 나온다. 하지만 최악의 경우 O (n ^2 ) 이 나온다. ( 오름차순 정렬을 원할 때 배열이 내림차순으로 정렬된 경우)

아래 유튜브가 아주 잘 설명해주고 있다.

 

O(n log n)

병합정렬 / 합병정렬

원소가 1개 혹은 0개가 될 때까지 쪼갠다.
쪼개고 난 후에 다시 합치면서 정렬을 한다.

왜 병합정렬인가?

- 나누고 합치는 정렬이기에

힙 정렬

말 그대로 힙을 이용한 정렬이다.
항상 같은 정렬의 성능을 발휘한다.

퀵 정렬

피벗을 배열의 끝(처음 혹은 마지막)으로 정하고 피벗을 기준으로 피벗보다 큰 배열, 작은 배열로 나눈다.
나눠진 배열을 다시 퀵 정렬을 시도한다.
배열의 크기가 1이거나 0일 때 까지 반복한다.

최악의 경우 n^2이 나온다.

하지만 평상시의 정렬에서 가장 최적의 성능이 나온다.

왜 퀵 정렬인가?

- 비교 연선자를 사용하는 정렬 중에서 가장 빠른(퀵) 정렬

 

추가적인 사항

왜 퀵 정렬이 힙 정렬보다 빠르다는 것일까?

- 퀵 정렬이 메모리 친회적이여서 그렇다.( 퀵 기준: 옆 집 메모리가 내 다음 인덱스 ) 힙 정렬은 메모리가 분산되어 있기 때문이다.

Swift 에서는 무슨 정렬을 사용하고 있을까?

- modified Timsort