3퀵소트 Report

 자료 (압축파일).zip

3퀵소트

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

2)퀵 정렬 방법은 하나의 커다란 입력 데이터의 집합을 정렬하는 것보다는 두개의 작은 입 력 데이터들을 정렬하는 것이 빠르다는 일반적인 사실에 바탕을 둠
3)분할 및 정복 방법 사용
4)피봇(Pivot)이라 부르는 특정한 데이터를 기준으로 피봇보다 작은 값을 가진 데이터들은
배열의 왼쪽 부분에, 큰 값을 가진 데이터는 오른쪽에 위치하도록 배열
5)퀵 정렬은 기본적으로 순환(recursive) 알고리즘 형태를 취하며, 오름차순으로 정렬할 경 우 레코드 R1을 제어 키 또는 피봇 키로 하여 왼쪽으로 가면서 R1보다 큰 키 값을 찾고, 오른쪽으로부터 왼쪽으로 가면서 R1보다 작은 키 값을 찾아 서로 교환한다. 위의 과정이 수행될 때 오른쪽과 왼쪽이 서로 교차하면 중지하고 R1을 제일 나중에 찾은 R1보다 작 은 키 값과 교환하면 R1보다 작은 키 값을 갖는 레코드들과 큰 키 값을 갖는 레코드들로 분할되어 하나의 파일이 제어키 R1을 기준으로 두 개의 서브 파일로 재배열된다. 재배열 된 서브파일에 대해 독립적으로 위의 수행 과정을 반복하면 정렬이 완료된다.
·퀵 정렬 알고리즘의 단계: 분할과 정복 방식
① 피봇(Pivot) : 정렬할 데이터 S에서 하나 v를 선택한다.
② 분할 : S1 = {v보다 작은 수}, v, S2 = {v보다 큰 수}
③ 재귀적 수행 : return {퀵 정렬(S1), v, 퀵 정렬(S2)}
·특징
1)평균 연산 시간에 있어서 내부 정렬 방법 중 가장 우수
- 실제 수행속도가 가장 빠른 정렬 알고리즘
2)스택 공간을 사용
3)재귀 호출을 기반으로 동작
·퀵 정렬 과정 사례
①초기 데이터
0 1★ 2 3 4 5 6 7☆ 8 9
8149635270
②3수의 중위수 피봇
-왼쪽, 중앙, 오른쪽 세수를 정렬한다.
-중앙의 수를 피봇한다.
-피봇된 수를 오른쪽-1의 위치에 있는 수와 SWAP한다.
0 1★ 2 3 4 5 6 7☆ 8 9
0142735968
왼쪽 피봇 오른쪽
③분할 : S1 = {v보다 작은 수}, v, S2 = {v보다 큰 수}
-★ 위치의 수를 피봇수와 비교하면서 증가시킴, 클 때 중단
-☆ 위치의 수를 피봇수와 비교하면서 감소시킴, 작을 때 중단
-★<☆이면 ★,☆의 위치에 있는 수를 SWAP한다
0 1 2 3★ 4 5 6 7☆ 8 9
0142735968
왼쪽 피봇 오른쪽
0 1 2 3 4★ 5 6☆ 7 8 9
0142537968
왼쪽 피봇 오른쪽
-i>j이면 피봇 수와 i의 위치에 있는 수를 SWAP한다.
0 1 2 3 4 5★ 6☆ 7 8 9
0142536978
왼쪽 피봇 오른쪽
④ 재귀적 수행 : return {퀵 정렬(S1), v, 퀵 정렬(S2)}
0 1 2 3 4 5 6 7 8 9
0142536978
·예제로 보는 퀵 정렬 단계


자료출처 : http://www.ALLReport.co.kr/search/detail.asp?pk=16131155&sid=qjfRnf777&key=



[문서정보]

문서분량 : 4 Page
파일종류 : HWP 파일
자료제목 :
파일이름 : 3퀵소트.hwp
키워드 : 3퀵소트



[추천자료]

- MU-2 국제단위계(SI)
- 효소반응 속도
- 후위식 변환과 계산
- 연세대학교 화폐금융론(00중간) 김학은
- 기업경영 조직