정렬 알고리즘

알고리즘이란?

 

컴퓨터가 어떠한 문제를 해결하거나 작업을 수행하기 위해 거치는 일련의 단계적 절차나 방법을 뜻한다.

정렬 알고리즘이란?

 

무작위로 나열된 데이터를 특정한 기준(오름차순 또는 내림차순)에 따라 순서대로 재배열하는 알고리즘을 뜻한다. 데이터를 효율적으로 탐색하고 관리하기 위한 기초적이고 핵심적인 컴퓨터 기법이라 할 수 있다.

정렬 알고리즘이 필요한 이유는?

• 탐색 효율 극대화 : 데이터가 정렬되어 있어야 이진 탐색(Binary Search)과 같은 빠르고 효율적인 탐색 알고리즘을 사용할 수 있다.
• 데이터 관리 : 대량의 데이터를 이름순, 가격순, 시간순 등으로 정렬하려 가시성과 활용도를 높인다.

정렬 알고리즘의 종류와 특징

1. 비교 정렬 알고리즘

버블 정렬(Bubble Sort)

인접한 두 원소를 비교하여 크기가 순서대로 되어있지 않으면 자리를 교환하는 방식.

버블 정렬

특징

• 최선, 평균, 최악의 시간복잡도는 모두 O(n^2)
• 직관적이나 거의 사용하지 않는 정렬 알고리즘이다.

장점

• 인접한 값만 계속해서 비교하는 방식으로 구현이 쉬우며, 코드가 직관적이다.
• n개의 원소에 대해 n개의 메모리를 사용하기에 데이터를 하나씩 정밀 비교가 가능하다.
• 배열 내에서 교환하는 방식(제자리 정렬)으로 추가적인 메모리 공간을 필요로 하지 않는다.

단점

• 최선이든 최악이든 O(n^2)의 시간 복잡도를 가진다.
• n개의 원소에 대해 n개의 메모리는 사용하기에 원소의 개수가 많아지면 비교 횟수가 많아져 성능이 저하된다.
• 하나의 요소가 끝으로 이동하기 위해 배열의 모든 요소와 교환이 이뤄져야 한다.

---

선택 정렬(Selection Sort)

정렬되지 않은 데이터 중 가장 작은(또는 가장 큰) 데이터를 선택해 맨 앞으로 보내는 방식.

특징

• 최선, 평균, 최악의 시간 복잡도는 모두 O(n^2)
• 비교 횟수는 많지만, 실제 교환되는 횟수는 적다. 따라서 똑같은 O(n^2)의 시간 복잡도를 가진 버블 정렬보다 적은 시간이 소요된다.

장점

• 알고리즘이 단순하고, 구현이 쉽다.
• 정렬된 배열을 반대로 재정렬할 때 효율이 좋다.
• 배열 내에서 교환하는 방식(제자리 정렬)으로 추가적인 메모리 공간을 필요로 하지 않는다.

단점

• 배열의 길이가 길어질수록 지수적으로 시간이 증가하기 때문에 비효율적이다.
• 중복된 값이 있을 경우, 기존 요소의 순서가 바뀔 수 있는 불안정성을 지닌다.

---

삽입 정렬(Insertion Sort)

선택한 요소를 이미 정렬된 요소들과 비교해 알맞은 위치에 삽입한다. 선택한 요소의 앞쪽 요소들은 이미 정렬된 상태를 유지하고 있으므로, 매 순서마다 바로 이전 인덱스 요소와 비교하여 원소가 삽입될 올바른 위치를 찾아낸다.

특징

• 최선의 시간복잡도는 O(n)이며, 평균 및 최악의 시간 복잡도는 O(n^2)
• O(n^2)의 시간 복잡도를 갖는 선택 정렬과 버블 정렬에 비해 상대적으로 속도가 빠르다.

장점

• 알고리즘이 단순하고, 구현이 쉽다.
• 이미 정렬된 배열일 경우, 매번 1번의 비교로 정렬되기 때문에 O(n)의 시간 복잡도를 가지며 매우 효율적이다.
• 배열 내에서 교환하는 방식(제자리 정렬)으로 추가적인 메모리 공간을 필요로 하지 않는다.

단점

• 다른 정렬 알고리즘에 비해 비교적 많은 교환이 발생한다.
• 배열의 길이가 길어질수록 지수적으로 시간이 증가하기 때문에 비효율적이다.

---

퀵 정렬(Quick Sort)

기준값(Pivot)을 정해 그보다 작은 그룹과 큰 그룹으로 나누어 정렬을 반복하는 방식. 피벗을 기준으로 왼쪽은 피벗보다 작은 값, 오른쪽은 피벗보다 큰 값을 가질 수 있도록 값을 이동시킨다. 분할과 동시에 정렬이 이뤄지며, 분할된 배열의 크기가 1이 되면 정렬이 완료된다.

특징

• 최선 및 평균 시간 복잡도는 O(nlogn)이며, 최악의 시간복잡도는 O(n^2)
• O(nlogn)의 시간 복잡도를 가지는 병합 정렬보다 상대적으로 속도가 빠르다.

장점

• 배열 내에서 교환하는 방식(제자리 정렬)으로 추가적인 메모리 공간을 필요로 하지 않는다
• 다른 알고리즘과 비교했을 때 가장 빠르다.

단점

• 정렬된 배열에 대해서는 불균형 분할로 인해 더 오랜 시간이 소요된다.

---

병합 정렬(Merge Sort)

하나의 배열을 두 개의 균등한 배열로 분할해 정렬하고, 두 배열을 다시 합하여 정렬한다. 큰 문제를 작은 단위의 문제들로 쪼개어 해결해가는 방식인 분할 정복을 이용한 정렬 알고리즘이다.

특징

• 배열을 이용할 경우 추가적인 메모리가 필요하지만, 연결리스트를 이용할 경우에는 필요하지 않다.
• 최선, 평균, 최악의 시간 복잡도는 모두 O(nlogn)이다.

장점

• 연결리스트를 이용할 경우, 링크 인덱스만 변경하면 되므로 이동 연산이 줄어든다.(추가적인 메모리 필요없음)
• 퀵 정렬과 비교했을 때 데이터 분포에 영향을 받지 않는다.

단점

• 배열을 이용할 경우, 추가적인 메모리(임시 배열)이 필요하다.
• 이동 연산이 많아, 레코드 개수가 클 경우에는 비효율적이다.

---

2. 비비교 정렬 알고리즘

계수 정렬(Counting Sort)

데이터의 값 자체를 인덱스로 삼아 개수를 세는 방식.

장점

• 시간 복잡도가 O(n)으로 어떤 정렬 알고리즘보다 빠르고 간단하게 정렬한다.

단점

• 입력되는 배열이 0 부터 k 사이의 정수라는 가정하에 정렬을 시작한다. 이를 위해 배열에서 가장 큰 값이 무엇인지 알아야만 한다. 그렇지 않다면 계수 정렬을 사용할 수 없다.