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

숭실대학교 컴퓨터학부의 알고리즘 수업을 들으며 정리한 내용입니다.
참고교재: 쉽게 배우는 알고리즘(문병로)

다양한 정렬 알고리즘

정렬 알고리즘은 데이터를 특정한 순서로 나열하는 알고리즘을 말합니다. 여러 가지 종류의 정렬 알고리즘이 있으며, 각각의 알고리즘은 그 성능과 효율성에 차이가 있습니다.

 

기본적인 정렬 알고리즘 O(n^2)

1. 선택 정렬(Selection Sort): 주어진 리스트 중에서 최소값을 찾고, 그 값을 맨 앞에 위치한 값과 바꾸는 방법입니다. 이 과정을 반복하여 정렬을 완성합니다.
2. 버블 정렬(Bubble Sort): 인접한 두 개의 원소를 비교하여 자리를 바꾸는 과정을 반복하여 모든 원소를 순서에 맞게 만드는 방법입니다.
3. 삽입 정렬(Insertion Sort): 각 숫자를 적절한 위치에 삽입하는 방법으로 정렬을 완성합니다.

고급 정렬 알고리즘 O(n*logn)

1. 병합 정렬(Merge Sort): 데이터를 절반씩 나누어 정렬한 후, 다시 합치는 방법입니다. 분할 정복 알고리즘의 일종입니다.
2. 퀵 정렬(Quick Sort): 기준점(Pivot)을 정하여 기준점보다 작은 데이터는 왼쪽, 큰 데이터는 오른쪽으로 모으는 방법입니다. 분할 정복 알고리즘의 일종입니다.
3. 힙 정렬(Heap Sort): 힙 자료구조를 이용하여 정렬하는 방법입니다.

특수 정렬 알고리즘 O(n)

1. 계수 정렬(Counting Sort): 각 정수를 세어준 뒤, 그 개수만큼 각 정수를 차례로 출력하는 방법입니다. 데이터의 크기 범위가 제한된 경우에만 사용할 수 있습니다.
2. 기수 정렬(Radix Sort): 각 자릿수를 비교하여 정렬하는 방법입니다. 일반적으로 정수나 문자열에 적용됩니다.

 

알고리즘의 선택 조건

각 알고리즘은 그 특성에 따라 사용하면 좋습니다. 예를 들어, 데이터의 크기가 크고 범위가 제한적일 때는 '계수 정렬'이 효율적일 수 있습니다. 반면, 데이터의 크기가 크고 범위가 넓을 때는 '퀵 정렬'이나 '병합 정렬' 같은 O(n log n)의 정렬 알고리즘이 적합합니다.