[알고리즘] 정렬에 관한 자료(Quick, Merge, Heap Sort)

목차

1. 개요
2. 설계
3. 소스
4. 고찰

본문내용

1)Quick-Sort
퀵 정렬은 버블정렬이나 선택정렬에서 배열의 인접 원소끼리 비교, 교환 작업을 하는데서 발생될 수 있는 비효율성을 개선한 정렬 방법이다. 제 위치에서 멀리 떨어진 원소들이 많으면 많을수록 버블정렬이나 선택정렬은 비효율적이라고 할 수 있다. 즉, 퀵 정렬은 멀리 떨어져 있는 원소들을 비교, 교환해서 정렬을 하는 방식이다.
장점: 평균적으로 약 의 시간이 소요되며 안쪽 루프가 매우 짧다.
단점: 알고리즘이 순환적이며 최악의 경우 의 시간이 소요된다.
퀵 정렬은 분할정복 방법을 적용한 것으로 파일을 두 부분으로 나눈 후 이 부분들을 다시 순환적으로 정렬한다.
퀵 정렬의 핵심은 분할(partition) 프로시저로서 우단의 원소를 분할 원소로 취하여 이를 제 위치에 위치시키며 그 좌측은 분할 원소보다 작거나 같은 원소가 오도록 하고 우측은 크거나 같은 원소가 오도록 한다.
이미 정렬된 파일에 대해서는 한 번에 한 원소씩 줄이면서 n번 순환호출하게 되어 소요시간이 이 되고 순환에 필요한 공간도 이 된다.
퀵 정렬은 분할 원소를 항상 부분 배열의 중간값으로 취할 수 있다면 가장 성능이 좋으며 이다. 평균 성능 또한 이고 최악의 경우로 될 가능성이 낮다고 할 수 있다. 특히 임의성만 보장하면 시간을 달성할 수 있다.

참고 자료

없음