cs-js-13-알고리즘-정렬(Sort)

SeungWoo Yoo ·2023년 2월 7일

DataAlgo

JS-자료구조-알고리즘

목록 보기

13/16

1. 정렬

만약 구슬들을 크기 별로 나열해야 한다면?
제일 큰 것부터 찾거나 일단 분류해서 정리하는 등의 행동들을 할 것입니다. 이러한 행동을 정렬이라고 부릅니다.

정렬 : 요소들을 일정한 순서대로 열거하는 알고리즘

1.1 정렬의 특징

정렬 기준은 사용자가 정할 수 있다. (e.g. 오름차순, 내림차순)
크게 비교식과 분산식으로 나눌 수 있다.
대부분의 언어가 빌트인으로 제공해준다.
삽입, 선택, 버블, 머지, 힙, 퀵 정렬 등 다양한 정렬 방식이 존재한다.

1.2 어떤 정렬이 제일 빠를까?

정렬들은 각각 유리하고, 불리한 상황이 존재하기 때문에 무엇이 좋고 나쁜지는 정해져 있지 않습니다.

https://www.toptal.com/developers/sorting-algorithms

2. 비교식 정렬

다른 요소와 비교를 통해 정렬을 하는 방식

2.1 버블 정렬(Bubble Sort)

서로 인접한 두 요소를 검사하여 정렬하는 알고리즘
$O(n^2)$ 시간복잡도를 가진다.

Data Structure_13_1

배열을 오름차순으로 정렬

첫 번쨰 정렬
- 첫 번쨰 요소에 인접한 요소를 비교합니다.
  - 4 < 7 이기 때문에 오름차순에 따라 두 요소를 교환합니다.
- 교환 후 2번쨰 요소와 3번째요소를 비교합니다.
  - 5 < 7 이기 때문에 오름차순에 따라 두 요소를 교환합니다.
- 교환 후 3번쨰 요소와 4번째요소를 비교합니다.
  - 1 < 7 이기 때문에 오름차순에 따라 두 요소를 교환합니다.
- 교환 후 4번쨰 요소와 5번째요소를 비교합니다.
  - 3 < 7 이기 때문에 오름차순에 따라 두 요소를 교환합니다.
두 번째 정렬
- 첫 번쨰 요소에 인접한 요소를 비교합니다.
  - 4 < 5 이기 때문에 교환하지 않습니다.
- 2번쨰 요소와 3번째요소를 비교합니다.
  - 1 < 5 이기 때문에 오름차순에 따라 두 요소를 교환합니다.
- 교환 후 3번쨰 요소와 4번째요소를 비교합니다.
  - 3 < 5 이기 때문에 오름차순에 따라 두 요소를 교환합니다.
세 번째 정렬
- 첫 번쨰 요소에 인접한 요소를 비교합니다.
  - 1 < 4 이기 때문에 오름차순에 따라 두 요소를 교환합니다.
- 2번쨰 요소와 3번째요소를 비교합니다.
  - 3 < 4 이기 때문에 오름차순에 따라 두 요소를 교환합니다.
네 번쨰 정렬
- 첫 번쨰 요소에 인접한 요소를 비교합니다.
  - 1 < 3 이기 때문에 교환하지 않습니다.
- 마무리!

결국 버블 정렬은 n-1번 순회하면 정렬이 마무리됩니다.

2.2 선택 정렬(Selection Sort)

사람이 이해하기 가장 단순한 정렬
선택한 요소와 가장 우선순위가 높은 요소를 교환하는 정렬 알고리즘
$O(n^2)$ 시간복잡도를 가진다

Data Structure_13_2

선택된 첫 번째 요소와 나머지 요소 중 가장 우선순위가 높은 1과 교환합니다.
다음 두 번쨰 요소와 나머지 요소 중 가장 우선순위가 높은 3과 교환합니다.
다음 세 번쨰 요소와 나머지 요소 중 가장 우선순위가 높은 4와 교환합니다.
다음 네 번쨰 요소와 나머지 요소 중 가장 우선순위가 높은 5와 교환합니다.

참고로 나머지 요소 중 선택된 요소보다 우선순위가 높은 요소가 없다면, 교환하지 않고 넘어가면 됩니다.

2.3 삽입 정렬(Insertion Sort)

선택한 요소를 삽입할 수 있는 위치를 찾아 삽입하는 방식의 정렬 알고리즘
$O(n^2)$ 시간복잡도를 가진다.

Data Structure_13_3

