정렬 (1) - 개요

1. 정렬의 정의 :

• 데이터를 정해진 순서로 재배열하는 것 (오름차순, 내림차순) 
• 정렬은 비교와 교환의 미학
• 수많은 정렬 알고리즘이 존재함.

 

2. 키와 레코드

• 키 : 정렬의 기준 (비교의 대상)
• 레코드 : 하나의 정보단위 (교환의 대상)
• 직원정보를 사번으로 정렬 → (키 : 사번, 레코드 : 직원정보 전체)

 

3. 정렬알고리즘의 선택

• 단순정렬 : 선택, 삽입, 버블, 쉘 (성능 낮음, $O(n^2)$, 쉬움)
• 복잡정렬 : 퀵, 기수, 힙, 병합 (성능 높음, $O(n * Log(n)$, 어려움)

 

2) 위치에 따라

• 내부정렬 : 컴퓨터 메모리 내부에서 정렬하는 것
• 외부정렬 : 테이프, 하드디스크에서 정렬하는 것 

 

3) 교환 방식에 따라

• 직접정렬 : 레코드 전체를 이동하여 정렬
• 간접정렬 : 별도 존재하는 키값의 인덱스만 정렬하는 것

 

4) 안정성(Stability)에 따라

• A C K D A O 를 정렬할때 A가 두번 나오는데, A1과 A2가 정렬 후에도 그 상대적 순서를 유지하면 안정성이 있다고 하고 유지하지 못하면 안정성이 없다고 함.