정렬 알고리즘

정렬 알고리즘의 구분

- 정렬 알고리즘을 선택할 때는 사용되는 컴퓨터 시스템의 특징, 정렬할 자료의 양, 초기 자료의 배열

상태, 키 값의 분포 상태, 작업 공간의 크기, 자료의 이동 횟수, 키의 비교 횟수 등을 고려함

[표-1]정렬 알고리즘의 상세구분

구분 정렬 알고리즘의 상세설명

 

내부 정렬(Internal Sorting)

삽입 - 정렬되지 않은 리스트의 레코드를 정렬된 리스트의 순서에 맞게 삽입

쉘 - 주어진 리스트를 적당한 매개변수 값만큼 떨어진 레코드와 비교하여 교환하는 과정을 반복하는 방법

버블 - 가장 큰 레코드가 한칸씩 오른쪽 끝으로 이동되는 정렬방법

퀵 - 분할 및 정복법에 기반 전체 리스트를 2개로 분할 후 각각 다시 정렬

선택 - 가장 작은(또는 큰)값을 가장 왼쪽에 위치, 나머지 레코드에 대해 동일하게 반복

Heap - 레코드를 트리구조인 힙형태로 변환, 가장 큰 레코드 키 값을 가지는 로트 노드를 출력한 후 나머지 트리를 다시 힙으로 구성하는 방법

2-way merge - 주어진 레코드들을 각각 크기가 1인 정렬된 리스트로 간주, 순서에 맞추어 반복적으로 합병함으로써 최종적으로 1개의 리스트를 생성

기수 - 숫자의 각 자리수를 기준으로 정렬

 

외부 정렬(External Sorting)

균형합병 - 정렬하고자 하는 입력 파일을 몇 개의 테이프로 균등하게 분배하여 합병하는 방법

다단계 합병 - 입력 파일의 분배 시에 피보나치 수열을 이용하여 분배하는 정렬방법

교대합병 - 자기테이프의 순방향과 역방향 모두 가능한 상태에서 사용

계단식 합병 - 복사량을 줄이기 위한 불균형 방법 중 하나로 연속 병합 정렬이라고 함

- 내부 정렬(Internal Sorting): 데이터의 크기가 주 기억장소 용량보다 적을 경우 기억장소를 활용하여 정렬

- 외부 정렬(External Sorting): 데이터의 크기가 주 기억장소 용량보다 클 경우 외부 기억장치를 사용 정렬

 

[알고리즘의 효율성]

공간 - 공간적 효율성은 얼마나 많은 메모리 공간을 요하는가를 말함

시간 - 시간적 효율성은 얼마나 많은 시간을 요하는가를 말함

     - 효율성을 뒤집어 표현하면 복잡도(Complexity)가 되며, 복잡도가 높을수록 효율성은 저하된다.