[자료구조] Sorting Concept(Internal Sort concept/External Sort concept) (Ch07. Sorting)

Sorting은 데이터를 특정 순서대로 정렬하는 과정을 의미하며, 자료구조에서 중요한 개념 중 하나이다. Sorting 알고리즘은 크게 내부 정렬(Internal Sorting)과 외부 정렬(External Sorting)로 나눌 수 있다.

내부 정렬 (Internal Sorting)

내부 정렬은 모든 데이터를 주 메모리(RAM)에 적재할 수 있는 경우에 사용하는 정렬 방법이다. 주로 사용하는 내부 정렬 알고리즘은 다음과 같다.

버블 정렬 (Bubble Sort)

버블 정렬은 인접한 두 요소를 비교하여 필요에 따라 위치를 바꾸는 과정을 반복하여 정렬하는 알고리즘이다. 가장 큰 요소가 맨 뒤로 "버블"처럼 이동하는 것에서 이름이 유래되었다.

• 특징: 단순하지만 비효율적이다.
• 시간 복잡도: O(n^2)

삽입 정렬 (Insertion Sort)

삽입 정렬은 정렬된 부분과 정렬되지 않은 부분으로 나누어, 정렬되지 않은 요소를 하나씩 정렬된 부분에 삽입하여 정렬하는 알고리즘이다.

• 특징: 데이터 양이 적거나 거의 정렬된 상태에서는 효율적이다.
• 시간 복잡도: O(n^2)

선택 정렬 (Selection Sort)

선택 정렬은 매번 가장 작은 요소를 선택하여 정렬되지 않은 부분의 맨 앞으로 이동시키는 방식으로 정렬하는 알고리즘이다.

• 특징: 단순하지만 비효율적이다.
• 시간 복잡도: O(n^2)

퀵 정렬 (Quick Sort)

퀵 정렬은 기준(pivot)을 설정하고 기준보다 작은 요소는 왼쪽, 큰 요소는 오른쪽으로 분할하는 과정을 재귀적으로 반복하여 정렬하는 알고리즘이다.

• 특징: 평균적으로 매우 빠르다.
• 시간 복잡도: 평균 O(nlogn), 최악 O(n^2)

병합 정렬 (Merge Sort)

병합 정렬은 배열을 절반으로 나누어 각각을 재귀적으로 정렬하고, 두 정렬된 배열을 병합하여 최종 정렬을 완료하는 알고리즘이다.

• 특징: 안정적이고 성능이 좋다.
• 시간 복잡도: O(nlogn)

외부 정렬 (External Sorting)

외부 정렬은 데이터가 너무 커서 주 메모리에 모두 적재할 수 없는 경우에 사용하는 정렬 방법이다. 보조 기억 장치(예: 디스크)를 사용하여 데이터를 정렬한다.