안정정렬, 불안정 정렬, 제자리 알고리즘 / Stable Sort, Unstable Sort, In-place Algorithm

정렬 알고리즘을 공부하다보면 나오는 용어들입니다.

이 정렬 알고리즘의 특징은 Stable sort이고, in-place 알고리즘을 가진다 라고 말이죠..

그렇다면 이 두 용어의 뜻은 무엇일까요?​​

​

Stable Sort(안정 정렬) / UnStable Sort(불안정 정렬)

 

Stable Sort가 뭘까요?

번역하면 안정적인 정렬... 안정적... 뭐가 안정적이란 말일까요?​​

 

음식 맛이 안정적이라는 건가?

 

안정정렬이란 중복된 키를 순서대로 정렬하는 알고리즘을 말합니다.

​

예를들어 아래와 같은 배열이 있다고 생각합시다.

 

이 배열에서는 중복된 숫자 1과 4가 존재합니다.

 

좀더 시각적으로 확인하기 위해 (1) (2) 이런식으로 어떤게 먼저 나온건지 구분을 하도록 하겠습니다.

이 배열을 정렬하였을때

​이런식으로 나온다면 Stable Sort (안정 정렬)

​위와 같이 나온다면 UnStable Sort (불안정 정렬) 이라고 부릅니다.

​

즉 정렬을 하였을때 중복된 값들의 순서가 변하지 않는다면 안정(Stable)정렬, 변하면 불안정(Unstable)정렬 이라고 말하는 것입니다.​

 

대표적인 알고리즘

Stable Sort

1. Insertion Sort (삽입 정렬)
2. Merge Sort (합병 정렬)
3. Bubble Sort (거품 정렬)
4. Counting Sort (계수 정렬)​

​Unstable Sort

1. Selection Sort (선택 정렬)
2. Heap Sort (힙 정렬)
3. Shell Sort (셸 정렬)
4. Quick Sort (퀵 정렬)

​​

 

In-place Algorithm (제자리 알고리즘)

 

In-place 알고리즘은 원소들의 개수에 비해서 충분히 무시할만한 저장 공간만을 더 사용하는 정렬 알고리즘을 말합니다.

즉 정렬을 하기위해 추가적인 메모리 공간이 거의 들지 않는 정렬알고리즘 이라고 생각하시면 됩니다.

음.. 잘 이해가 안가시나요?

​

https://blog.naver.com/cjy2103/222903766085

자바(Java) 정렬 - 버블정렬, 거품정렬 (bubble sort)

 

 

정말 간단하면서 다들 공부하셨을 거라고 생각되는 버블 정렬 알고리즘을 생각해볼까요?

저희가 정렬을 하기위해서 무엇이 필요했나요?

loop문을 제외하고 값을 변경하기전 저장하기 위한 변수 하나가 필요했죠?

​

변수 하나라고 해봤자 메모리 공간을 얼마나 차지할까요?

(당연히 거의 들지 않겠죠?)

이렇게 이해를 하시면 됩니다.

 

대표적 알고리즘

 

In-Place Sort

1. Insertion Sort (삽입 정렬)
2. Selection Sort (선택 정렬)
3. Bubble Sort (거품 정렬)
4. Shell Sort (셀 정렬)
5. Heap Sort (힙 정렬)
6. Quick Sort (퀵 정렬)

 

Not In-place Sort

1. Merge Sort (합병 정렬)
2. Counting Sort (계수 정렬)
3. Radix Sort (기수 정렬)
4. Bucket Sort (버킷 정렬)