정렬 알고리즘 특징/종류/시간 복잡도 [ 선택, 삽입, 버블, 합병, 힙, 퀵, 기수 ]

차근차근 인공지능, 인프준

 

 

 

 

알고리즘이 무엇인가?

 

알고리즘은 어떤 문제를 해결하기 위한 동작들의 절차입니다. 일상에서 보면 내가 목적지까지 가기 위한 과정을 말하기도 하고 프로그래밍에서는 입력받은 인풋을 통해서 우리가 원하는 아웃풋을 얻는 과정이라고 볼 수 있습니다. 우리에게 친근한 알고리즘은 나의 유튜브 영상이 관심 있는 사람의 키워드와 맞아 추천되거나 블로그 포스팅이 상위 노출되는 원리이기도 하죠. 인공지능은 특정한 문제를 해결하기 위해 고도화된 알고리즘으로 이루어져 있습니다. 알고리즘 종류는 정말 다양하지만 그중에서 오늘은 정렬 알고리즘 종류 몇 가지를 간단하게 소개해보겠습니다.

 

 

우리가 흔히 쓰는 알고리즘은 사실 리듬(rhythm)과 같이 알고리듬(algorithm)으로 읽는 게 맞다는 논쟁이 있다.

 

---

 

 

정렬 알고리즘의 종류와 복잡도

 

정렬 알고리즘은 여러 방식의 정렬을 하는 알고리즘이 있습니다. 주어진 문제를 해결하기 위한 최선의 알고리즘을 선택해야 하는데 그때 고려해야 할 사항이 시간 복잡도와 공간 복잡도입니다. 시간 복잡도는 이 알고리즘이 결과를 도출하는 데 걸리는 시간의 값이며 공간 복잡도는 이 알고리즘이 결과를 도출하는데 필요한 공간의 값입니다. 즉 문제를 해결하기 위해 선택해야 할 최선의 알고리즘은 적은 시간과 적은 공간을 사용하는 알고리즘입니다.

 

 

문제 해결에 가장 효율적인 알고리즘은 가장 빠르고 가장 적은 공간을 사용하는 알고리즘

 

시간 복잡도 성능 비교

 

 

 

하나하나 포스팅하면서 코드도 구현해보면 좋을 것 같지만 오늘은 우선 간단하게 알아보려 합니다. 선택 정렬, 삽입 정렬, 버블 정렬, 합병 정렬, 힙 정렬, 퀵 정렬, 기수 정렬 각각의 특징과 시간 복잡도를 알아보고 비교해보겠습니다. 

 

 

---

 

 

1. Selection Sort, 선택 정렬

 

선택 정렬은 데이터 중 가장 작은 값의 데이터를 선택하여 앞으로 보내는 정렬입니다.

 

 

= 10 + 9 + 8 + 7 +...+ 2 + 1 = 10 * (10 + 1) / 2 = 55

= N * ( N + 1 ) / 2

= N * N

= O( N * N )

 

선택 정렬의 시간 복잡도는 O(N²)이며 Worst, Average, Best 모두 동일합니다.

 

 

 

2. Insertion Sort, 삽입 정렬

 

삽입 정렬은 데이터를 순서대로 뽑아서 적절한 위치를 찾아 삽입함으로써 완성하는 정렬입니다.

 

 

삽입 정렬의 시간 복잡도는 O(N²)이며 Worst, Average는 동일하고 이미 정렬되어 있는 Best의 경우 O(N)입니다. 무조건 위치를 변경하는 선택 정렬과 시간 복잡도가 같지만 필요할 때에 삽입한다는 점에서 연산수가 적어지므로 효율적입니다. 이미 정렬되어 있는 데이터가 많다면 빠른 알고리즘입니다.

 

 

 

3. Bubble Sort, 버블 정렬

 

버블 정렬은 버블이 수면 위를 올라오는 듯 옆에 있는 데이터와 비교하여 더 작은 값을 앞으로 보내는 정렬입니다.

 

 

버블 정렬의 시간 복잡도는 O(N²)이며 Worst, Average, Best 모두 동일합니다. 앞서 소개한 선택 정렬, 삽입 정렬과 시간 복잡도가 같지만 연산 수가 많아 정렬 알고리즘 중에서 가장 느리고 효율성이 떨어지는 정렬 방식입니다.

 

 

 

4. Merge Sort, 합병 정렬(또는 병합 정렬)

 

합병 정렬은 비교 기반 알고리즘으로 '분할, 정렬, 결합'순으로 진행되는데 데이터 배열을 2개 이상의 부분 배열로 분할하고 부분 배열에서 정렬을 한 뒤 결합하여 다시 정렬을 진행합니다. 데이터 배열 전체가 다시 결합되고 정렬되면서 마칩니다.

 

 

합병 정렬의 시간 복잡도는 O(N ㏒ N)이며 Worst, Average, Best 모두 동일합니다. 데이터를 정확히 반으로 나누고 정렬하기 때문에 항상 일정한 시간 복잡도를 유지하므로 퀵 정렬의 한계점을 보완할 수 있는 장점이 있지만 다른 알고리즘과 비교했을 때 O(n) 수준의 메모리가 추가로 필요하다는 단점이 있습니다.

 

 

 

5. Heap Sort, 힙 정렬 

 

힙 정렬은 이진트리 기반의 트리형 자료구조로써 최솟값이나 최댓값을 찾아내기 위해서 사용합니다. 내림차순 정렬을 위해서는 최대 힙, 오름차순 정렬을 위해서는 최소 힙을 구성하면 됩니다.

 

 

힙 정렬의 시간 복잡도는 O(N ㏒ N)이며 Worst, Average, Best 모두 동일합니다. 완전 이진트리를 사용합니다.

 

 

 

6. Quick Sort, 퀵 정렬

 

퀵 정렬은 데이터 중 임의의 기준값을 정해서 두 부분 집합으로 나눕니다. 이때의 기준 값을 피벗(Pivot)이라고 하고 왼쪽은 피벗보다 작은 값, 오른쪽은 피벗보다 큰 값을 배치하고 더 이상 집합을 나눌 수 없을 때까지 재귀적으로 실행됩니다.

 

 

퀵 정렬의 시간 복잡도는 O(N ㏒ N)이며 Average, Best는 동일하고 Worst의 경우 O(N²)입니다. 삽입 정렬과 반대로 퀵 정렬은 이미 정렬된 데이터라면 매우 비효율적으로 작용합니다.

 

따라서 퀵 정렬은 이름처럼 가장 빠른 알고리즘 중 하나지만 이미 정렬된 데이터의 경우 퀵 정렬보다 삽입 정렬을 사용하는 것이 더 빠르고 효율적입니다. 이처럼 상황에 따라 효율적인 알고리즘은 다릅니다.

 

 

 

7. Radix Sort, 기수 정렬

 

기수 정렬은 낮은 자릿수부터 비교하여 완성하는 정렬입니다. 기수 정렬은 비교 연산을 하지 않으며 정렬 속도가 빠른 편이지만 데이터 전체 크기에 기수 테이블의 크기만 한 메모리가 더 필요한 단점이 있습니다.

 

 

기수 정렬의 시간 복잡도는 O(dN)이며 d는 자릿수입니다.

 

 

 

 

 

---

 

 

 

내용 참고

한양대학교 인공지능융합대학원 컴퓨터 알고리즘 강의자료, yjglab님 블로그, 에드윈 H님 블로그