본문 바로가기

CS/정렬

(2)

내부 정렬 선택 정렬 - 레코드의 이동 횟수를 줄이려는 목적에서 개발되었으며, 자료 중에서 최솟값 또는 최댓값을 선택해 가면서 리스트의 처음이나 마지막으로 이동하는 방식 - 키 비교 횟수를 정확히 산출할 수 있으나 정렬 도중에 이미 정렬이 완료된 경우라도 이를 확인할 수가 없다. 최대 비교 횟수는 n(n-1)/2 이므로 O(n^2)이 된다. 거품 정렬 - 인접한 레코드의 키 값을 비교해서 그 크기에 따라 교환하는 방식으로, 각 단계마다 가장 큰(작은) 키 값을 갖는 레코드를 마지막에 위치시킨다. - 이미 정렬이 부분적으로 완료되어 있는 상태에서는 사실상 이들 레코드들의 키 값을 비교할 필요가 없는데도 불필요하게 비교 작업이 반복되는데, 이때 flag를 사용하면 이런 단점을 보완할 수 있다. - 이렇게 하면 n개의 ..

정렬 정렬의 종류 내부정렬 - 정렬하고자 하는 파일을 주기억장치에 모두 넣고 정렬하는 방법으로, 정렬 속도가 빠르고 처리하는 데이터양이 적을 경우 적합 삽입법 : 삽입정렬, 쉘정렬 교환법 : 버블정렬, 퀵정렬 선택법 : 선택정렬, 힙정렬 합병법 : 2원 합병정렬 분배법 : 기수정렬 외부정렬 -정렬하려는 파일의 크기가 너무 커서 주기억장치에 모두 적재할 수 없는 경우, 파일을 보조기억장치에 두고 정렬하는 방법으로 속도가 느리다. 디스크를 사용 : k-원 합병정렬 테이프를 사용 : 균형 합병정렬, 다단계 합병정렬, 계단식 합병정렬, 진동 합병정렬 정렬 방법에 따른 분류 비교 정렬 - 각 레코드의 키 값을 두 개씩 비교하여 교환하는 정렬 방법으로 선택 정렬, 삽입 정렬, 쉘 정렬, 퀵 정렬, 버블 정렬, 힙 정렬,..

티스토리툴바