기본적인 정렬 방법들(선택, 삽입, 버블)에 대해 알아보자

기본적인 정렬 방법들 (선택, 삽입, 버블)

이 게시글은 정렬의 코드보단 정렬의 방법과 특징에 비중을 두고 있습니다.

응용된 정렬 방법들 (셸, 병합, 퀵) 보러가기

정렬의 종류와 시간복잡도

정렬은 버블 정렬, 선택 정렬, 삽입 정렬, 셸 정렬, 병합 정렬, 퀵 정렬로 이루어져있으며,

각각의 특징이 있으므로 상황을 고려해서 쓰는 게 좋다.

기본적인 정렬 알고리즘(1) - 선택 정렬(Selection Sort)

선택 정렬의 과정

선택 정렬은 앞에서부터 가장 작은 수를 찾아 key의 값과 교체하는 정렬 방법이다.

key(7)부터 끝까지의 수들 중, 가장 작은 수(1)를 찾아서 key의 값과 바꾼다.

key(11)부터 끝까지의 수들 중, 가장 작은 수(3)를 찾아서 key의 값과 바꾼다.

key(15)부터 끝까지의 수들 중, 가장 작은 수(7)를 찾아서 key의 값과 바꾼다.

key(11)부터 끝까지의 수들 중, 가장 작은 수(11)를 찾아서 key의 값과 바꾼다.

아래는 조금 더 이해를 도울 선택 정렬의 전 과정을 담은 GIF이다.

선택 정렬의 시간복잡도

• O(N²)

선택 정렬의 특징

장점

• 반복 횟수가 같기 때문에 자료의 정렬 정도에 구애받지 않는다.
• 정렬방법과 구현이 쉽고 간단하다

단점

• 속도가 느리고 비효율적이다.

기본적인 정렬 알고리즘(2) - 삽입 정렬(Insertion Sort)

삽입 정렬의 과정

삽입 정렬은 두 번째부터 비교를 시작하며, 앞의 값들과 비교하여 자신의 자리를 찾는 정렬 방법이다.

두 번째(7)부터 비교를 시작한다.

두 번째 값(7)의 앞에 있는 값들과(9) 비교를 한다.

9 > 7 이므로 9는 한 칸 뒤로(2번째), 7은 한 칸 앞(1번째)로 간다.

세 번째 값(5)의 앞에 있는 값들(7, 9)과 비교를 한다.

1. 2번째(9)와 3번째(5)

   • 9 > 5이므로 9는 한 칸 뒤로(3번째), 5는 한 칸 앞(2번째)로 간다.
   1. 2번째(5)와 1번째(7)

• 5 < 7이므로 7은 한 칸 뒤로(2번째), 5는 한 칸 앞으로(1번째)로 간다.

네 번째 값(3) 앞에 있는 값들(5,7,9)와 비교를 한다.

1. 3번째(9)와 4번째(3)

   • 9 > 3이므로 9는 한 칸 뒤로(4번째), 3는 한 칸 앞(3번째)로 간다.
   1. 3번째(3)와 2번째(7)

• 7 > 3이므로 7은 한 칸 뒤로(3번째), 3는 한 칸 앞(2번째)로 간다.

1. 2번째(3)와 1번째(5)

• 3 < 5이므로 5는 한 칸 뒤로(2번째), 3는 한 칸 앞(1번째)로 간다.

아래는 조금 더 이해를 도울 삽입 정렬의 전 과정을 담은 GIF이다.

삽입 정렬의 시간복잡도

• O(N²)

삽입 정렬의 특징

장점

• 안정적이다.
• 값의 개수가 적거나 정렬된 상태가 고를 때 효율적이다.
• 기본적인 정렬 방법들 중에는 가장 효율적이다.

단점

• 값의 개수가 많으면 반복 횟수가 많아진다.

기본적인 정렬 알고리즘(3) - 버블 정렬(Bubble Sort)

버블 정렬의 과정

오른쪽에 있는 값과 비교를 하여 왼쪽이 더 크면 교환을 하는 방법이다.

1. 1번째(9)과 2번째(7)를 비교한다.
   • 9 > 7 이므로 교환한다.
2. 2번째(9)와 3번째(5)를 비교한다.
   • 9 > 5 이므로 교환한다.
3. 3번째(9)와 4번째(3)을 비교한다.
   • 9 > 3 이므로 교환한다.

1. 1번째(7)와 2번째(5)를 비교한다.
   • 7 > 5 이므로 교환한다.
2. 2번째(7)와 3번째(3)을 비교한다.
   • 7 > 3 이므로 교환한다.

1. 1번째(5)와 2번째(3)을 비교한다.
   • 5 > 3 이므로 교환한다.

아래는 조금 더 이해를 도울 버블 정렬의 전 과정을 담은 GIF이다.

버블 정렬의 시간복잡도

• O(N²)

버블 정렬의 특징

장점

• 간단하고 구현이 쉽다.
• 정밀한 비교가 가능하다.

단점

• 비교 횟수가 많아지면 시간이 늘어난다.
• 비효율적이다.

정리

위에 소개한 세가지 정렬방법 모두 간단하고 기본적인 정렬방법이지만, 성능면으로 좋지 않다.

셋 다 시간복잡도가 O(N²) 이다.

참고 문헌

정렬별 장단점 및 특징