[컴퓨터]퀵정렬(Quick Sort)

소개글

이산수학 재귀를 들으면서 쓴 레포트입니다.
퀵정렬 수행과정을 표로 알기쉽게 정리 했습니다.
한 번 보면 바로 이해할 수 있습니다.

목차

1. 퀵 정렬 개념
2. 퀵 정렬 알고리즘
3. 퀵 정렬 사례 수행 과정
4. 퀵 정렬 분석

본문내용

1. 퀵 정렬 개념
▶ 주어진 입력 리스트를 피봇(pivot) 또는 제어키(control key)이라 불리는 특정 키 값보다 작은 값을 가지는 레코드들의 리스트와 큰 값을 가지는 레코드들의 리스트로 분리한 다음,
이러한 두 개의 서브 리스트들을 재귀적으로 각각 재배열하는 과정을 수행하는 방식

▶ 퀵 정렬 방법은 하나의 커다란 입력 데이터의 집합을 정렬하는 것보다는 두개의 작은
입력 데이터들을 정렬하는 것이 빠르다는 일반적인 사실에 바탕을 둠

▶ 분할 및 정복 방법 사용

▶ 피봇(Pivot)이라 부르는 특정한 데이터를 기준으로 피봇보다 작은 값을 가진 데이터들은
배열의 왼쪽 부분에, 큰 값을 가진 데이터는 오른쪽에 위치하도록 배열

▶ 퀵 정렬은 기본적으로 순환(recursive) 알고리즘 형태를 취하며, 오름차순으로 정렬할
경우 레코드 R1을 제어 키 또는 피봇 키로 하여 왼쪽으로 가면서 R1보다 큰 키 값을 찾고,
오른쪽으로부터 왼쪽으로 가면서 R1보다 작은 키 값을 찾아 서로 교환한다. 위의 과정이
수행될 때 오른쪽과 왼쪽이 서로 교차하면 중지하고 R1을 제일 나중에 찾은 R1보다 작은
키 값과 교환하면 R1보다 작은 키 값을 갖는 레코드들과 큰 키 값을 갖는 레코드들로 분할
되어 하나의 파일이 제어키 R1을 기준으로 두 개의 서브 파일로 재배열된다. 재배열된
서브파일에 대해 독립적으로 위의 수행 과정을 반복하면 정렬이 완료된다.

2. 퀵 정렬 알고리즘
▶ 퀵 정렬 알고리즘 단계 : 분할과 정복 방식
① 피봇(Pivot) : 정렬할 데이터 S에서 하나 v를 선택한다.
② 분할 : S1 = {v보다 작은 수}, v, S2 = {v보다 큰 수}
③ 재귀적 수행 : return {퀵 정렬(S1), v, 퀵 정렬(S2)}

참고 자료

없음