레코드 : 데이터 모임
안정적 : 정렬 후에도 값이 같은 요소의 상대적 위치가 변하지 않을 때
제자리 정렬 알고리즘 : 추가 기억장소의 수가 상수 개를 넘지 않는 알고리즘
더미 키 : 배열의 한계를 벗어나지 않도록 모든 원소보다 작은 값 a[0]에 저장
선택 정렬
: 배열에서 제일 작은 거 찾아서 첫번째랑 교환 두 번째부터 제일 작은 거 찾아서 두 번째랑 교환 반복
(제자리, 불안정, O(N^2))
(실교환은 for문당 한번이므로 작은 키와 큰 레코드에 유리)
(어짜피 요소를 전부 확인 하므로 자료 순서에 민감X)
버블 정렬 : 앞에서부터 인접한 두 원소 오름차순에 맞게 정렬하면서 뒤부터 차곡차곡 정렬됨
(제자리, 안정적, O(N^2))
(계속 교환하므로 레코드의 크기가 큰 경우 불리)
(정렬되어 있을 경우 교환이 이루어지지 않으므로 유리)
삽입 정렬
: S(정렬된 원소), U(정렬할 원소)
최초 S에는 a[1]만 있음
U의 제일 왼쪽 원소를 하나씩 S에 맞는 위치에 삽입을 반복
v에 a[i]넣고 S제일 오른쪽부터 v보다 큰거 오른쪽으로 한칸씩
a[0]에 요소보다 작은 더미 키 필요
(제자리, 안정적, O(N^2))(버블과 유사)
(계속 이동 시키므로 레코드 클수록 불리)
(정렬되어 있을 경우 교환이 이루어지지 않으므로 유리)
쉘 정렬
: k개의 서브리스트로 나누어 각각 삽입 정렬하고 다시 k보다 작은 수의 서브리스트가 되도록 나누어 삽입 정렬하는 것을 반복, 서브리스트로 나눌 때 인덱스의 일정한 간격을 가진 원소들만 포함(h*3+1)
(최선 O(nlogn), 최악 : O(n^4/3), 제자리 정렬, 불안정)
퀵 정렬
- 가장 오른쪽 원소 피봇으로 선정
- 왼쪽 피봇보다 작은 원소 오른쪽 피봇보다 큰원소, 피봇 a[i]에 삽입
- 나눠진 외쪽 파티션과 오른쪽 파티션에 대해 다시 퀵정렬
분할 방법 - (i)왼쪽에서 오른쪽으로 움직이며 피봇보다 큰 값 찾기
- (j)오른쪽에서 왼쪽으로 움직이면 피봇보다 작은 값 찾아서 교환
- 왼쪽 포인터와 오른쪽 포인터 만나면 피봇과 i 교환
a[0]에 j가 배열 범위 벗어나지 않게 감시 키 필요
(분할 정복 기법을 사용한 정렬 방법의 하나)
(제자리, 불안정, 최선 O(nlogn), 최악 : O(n^2))
퀵 정렬 성능 향상시키는 방법
1. 작은 부분화일 : 처리해야 할 원소 수가 일정 상수보다 작아지면 삽입 정렬 수행
2. 중간값 분할 : 왼쪽, 가운데, 오른쪽 원소를 정렬한 후 가장 작은 값을 A[l], 가장 큰 값을 A[r], 중간 값을 A[r-1]에 넣고 A[l+1]...A[r-2]에 대해 분할 알고리즘 수행(최악의 경우가 발생하는 확률을 낮추고 감시 키가 필요 없음)
합병 정렬
: 나누어지지 않을 때까지 이등분해서 두 리스트의 원소 비교해서 하나로 합치면서 정렬
(제자리X - 추가 기억장소 필요, 안정적, 최악에도 O(nlogn))
(순차적 방식으로 데이터에 접근하므로 연결리스트와 같이 순차 접근이 유일한 방법일 경우에도 사용 가능)
(입력 배열에 민감X)
히프 정렬
: 원소를 히프에 넣고 하나씩 삭제해서 삭제한 원소 리스트의 뒤에서부터 삽입
(제자리, 안정적X, O(NlogN))
(입력 배열에 민감X)
계수 정렬
: 크지않은 범위 내에 입력키가 있을 때 사용, 원소들의 개수를 세면 어떤 원소가 어느 위치에 들어가는지 알 수 있음, 배열 뒤에서부터 하나씩 가져와서 다른 배열에 복사 그다음 카운트 값 하나 감소
(제자리X, 안정적, O(N))
기수 정렬
: 키 값의 자리 수를 기초로 정렬, 가장 작은 자리 수를 기준으로 계수 정렬을 수행 후 그 다음 자리 수로 계수 정렬하는 것을 반복
(제자리X, 안정적, O(N))
