검색어 입력폼

퀵 소트 핵심 정리

저작시기 2006.10 |등록일 2006.10.29 워드파일MS 워드 (doc) | 1페이지 | 가격 500원

목차

◎ 퀵정렬의 특징
◎ 퀵정렬 알고리즘의 수행단계
◎ 퀵정렬의 효율성

본문내용

1. QUICK SORT에 대해 설명하시오.
◎ 퀵정렬의 특징
- 퀵정렬은 O(nlogn)의 실행시간을 갖는 C. A. R. Hoare가 고안한 가장 널리 사용되는 알고리즘의 하나임.
- 퀵정렬에서는 정렬할 키들을 배열 내에서 적당히 이동시키면서 다음의 두 조건이 만족되도록
배열을 오른쪽 부분배열과 왼쪽 부분배열로 나눈다.
(1) 왼쪽 부분배열에 있는 모든 키들은 오른쪽 부분배열의 가장 작은 키보다도 작고
(2) 오른쪽 부분배열에 있는 모든 키들은 왼쪽 부분배열의 가장 큰 키보다 크다
배열을 이렇게 나누면, 앞으로의 정렬 과정에서 왼쪽 부분배열과 오른쪽 부분배열에 독립적으로
퀵정렬을 순환적으로 적용함으로써 배열 전체를 정렬할 수 있다.
- 퀵정렬은 분할 정복(divide and conquer)방식의 정렬 알고리즘이다.
다운로드 맨위로