[알고리즘] 정렬(sorting)의 개요- 레코드(record), 키(key)

정렬

잘 알려져 있는 순서로(서명순, 학번순) 리스트에 있는 원소를 재배열 하는데 사용

 

레코드(record)와 키(key)

레코드 : 리스트의 각 원소를 부르는 말

키 : 보통의 경우 레코드의 한 서브 필드를 의미

- key Ki는 record Ri 와 연관되어있다.

- ex) 학생이라는 레코드는 이름, 학번, 점수 등의 키를 가진다.

 

 

내부정렬(internal sorting)과 외부정렬(external sorting)

내부정렬 : 정렬할 레코드가 주 기억 장치에 있는 것

외부정렬 : 정렬할 레코드가 보조 기억 장치에 있는 것

 

안정적(stable) 알고리즘

한 리스트에서 두 개의 레코드 Ri와 Rj의 키 값이 같으면서, 즉, Ki = Kj 이면서

Ri가 Rj보다 앞에 위치하고 있을 때, 정렬된 리스트에서도 레코드 Ri가 레코드 Rj보다 앞에 위치한다면

이러한 정렬기법을 안정적(stable)이라고 한다.

 

비교 기반 정렬(comparion-based sort) 알고리즘

정렬 알고리즘 중에서 키 값들의 비교를 통해 정렬을 수행하는 알고리즘

- 대부분 정렬 알고리즘이 비교 기반 정렬 알고리즘

- 이런 알고리즘의 최선의 경우 시간 복잡도는 O( N logN )임이 증명됨

 

제자리(in place)정렬 알고리즘

정렬 알고리즘에서 입력 배열 이외의 추가 기억장소의 수가 상수 개를 넘지 않는 알고리즘

- array 대신 linked list를 사용한다면 리스트 포인터를 위한 N개의 추가 기억장소가 필요

- 합병 정렬, 계수 정렬 등의 알고리즘은 정렬시킬 배열과 동일한 크기의 추가 기억장소를 필요

 

 

정렬 알고리즘의 효율성을 비교하는 기준

원소의 비교 횟수, 원소의 이동 횟수

 

감시키(sentinel key), 더미 키(dummy key)

배열의 data비교시 배열의 한계를 벗어나지 않도록 배열의 모든 원소보다 작은 키값을 사용

- 경계로 사용하는 키 값, a[0]에 저장

 

난수 발행 함수 rand(), srand48(), lrand48()

rand는 16비트 정수인 32,767이하의 난수만을 발생시킨다.

Unix기반 환경에서 이보다 큰 난수를 발생시키고 싶을때 srand48()과 lrand48()을 사용

 

알고리즘을 접했을 때 생각할 것들

내부정렬기반인지 외부정렬기반인지,

안정적인지 불안정적인지

입력자료의 순서에 민감한지 민감하지 않은지

제자리 정렬인지 제자리 정렬이 아닌지