[Algorithm] Sorting(정렬)

그 동안 배운 자료구조를 통해 데이터를 다루는 방법에 대해 알아 보도록 하겠다.

이번 시간에는 정렬에 대해서 먼저 설명하겠다.

정렬 알고리즘이란?

가장 기본적으로 자료 구조에 정의된 데이터들을 어떻게 정렬할 수 있는지에 대해서 알아보자. 정렬 알고리즘은 다양하게 존재하는데 우선 기본적인 종류는 다음과 같다.

1) 간단하지만(simple) 느린(slow) 방식

• Bubble Sort
• Selection Sort
• Insertion Sort

2) 약간 복잡하지만 빠른 방식

• Shell Sort
• Merge Sort
• Quick Sort
• Heap Sort

3) 아주 빠르지만 제한적으로만 사용 가능한 방식

• Counting Sort
• Radix Sort
• Bucket Sort

4) 기타 필요에 따라 사용되는 방식

• Topological Sort

정렬 알고리즘은 특정 방식에 따라 여러 종류로 나뉠 수 있다.

실행 방법에 따라

• 비교식(Comparative) 정렬
  • 비교식 정렬은 정렬을 수행하면서 두 개의 데이터를 서로 비교하여 필요하면 교환하는 방식으로 실행한다.
• 분산식(Distribute) 정렬
  • 정렬할 데이터를 부분적으로 나누어 분해한 뒤 다시 그 집합을 정렬하고 합치면서 전체를 정렬하는 방식이다.

정렬 장소에 따라

• 내부(Internal) 정렬
  • 내부 정렬은 정렬 자료를 메인 메모리에 저장하며 정렬하여 속도가 빠르지만 용량에 따라 수행가능한 수준이 제한적이다.
• 외부(External) 정렬
  • 외부 정렬은 정렬 자료를 보조 기억장치에서 정렬하며 대용량이므로 큰 데이터를 정렬할 수 있지만 속도는 제한적이다.

저장되는 방식에 따라

• 안정(Stable) 정렬
  • 안정 정렬은 정렬이 진행됨에 따라 같은 수준의 순서를 갖는 객체를 정렬할 때는 원래의 순서를 바꾸지 않는 정렬 방식이다. 예를 들어, 객체 A와 B는 순서상으로 완전히 동일하다면 정렬이 끝난 뒤와 정렬 전의 A, B의 순서는 유지되는 경우를 의미한다.
• 불안정(Unstable) 정렬
  • 불안정 정렬은 해당 내용이 반드시 유지되지 않을 수 있는 모든 정렬을 의미한다.

메모리 사용 방식에 따라

• In-Place 정렬
  • In-place 정렬은 데이터를 정렬 시 입력된 n 사이즈의 크기 배열 공간이 추가로 필요하지 않은 경우이다.
• Out-of-place 정렬
  • Not-in-place라고도 하며, 정렬 시에 기존 데이터가 저장된 배열 외에 추가적인 공간을 더 필요로 하는 경우를 의미한다.

안정 정렬 / 불안정 정렬, 그리고 In-place 정렬/ Out-of-place 정렬에 대해서 더 자세히 알아보자.

안정(stable) 정렬 vs. 불안정(unstable) 정렬

앞서 말했듯 저장되는 방식에 따라 안정 정렬과 불안정 정렬로 구분되어 있다.

아래와 같은 리스트를 생각해 보자.

이 리스트에는 1이라는 중복된 데이터가 들어있어 a와 b로 표시하여 구분하였다. 이 리스트를 정렬해 보도록 하겠다.

첫 번째 리스트는 중복된 숫자의 순서까지도 보장이 되어 정렬된 모습이고 두 번째 리스트는 그렇지 못한 모습입니다. 이 때, 첫 번째 리스트를 안정 정렬 되었다 하고 두 번째 리스트를 불안정 정렬 되었다 합니다.

이번 예시는 중복된 숫자로 예시를 들어 크게 와닿지 않을 수 있다.(이게 왜 필요한 거지?라는 의문) 그래서 더 이해하기 쉬운 예시를 들어보겠다.

아래와 같이 이름 순으로 정렬 된 파일이 있다고 가정하자.

이름 순 정렬
국어과제1.pdf	2021-06-01
국어과제2.pdf	2021-06-01
영어과제1.pdf	2021-04-01
영어과제2.pdf	2021-04-01
한문과제1.pdf	2021-07-01
한문과제2.pdf	2021-07-01

이 파일들을 날짜 순으로 재 정렬 해 보자.

중복된 날짜가 있을 때 안정 정렬을 하게 되면 아래와 같이 이름 순으로 정렬 된 파일을 보장 받는다.

날짜 순 정렬(안정)
영어과제1.pdf	2021-04-01
영어과제2.pdf	2021-04-01
국어과제1.pdf	2021-06-01
국어과제2.pdf	2021-06-01
한문과제1.pdf	2021-07-01
한문과제2.pdf	2021-07-01

반면 불안정 정렬로 하게 되면 아래와 같이 날짜 순으로는 정렬이 되지만 파일의 이름 순으로 정렬되어 있는 것은 보장 받지 못한다.

날짜 순 정렬(안정)
영어과제2.pdf	2021-04-01
영어과제1.pdf	2021-04-01
국어과제2.pdf	2021-06-01
국어과제1.pdf	2021-06-01
한문과제2.pdf	2021-07-01
한문과제1.pdf	2021-07-01

In-place 정렬 vs. Out-of-place 정렬

구현 방식에 따라 In-place 정렬과 Out-of-place 정렬로 나뉘게 된다.

In-place 정렬은 원본 데이터 내에서 정렬이 이루어 지게 되는 정렬을 말하는 것이고 원본 데이터가 아닌 새로운 배열로 정리된 output 결과를 만드는 것을 Out-of-place 정렬이라고 한다.

따라서 정렬을 할 때에는

• 시간 복잡도
• 안정/ 불안정 정렬
• 구현 방식
• 저장되는 방식

위와 같은 것들을 생각하여 정렬이 진행된다.

정렬 간 시간복잡도 비교

정렬 방식	Average	Worst	Memory	Stable 여부	In-Place 여부	Run-time(정수 60,000개) 단위: sec
Bubble 정렬	O(n2)	O(n2)	O(1)	O	O	7.438
Selection 정렬	O(n2)	O(n2)	O(1)	X	O	10.842
Insertion 정렬	O(n2)	O(n2)	O(1)	O	O	22.894
Shell 정렬	O(nlog2n)	O(n2)	O(1)	X	O	0.056
Merge 정렬	O(nlog2n)	O(nlog2n)	O(n)	O	X	0.014
Quick 정렬	O(nlog2n)	O(n2)	O(1)	X	O	0.034
Heap 정렬	O(nlog2n)	O(nlog2n)	O(1)	X	O	0.026

Bubble 정렬의 설명은 이곳을 참조

Insertion 정렬의 설명은 이곳을 참조

Shell 정렬의 설명은 이곳을 참조

Merge 정렬의 설명은 이곳을 참조

Quick 정렬의 설명은 이곳을 참조

Heap 정렬은 우선순위 큐에서 사용하는 정렬이므로 해당 포스팅 이곳을 참조

Counting 정렬의 설명은 이곳을 참조

Radix 정렬의 설명은 이곳을 참조

Bucket 정렬의 설명은 이곳을 참조

Topological 정렬의 설명은 이곳을 참조