정렬 정렬 정렬

정렬(Sorting)이란?

데이터를 특정한 기준에 따라서 순서대로 나열하는 것을 말한다. 프로그램에서 어떤 식으로든 오름차순 혹은 내림차순으로 데이터를 정렬하여 사용하는 경우가 많기에 정렬 알고리즘은 프로그램을 작성할 때 많이 쓰이는 알고리즘 중 하나다. 또 정렬 알고리즘은 이진탐색의 전처리 과정이기도 하니 이진탐색을 이해하기 위해서라도 제대로 알아야 한다.

 

정렬의 종류?

정렬 알고리즘은 그 역사가 길기에 굉장히 다양한 알고리즘이 존재한다. 그 중 많이 쓰이는 것들에 대해서만 정리해본다. 

 

 1. 선택 정렬

 

 2. 삽입 정렬

 

 3. 퀵 정렬

 

 4. 계수 정렬

 

 5. 버블 정렬

 

 6. ... etc

 

 

1. 선택 정렬 (Selction Sort)

선택 정렬이라는 이름은 매번 가장 작은것을 '선택' 한다는 의미에서 지어졌다. 밑의 <그림1>과 같이 0부터 9까지 10장의 숫자 카드가 무작위로 나열된 경우를 생각해보자. 우리 인간은 숫자 카드를 빠르게 눈으로 흝고, 0부터 9까지의 숫자라는걸 알아챈 다음 오름차순으로 나열할 수 있다.

 

하지만 이 경우 컴퓨터는 데이터를 어떻게 정렬하면 좋을까? 가장 작은 데이터를 선택해 맨 앞에 있는 것과 바꾸고, 그다음 작은 데이터를 두번째 값과 바꾸는 과정을 반복하는 것은 어떨까? 원시적이긴 가장 떠올리기 쉬운 아이디어인것 같다. 이게 바로 선택 정렬이다.

6

9

0

1

5

4

3

8

7

2

<그림 1>

 

그렇다면 이제 선택정렬의 시간복잡도를 계산해보자. 선택 정렬은 총 N-1 번만큼 가장 작은 수를 찾아 앞을 보내야 한다. 이때 매번 가장 작은 수를 찾기 위한 연산이 필요하다. 하여 연산횟수는 N + N-1 + N-2 ... + 2 일것이다. 이에 등차수열의 합 공식을 적용해보면 근사치로 (N x N+1) / 2 로 표현 할 수 있다. 이를 빅오 표기법으로 나타내면 O(N^2)이다. 추후에 다른 정렬 알고리즘과의 비교를 위해 선택정렬의 시간복잡도는 O(N^2)이라고 기억해놓자. 

 

 

2. 삽입 정렬 (Insertion Sort)

특정 데이터를 특정 위치에 삽입한다는 의미에서 삽입정렬이라 불린다.

 

삽입 정렬은 특정한 데이터가 적절한 위치에 삽입되기 이전에, 그 앞까지의 데이터들은 이미 정렬이 되어있다고 가정한다. 이게 무슨말인가 예제로 한번 이해해보자.

다음과 같이 숫자 카드가 구성되어 있다. 

6

9

0

1

5

4

3

8

7

2

(Step 0)첫 번째 데이터는 이미 정렬되어 있다고 가정하기 때문에 삽입정렬은 두번째 데이터부터 시작한다.

(Step 1)첫 번째 카드 6은 이미 정렬되어 있다고 판단하고, 두번째 데이터인 9가 어떤 위치에 들어갈지 결정한다. 5의 오른쪽 왼쪽 두가지 경우만 존재한다. 우리는 카드를 오름차순으로 정렬할 것이기 때문에 6의 오른쪽에 삽입한다. 

(Step 2)이어서 0이 어떤 위치에 들어갈지 결정한다. 가능한 경우는 6의 왼쪽, 6과 9사이, 9의 오른쪽 3가지이다. 0은 6과 9보다 작기 때문에 가장 왼쪽에 들어간다.

...

이런 과정을 총 N-1번 반복하면 모든 데이터가 정렬된다. (두번째 부터 시작하므로 N-1번 반복)