먼저 정렬 알고리즘이란

컴퓨터 과학과 수학에서 정렬 알고리즘(sorting algorithm)이란 원소들을 번호순이나 사전 순서와 같이 일정한 순서대로 열거하는 알고리즘이다. (출처: 위키피디아)

정렬에 들어가기 전에 2가지 개념에 대해 먼저 설명하려고 한다.
첫 번째는 Stable이고 두 번째는 In-place이다.

안정 정렬(Stable Sort)

중복된 키를 순서대로 정렬하는 정렬 알고리즘을 뜻한다.

예를 들어, 다음과 같은 list가 있다고 하자.

list=[1, 7, 3, 5, 4, 7, 9

이 리스트에서 7이 두번 나온다. 구분을 위해 ()를 이용해 앞은 (1), 뒤는 (2)를 표시하면

list=[1, 7(1), 3, 5, 4, 7(2), 9

와 같다.

이때 이 리스트를 정렬했을 때
(1) list=[1, 3, 4, 5, 7(1), 7(2), 9
(2) list=[1, 3, 4, 5, 7(2), 7(1), 9

(1)처럼 나오면 안정(Stable) 정렬, (2)처럼 나오면 불안정(Unstable) 정렬이라고 한다.

즉, 정렬을 했을 때 중복된 값들의 순서가 변하지 않으면 안정(Stable) 정렬, 변하면 불안정(Unstable) 정렬인 것이다.

대표적인 알고리즘들
Stable Sorting 알고리즘은 다음과 같다:

• Insertion Sort
• Merge Sort
• Bubble Sort
• Counting Sort

Unstable Soring 알고리즘:

• Selection sort
• Heap Sort
• Shell Sort
• Quick Sort

In-place Algorithm

In-place 알고리즘이란 원소들의 개수에 비해서 충분히 무시할 만한 저장 공간만을 더 사용하는 정렬 알고리즘. 아마 학교에서는 제자리성(혹은 제자리 정렬)과 같은 이름으로 들어봤을 수도 있겠다. (출처: 위키피디아)

헷갈리면 정렬들을 공부하다보면 이해가 될 것이니 일단은 추가적인 메모리 공간이 거의(아예가 아니다) 안 드는 정렬이라고만 알고 있자.

대표적인 알고리즘들
In-place Sorting 알고리즘

• Insertion Sort
• Selection Sort
• Bubble Sort
• Shell Sort
• Heap Sort
• Quick Sort(정렬 알고리즘-4.2: 정의에 따라서 Not in place sorting으로 볼 수도 있으나 흔히 In-place로 본다.)

Not in place Sorting 알고리즘

• Merge Sort
• Counting Sort
• Radix Sort
• Bucket Sort

그러면 다음장부터 본격적으로 정렬에 대해 살펴보자.

---

📑 참고 사이트

• 정렬 알고리즘 - 위키피디아

• Dojin Kim님 블로그 - Stable Sort, inplace algorithm이란? 왜 중요한가?