[데이터베이스] 정렬

1. 정렬(Sort)
 - 데이터 집합을 정해진 순서로 재배열
 - 정렬의 기본은 비교,교환
 - 정렬 방법에 따라 여러 알고리즘이 존재
 - 복잡성에 따라 단순정렬 (선택,삽입,버블), 고급정렬 (퀵,기수,힙,병합)
 - 장소에 따라 내부정렬,외부정렬
 - 교환방식에 따라 직접정렬, 간접정렬

2. 선택정렬(Selection Sort) 

 - 압부분 부터 정렬 되어 나감

 - 자료(N) : ↑ , 시간(T) : →

 - 비교 : N(N-1)/2, 교환 : N-1

 - worst case

   (2,3,4,5,1) -> (2,3,4,1,5) -> (2,3,1,4,5) -> (2,1,3,4,5) -> (1,2,3,4,5)

 - 단순하지만 입력자료에 둔감

3. 삽입정렬 (Insertion Sort)

 - 현재레코드를 일부 정렬된 부분의 적절한 위치로 옮김

 - 적절한 위치 검색 속도가 중요

 - Binary Search (이분법) 이용한 개선 가능

 - 정렬부분 관 미정렬 부분으로 구분 하여 미정렬 부분의 앞의값을 정렬부분의 뒤의값부터 앞으로 비교해 나감

- 자료(N) : ↑ , 시간(T) : →

-상대적으로 앞부분부터 정렬이 되어감

- 비교 : N(N-1)/2  * (1~(N-1)) , 교환 N(N-1)/2

- worst case  : Reverse

(5,4,3,2,1)-> (4,5,3,2,1) -> (3,4,5,2,1) -> (2,3,4,5,1) -> (1,2,3,4,5)

- 입력자료에 민감

- 난수배열에서는 삽입정렬이 약간 우수 하나 순차배열에서는 월등함, 일반적으로 삽입정렬이 성능이 좋음.


4.버블정렬

- 인접한 두개의 원소를 비교하여 자리를 교환

- 첫번째 원소부터 마지막 원소까지 반복해서 비교하여 가장 큰 원소가 가장 마지막으로 가는것이 한 단계

- 첫단계 이후 가장 큰 원소가 가장 큰 원소의 앞자리로 이동

- 메모리 사용공간 : N 개의 원소에 대하여 N 개의 메모리 사용

- best : 이미 정렬 되어 있음,  비교 : n(n-1)/2 , 교환 : 0

- worst : 자료가 역순으로 정렬 , 비교 : n(n-1)/2 , 교환 : n(n-1)/2