7, 4, 5, 1, 3순의 배열을 정렬해보겠습니다. 두 번째 요소부터 시작합니다.

두 번째 요소인 4부터 선택합니다.
- 4 < 7 이기 때문에 오름차순에 따라 첫 번쨰 요소에 4을 삽입합니다.
세 번째 요소인 5를 선택합니다.
- 5 < 7 이기 때문에 오름차순에 따라 두 번쨰 요소에 5을 삽입합니다.
- 다음으로 첫 번째 요소와 비교합니다.
- 4 < 5 이기 때문에 오름차순에 따라 밀어내지 못하고 5가 그대로 있습니다.
네 번째 요소인 1를 선택합니다.
- 1 < 7 이기 때문에 오름차순에 따라 세 번쨰 요소에 1을 삽입합니다.
- 1 < 5 이기 때문에 오름차순에 따라 두 번쨰 요소에 1을 삽입합니다.
- 1 < 4 이기 때문에 오름차순에 따라 첫 번쨰 요소에 1을 삽입합니다.
다섯 번째 요소인 3를 선택합니다.
- 3 < 7 이기 때문에 오름차순에 따라 네 번쨰 요소에 3을 삽입합니다.
- 3 < 5 이기 때문에 오름차순에 따라 세 번쨰 요소에 3을 삽입합니다.
- 3 < 4 이기 때문에 오름차순에 따라 두 번쨰 요소에 3을 삽입합니다.
- 1 < 3 이기 때문에 오름차순에 따라 밀어내지 못하고 1이 그대로 있습니다.

3. 분산식 정렬

요소를 분산해서 정렬하는 방식

3.1 분할 정복(Divide / Conquer)

Data Structure_13_4

문제를 작은 2개의 문제로 분리하고 더 이상 분리가 불가능할 떄 처리한 후 합치는 전략
정렬 뿐만 아니라 다양한 알고리즘에 응용된다.

3.2 합병 정렬(Merge Sort)

분할 정복 알고리즘을 이용한 최선과 최악이 같은 안정적인 정렬 알고리즘
선형 로그( $O(n\ log\ n)$ ) 시간복잡도를 가진다.

Data Structure_13_5

요소를 나누는 작업부터 먼저 시작합니다. (Divide)
- 8개의 요소를 절반으로 나누고, 요소가 1개가 남을 떄까지 계속 절반으로 나눈다.
모든 요소를 나눴다면 합치는 작업을 시작합니다. (Conquer)
- 나눈 것을 합치면, 두 요소 중 작은 것을 먼저 배치합니다.
- 21과 10의 경우 10이 먼저 배치되고 21이 배치됩니다.
- 이어서 2개까지를 합칠 떄도 작은 순으로 배치합니다.
- 최종적으로 모두 합치면 정렬된 상태가 됩니다.

3.3 퀵 정렬(Quick Sort)

분할 정복 알고리즘을 이용한 매우 빠르지만 최악의 경우가 존재하는 불안정 정렬
선형 로그( $O(n\ log\ n)$ ) 시간복잡도를 가진다.
최악의 경우 2차( $O(n^2)$ ) 시간복잡도를 가진다.

Data Structure_13_6

피벗이라는 기준으로 좌측과 우측을 나눕니다.
- 여기서는 첫 번쨰 요소인 5를 피벗으로 둡니다.
- 5를 기준으로 작은 값이 왼쪽, 큰 값이 오른쪽에 배치됩니다.
다시 나뉜 배열에서 각 첫 번쨰 요소가 피벗이 됩니다.
- 각각 1과 9가 피벗이 됩니다.
다시 나뉜 배열에서 각 첫 번쨰 요소가 피벗이 됩니다.
더 이상 나눌 수 없는 상태가 되었다면, 그대로 합쳐줍니다.

4. JS에서 정렬(sort)

JavaScript에서는 정렬이 매우 간단합니다.

const array = [5, 9, 10, 3, 8, 3, 2];

// 다음과 같이 그냥 정렬하면 ASCII 문자 순서로 정렬되어
// 우리가 원하는 숫자 크기대로 정렬되지 않는다.
array.sort();
console.log(array); // [10, 2, 3, 3, 5, 8, 9]
// 10이 먼저 나오는 이유는 ASCII 문자 '1'이 '2'보다 작기 때문

array.sort((a, b) => a - b); // 오름차순 정렬
console.log(array); // [2, 3, 3, 5, 8, 9, 10]

array.sort((a, b) => b - a); // 내림차순 정렬
console.log(array); // [10, 9, 8, 5, 3, 3, 2]