[알고리즘] 정렬(1)

정렬

내부 정렬

모든 데이터를 주기억장치에 저장하고 정렬

 

<내부 정렬의 방식>

비교 기반 정렬 

- 두 데이터를 직접 비교하여 정렬, 키 값의 비교 횟수로 알고리즘 성능 나타냄

ex. 선택 정렬, 버블 정렬, 삽입 정렬, 셀 정렬, 합병 정렬, 퀵 정렬, 힙 정렬

vs

데이터 분포 기반 정렬

- 데이터의 분포 정보를 활용해 정렬,   데이터 이동 횟수로 알고리즘  성능 나타냄

ex. 계수 정렬, 기수 정렬, 버킷 정렬

 

안정적 정렬

동일한 값을 가진 데이터들이 정렬을 하고 나서도 상대적인 위치가 같게 유지되는 정렬

 

제자리 정렬

입력 배열의 데이터 개수와 관계없이 일정한 상수개 외에 별도로 저장 공간이 필요하지 않은 정렬

 

<알고리즘 성능 (시간 복잡도) 가 O(n^2)인 기본 정렬>

 

선택 정렬 (Selection Sort)

- 가장 작은 값부터 순서대로 선택해서 정렬 -> 정렬 안 된 부분에서 최솟값 찾고 위치 이동

- O(n^2), 불안정적, 제자리

 

버블 정렬 (Bubble Sort)

- 왼쪽 또는 오른쪽 등 한 쪽에서 인접한 두 값을 차례로 비교해 더 큰 왼쪽 데이터는 오른쪽 데이터와 바꾸는 과정을 반복하여 정렬

- O(n^2), 안정적, 제자리

 

삽입 정렬 (Insertion Sort)

- 데이터를 뽑아 이미 나열된 데이터가 정렬을 항상 유지하도록 바른 위에 삽입하여 정렬 

- O(n^2), 안정적, 제자리

 

셀 정렬 (Shell Sort)

- 삽입 정렬 단점을 보완, 처음엔 멀리 떨어진 두 데이터를 비교/교환하고 점차 가까이 있는 원소를 비교/교환하는 정렬,

- 개념) 입력 배열을 부분배열로 나눠 삽입정렬을 수행하는데 계속 부분배열 크기와 개수를 줄여가며 반복

- O(n^2), 불안정적, 제자리