알고리즘: 정렬 - 삽입 정렬, 버블 정렬, 병합 정렬, 선택 정렬, 퀵 정렬, 힙 정렬, 카운팅(계수) 정렬

안정 정렬

Stable sort, 정렬 전의 순서를 유지하고 정렬된다

삽입(Insertion) 정렬, 버블(Bubble) 정렬, 병합(Merge) 정렬이 있다

 

삽입 정렬

두번째 자료부터 시작해 자신보다 앞 자료들과 크기를 비교해 알맞은 자리에 끼워넣는다

 

버블 정렬

서로 인접한 자료들을 계속해서 정렬해준다. 1번 회전이 될 때 가장 큰 수가 맨 오른쪽에 위치한다

 

병합 정렬

현재 배열을 두 개로 나눈 뒤 각각 정렬을 수행한다. 정렬된 두 배열의 처음 값들을 비교해 작은 값을 먼저 원래 배열에 넣어준다

병합 정렬의 원리

 

위의 예시는 원리를 설명하기 위한 병합정렬의 맨 마지막 과정이다. 자세히 보면 크기가 4인 배열들이 이미 정렬되어 있다. 크기가 4인 배열을 정렬하기 위해 크기가 2인 배열로 나누고 다시 크기가 1인 배열로 나누어 위의 원리에 따라 계속 병합해야 한다.

 

 

 

불안정 정렬

Unstable sort, 정렬 전의 순서를 유지하지 않고 정렬된다

선택(Selection) 정렬, 퀵(Quick) 정렬, 힙(Heap) 정렬, 인트로(Intro) 정렬이 있다

 

선택 정렬

배열 안에서 최소값을 찾고 앞에 위치한 값과 자리를 교체(pass)한다. 교체한 곳은 제외한 채 앞 내용을 반복한다

 

퀵 정렬

찰스 앤터니 리처드 호어(Charles Antony Richard Hoare)가 개발했다. 배열 안에서 숫자를 선택, 피벗(Pivot)을 정한다.

피벗(Pivot)보다 작은 숫자들은 모두 피벗 왼쪽에 배치하고 피벗(Pivot)보다 큰 숫자들은 모두 피벗 오른쪽에 배치한다

피벗을 제외한 후 다시 위의 과정을 반복한다.

 

퀵 정렬의 코드화

5 3 8 4 9 1 6 2 7 을 예로 들면, 먼저 5를 피벗으로 정한다

< 1 >

오른쪽에서 탐색: 5보다 작은 값이 있는지 찾는다 2

왼쪽에서 탐색: 5보다 큰 값이 있는지 찾는다 8

 

5 → 3 8 4 9 1 6 2 7 ←

찾은 다음 둘의 위치를 바꾼다

5  3 2 4 9 1 6 8 7

 

< 2 >

 

오른쪽에서 탐색: 5보다 작은 값이 있는지 찾는다 1

왼쪽에서 탐색: 5보다 큰 값이 있는지 찾는다 9

5 →3 2 4 9 1 6 8 7 ←

찾은 다음 둘의 위치를 바꾼다

5 →3 2 4 1 9 6 8 7 ←

 

< 3 >

오른쪽에서 5보다 작은 값, 왼쪽에서 5보다 큰 값을 찾는다.

하지만 탐색위치가 서로 겹치게 되므로 마무리를 위해 피벗을 이동해준다.

오른쪽에서 5보다 작은 값 1과 5의 위치를 바꾼다

1 3 2 4 5 9 6 8 7

피벗 5를 기준으로 정렬되었다. 이후 5를 제외한 나머지 배열을 위와 같은 방식으로 분할(devide), 정복(conquer) 해준다.

[ 1 3 2 4 ] 5 [ 9 6 8 7 ]

 

힙 정렬

힙 정렬은 이진 트리의 일종으로 최대, 최소값을 쉽게 추출할 수 있다.

현재의 값을 노드 최하단에 넣은 후 부모노드와 값을 비교해 위치를 바꿔준다

 

최상단 값을 삭제할 때는 값을 삭제한 후 마지막 노드의 값을 넣어준다

 

카운팅(계수) 정렬

시간 복잡도가 O(n)으로 효율이 매우 좋다. 나오는 숫자들을 모두 몇 번 나왔는지 각각 세어주고 누적합을 만들어 위치를 배정한다

 

다음 배열이 주어진다면 카운팅 정렬은 어떻게 수행될까?

먼저 최대값을 탐색한다. 최대값은 5이므로 0을 고려해 크기가 6인 배열을 만든다

index의 번호가 곧 그 숫자를 뜻한다. 숫자를 각각 몇 개인지 세어준 뒤 값을 배열 안에 넣어준다

0은 0개, 1은 1개, 2는 2개, 3은 1개, 4는 1개. 5는 1개 존재한다

이를 누적합으로 바꿔준다. 현재 숫자가 정확히 몇번째 숫자인지 알려줘야 하기 때문이다.

카운팅 배열

 

다시 원래 배열로 돌아가서 카운팅배열에 따라 배치해준다. 

원래 배열

왼쪽부터 탐색했을 때, 3 → 1 → 2 → 2 → 4 → 5 순서대로 배치한다.

3 → 카운팅배열에서 index[3]의 값을 찾는다(= 4). 3의 위치는 4번째이지만 배열은 0부터 시작하므로 index[3]에 위치한다.

       카운팅 배열의 index[3]을 사용했으므로 1을 차감한다

1 → 카운팅배열에서 index[1]의 값을 찾는다(= 1). 1의 위치는 1번째이지만 배열은 0부터 시작하므로 index[0]에 위치한다.

       카운팅 배열의 index[1]을 사용했으므로 1을 차감한다

...위 과정을 계속 반복한다

 

자료출처: Heee's Development Blog의 이미지를 참고했습니다