[알고리즘] 정렬 알고리즘 정리

03. 정렬 알고리즘

---

정렬 알고리즘(Sorting algorithm)이란,

원소들을 번호순이나 사전 순서와 같이 일정한 순서대로 열거하는 알고리즘입니다.

수들을 정렬할 때는 크게 오름차순, 내림차순으로 정렬을 진행합니다.

오름차순(ASC): 어센딩 정렬 ex) 1,2,3,4,5,..
내림차순(DESC): 디센딩 정렬 ex) 10,9,8,7,6....

 

정렬 알고리즘의 종류

---

ASC 또는 DESC로 수들을 정렬하기 위해서 다양한 방법들이 있습니다. 

1. 버블 정렬
2. 삽입 정렬
3. 선택 정렬
4. 퀵 정렬
5. 병합 정렬
6. 힙 정렬

---

1) 버블 정렬(Bubble Sort)

• 두 개씩 비교하며, 정렬하는 방식
• 수행 시간 O(N^2)

버블 정렬 예시

버블 정렬은 위 사진과 같이 숫자를 두 개씩 비교하며 정렬하는 방식입니다.

처음부터 끝까지 비교를 하면, 제일 큰 수가 맨 뒤에 위치하게 됩니다.

위 사진에서는 80이 제일 뒤로 가게 됩니다. ex) 50, 70, 10, 60, 20, 40, 30, 80

이같은 결과가 되면 다음으로 80을 제외해서 또 한번 두 개씩 비교를 시작합니다.

ex) 50, 10, 60, 20, 40, 30, 70, 80

이렇게 반복해서 최종적으로는 10, 20, ,30, 40, 50, 60, 70, 80과 같이 오름차순으로 정렬이 됩니다.

 

---

2) 삽입 정렬(Insertion Sort)

• 이미 정렬된 상태에서 새로운 요소를 추가하여 비교 후 재정렬하는 방식
• 수행 시간 O(N^2)

삽입 정렬 예시

삽입정렬은 두 번째 요소부터 이전 요소들과 비교하며 insert 될 위치를 찾는 방식입니다.

위 사진에서 봤을 때 예로 50, 80, 70, 10, 60, 20, 40, 30 라는 정렬되어 있지 않은 수들이 있습니다.

가장 먼저 수가 하나 있을 때는 비교를 할 필요가 없으니 두 번째 수부터 비교를 시작합니다.

따라서 50과 80을 비교해서 정렬을 합니다.

예시에서는 어센딩 방식으로 정렬을 하니 50이 먼저 오고 다음 80이 오면서 정렬이 되었습니다.

다음은 정렬된 50, 80과 70을 비교해줍니다.

먼저 80과 70을 비교해줍니다. 70 또한 80보다 작으니 80에 앞에 위치하게 됩니다.

다음은 50과 70을 비교합니다. 결과는 50이 더 작으므로 50, 70, 80으로 정렬이 됩니다.

마지막으로 10까지 정렬되는 과정을 알아보겠습니다.

방법은 위와 동일합니다. 먼저 80과 비교합니다. 10이 더 작은 수이므로 80에 앞으로 이동합니다. 

이런식으로 반복해서 최종적으로는 10, 20, 30, 40, 50, 60, 70, 80 으로 어센딩 정렬이 됩니다.

 

---

3) 선택 정렬(Selection Sort)

• 처음부터 끝까지 스캔하고, 최솟값 또는 최댓값을 앞으로 가져오는 방식(교체하는 것)
• 다음으로 정렬된 첫 수를 제외하고, 나머지 수들을 스캔
• 수행 시간 O(N^2)

선택 정렬 예시

---

 

지금까지 정렬의 종류 중 3가지(버블 정렬, 삽입 정렬, 선택 정렬)에 대해서 알아보았습니다.

이 3가지 방식의 공통점은 n개의 수를 n번 반복해서 O(N^2)의 수행속도를 갖는 것입니다.

다음 게시물에서는 정렬에서 O(logN)의 수행속도를 갖는 정렬에 대해서 알아보도록 하겠습니다.