[Sort] Intro

오랜만에 글을 쓰러 왔습니다. 왜냐면 그동안 바빴다가 휴학을 했기 때문이죠. 휴학하면서 배웠던 내용도 정리하고, 코딩을 꾸준히 해서 실력을 높여보려 합니다. 오늘은 정렬을 가져와봤습니다.

---

1. 정의

정렬(sort)은 요소(element)들을 특정 기준에 따라 재배열하는 것입니다.

각각의 요소는 (key, info)로 주어집니다.

대표적인 것은 숫자와 문자의 정렬이 있습니다. 이들은 보통 내림차순, 오름차순으로 정렬됩니다.

 

2. 분류

1) Memory usage

Internal(In-memory) sort	$ O(n^2) $ : bubble sort, selection sort, insertion sort $ O(n log{n}) $ : heap sort, quick sort, mergy sort
External sort	based on merge sort

 

정렬의 종류는 메모리 사용 방법에 따라 나눌 수 있습니다.

Internal sort는 main memory를 사용하기 때문에 In-memory라고도 합니다.

$ O(n^2) $과 $ O(n log{n}) $  2가지의 시간복잡도가 있고, 표처럼 나눌 수 있습니다.

이후 코드로 차근차근 알아봅시다.

External sort는 요소의 수가 너무 많은 경우 main memory를 사용하지 못하기 때문에 external memory를 사용하는 정렬입니다. 이 정렬은 mergy sort를 베이스로 합니다.

 

2) Comparison

Comparision sort	bubble sort, selection sort, insertion sort heap sort, quick sort, mergy sort
Non-comparision sort	bucket sort (examines bits of keys) radix sort (examines individual bits of keys) counting sort (indexes using key values)

 

정렬할 때 비교의 여부에 따라 나누기도 합니다.

comparision sort는 오직 key의 관계를 비교하여 정렬하고, non-comparision sort는 key의 특성을 이용하여 정렬합니다.

 

3)  Stability

Stable sort는 중복 키가 존재히도, 그 순서가 바뀌지 않는 정렬을 말합니다.

예를 들어 (3, d) (1, a) (2, c) (2, b)가 주어졌다고 하면,

(1, a) (2, c) (2, b) (3, d)는 순서가 바뀌지 않은 것,

(1, a) (2, b) (2, c) (3, d)는 순서가 바뀐 것으로 볼 수 있습니다.

 

---

이번 글에선 정렬의 정의와 종류를 알아보았습니다. 다음 글에서부턴 소개한 정렬을 코드와 함께 정리해보겠습니다!