빠른정렬(Quick Sort) – 개요 (1/2)

Slides:



Advertisements
Similar presentations
Ⅰ. 연산자 Ⅱ. 제어 구조. 연산자 : 할당 연산자 - 사용자가 정의한 변수에 임의의 값을 저장하는 기능 strvar = strVar1+ “ Hello ”
Advertisements

Chapter 12. 배열. 배열  동일한 항목들이 동일한 크기로 연속적으로 메모리에 저장되는 구조  동일한 자료 유형이 여러 개 필요한 경우에 이용할 수 있는 자료 구조.
1. 2 차원 배열  배열은 동일한 데이터 유형으로 여러 개의 변수를 사용할 경우 같은 이 름으로 지정하여 간편하게 사용할 수 있도록 하는 것으로서 앞에서 1 차원 배열을 공부하였습니다.  2 차원 배열은 바둑판을 생각하면 되며, 1 차원 배열에서 사용하는 첨자를 2.
알고리즘 기본 개념 정렬 알고리즘 탐색 알고리즘 알고리즘 복잡도.
Report #5 - due: 4/13 다음 10*5의 희소 행렬 A, B를 고려하라.
9장. C 언어의 핵심! 함수. 9장. C 언어의 핵심! 함수 9-1 함수의 정의와 선언 main 함수 다시 보기 : 함수의 기본 형태 { } 그림 9-1.
Report #2 - Solution 문제 #1: 다음과 같이 프로그램을 작성하라.
알고리즘(Algorithm)  알고리즘 개요 (효율, 분석, 차수) Part 1 강원대학교 컴퓨터과학전공 문양세.
컴퓨터 프로그래밍 기초 [Final] 기말고사
보고서 #7 (기한: 6/2) 2개의 스택, stk1, stk2를 이용하여 큐를 구현하라.
알고리즘 강의 슬라이드 2 분할정복 강의 슬라이드 #2
7장 배열 ②.
분할 정복 (Divide-and-Conquer)
누구나 즐기는 C언어 콘서트 제8장 배열.
7. 계산복잡도 개론 정렬 문제 알고리즘 강의 슬라이드 7 정렬문제
자료구조론 11장 정렬(sort).
Lesson 9. 예외처리.
빠른정렬(Quick Sort) – 개요 (1/2)
11장. 포인터 01_ 포인터의 기본 02_ 포인터와 Const.
쉽게 풀어쓴 C언어 Express 제10장 배열 C Express Slide 1 (of 32)
제8장 배열 1부 8.1 배열 8.2 배열의 초기화 8.3 배열의 응용 8.4 정렬과 탐색 8.5 다차원 배열.
11장. 1차원 배열.
CHAP 9: 정렬 (part 2) 순천향대학교 컴퓨터학부 하 상 호.
Introduction To Data Structures Using C
프로그래밍 개요
어서와 C언어는 처음이지 제14장.
박성진 컴퓨터 프로그래밍 기초 [09] 배열 part 1 박성진
CHAP 9: 정렬 순천향대학교 컴퓨터학부 하 상 호.
Quiz #7 다음 수들을 합병 정렬과 퀵 정렬 알고리즘을 이용하여 오름 차순으로 정렬하였을 때, 데이터 이동 회수를 각각 구하라. 여러분은 정렬 과정을 단계별로 보이면서 이동 회수를 추적해야 한다. 단, 퀵 정렬시에 피봇으로 배열의 왼쪽 첫 번째 원소를 선택한다. 5.
제 1 장 알고리즘 : 효율, 분석, 그리고 차수.
Ch.02 Divide and Conquer (분할정복)
알고리즘(Algorithm)  알고리즘 개요 (효율, 분석, 차수) Part 년 봄학기
Chapter6 : JVM과 메모리 6.1 JVM의 구조와 메모리 모델 6.2 프로그램 실행과 메모리 6.3 객체생성과 메모리
[CPA340] Algorithms and Practice Youn-Hee Han
[CPA340] Algorithms and Practice Youn-Hee Han
컴퓨터 프로그래밍 기초 - 10th : 포인터 및 구조체 -
행렬의 개요 행렬은 수를 원소로 지니는 다차원 배열이다. mn (“m by n”) 행렬은 m개의 행과 n개의 열을 갖는다.
행렬의 개요 행렬은 수를 원소로 지니는 다차원 배열이다. mn (“m by n”) 행렬은 m개의 행과 n개의 열을 갖는다.
알고리즘 강의 슬라이드 2 분할정복 분할정복법 도경구역, 알고리즘, 사이텍미디어, 1999.
 Divide and Conquer (분할정복)
컴퓨터 프로그래밍 기초 - 8th : 함수와 변수 / 배열 -
 Divide and Conquer (분할정복)
보고서 #7 (기한: 6/2) 2개의 스택, stk1, stk2를 이용하여 큐를 구현하라.
컴퓨터 프로그래밍 기초 [01] Visual Studio 설치 및 사용방법
 Divide and Conquer (분할정복)
2014년 가을학기 손시운 지도 교수: 문양세 교수님 데이터 프레임 2014년 가을학기 손시운 지도 교수: 문양세 교수님.
[CPA340] Algorithms and Practice Youn-Hee Han
균형이진탐색트리 이진 탐색(binary search)과 이진 탐색 트리(binary search tree)와의 차이점
미분방정식.
알고리즘의 분석(analysis) 공간적 효율성(Space Efficiency)과 시간적 효율성(Time Efficiency)
합병정렬(Merge Sort) (1/2) 문제: n개의 정수를 (비내림차순으로) 정렬하시오.
디버깅 관련 옵션 실습해보기 발표 : 2008년 5월 19일 2분반 정 훈 승
DA :: 퀵 정렬 Quick Sort 퀵 정렬은 비교방식의 정렬 중 가장 빠른 정렬방법이다.
5장. 선택 알고리즘.
7주차: Functions and Arrays
알고리즘 강의 슬라이드 2 분할정복 제 2 장 분할정복 도경구역, 알고리즘, 사이텍미디어, 1999.
쉽게 배우는 알고리즘 2장. 점화식과 점근적 복잡도 분석
CHAP 9: 정렬 순천향대학교 컴퓨터학부 하 상 호.
11장 배열 1. 배열이란? 1.1 배열의 개요 1.2 배열의 선언과 사용.
알고리즘의 분석(analysis) 공간적 효율성(Space Efficiency)과 시간적 효율성(Time Efficiency)
컴퓨터 프로그래밍 기초 - 9th : 배열 / 포인터 -
알고리즘(Algorithm) – Divide and Conquer (분할정복)
Static과 const 선언 조 병 규 한 국 교 통 대 학 교 SQ Lab..
수치해석 ch3 환경공학과 김지숙.
제 29 강 스트링(string) 다루기 s a i s . s T i h t g r i n.
29장. 템플릿과 STL 01_ 템플릿 02_ STL.
빠른정렬(Quick Sort) – 개요 (1/2)
BoardGame 보드게임 따라가기.
알고리즘의 분석(analysis) 공간적 효율성(Space Efficiency)과 시간적 효율성(Time Efficiency)
2019 2학기 9장 배열과 포인터 1. 주소, 주소연산자(&) 2. 포인터, 역참조연산자(*) 3. 배열과 포인터.
Presentation transcript:

빠른정렬(Quick Sort) – 개요 (1/2) 1962년에 영국의 호아(C.A.R. Hoare)의 의해서 고안 빠른정렬(Quicksort)란 이름이 오해의 여지가 있음 사실 가장 빠른 정렬 알고리즘이라고 할 수는 없다. 주어진 배열을 두 개로 분할하고, 각각을 정렬한다.  합병정렬과 동일? 합병정렬과 다른점 합병정렬은 그냥 두 부분으로 나누는 반면에, 빠른정렬은 분할할 때부터 기준 아이템(pivot item) 중심으로, 이보다 작은 것은 왼편, 큰 것은 오른편에 위치시킨다.  즉, 정렬(정복과정)이 분할 과정에서 함께 행해진다. 각 부분 정렬이 끝난 후, 합병정렬은“합병”이라는 후처리 작업이 필요하나, 빠른정렬은 필요로 하지 않는다.

빠른정렬(Quick Sort) – 개요 (2/2) 예제: 15, 22, 13, 27, 12, 10, 20, 25

빠른정렬 – 정렬 알고리즘 (1/2) void quicksort (index low, index high){ 입력: (1) 크기가 n인 배열 S[1..n]  전역적으로 정의 (2) low - 배열의 첫번째 인덱스, high – 배열의 마지막 인덱스 출력: 비내림차순으로 정렬된 배열 S[1..n] 알고리즘 (교재와 약간 다름): [알고리즘 2.6] (P.61) void quicksort (index low, index high){ index pivotpoint; if (high > low) { pivotpoint = partition(low, high); quicksort(low, pivotpoint-1); quicksort(pivotpoint+1, high); }

빠른정렬 – 정렬 알고리즘 (2/2) quicksort(1,8) quicksort(1,3) 4 quicksort(5,8) 6 quicksort(7,8) 5 quicksort(2,2) 3 quicksort(4,3) quicksort(7,7) 8 quicksort(9,8) 2 7

빠른정렬 – 분할 알고리즘 (1/4) 문제: 빠른정렬을 하기 위해서 배열 S를 둘로 쪼갠다. 입력: (1) 첨자 low, high (2) 첨자 low에서 high까지의 부분배열 S[low,high]  전역적인 변수 출력: (1) S의 부분배열을 분할한 기준점 pivotpoint (2) 기준점 값에 의해 분할된 부분배열 S[low,high] (좌우로 이동 배치된 부분배열) NOTE: In-place 알고리즘: (see the next page)

빠른정렬 – 분할 알고리즘 (2/4) index partition (index low, index high){ index i, j, pivotpoint; keytype pivotitem; pivotitem = S[low]; j = low; //j의 역할: 아래 for루프가 끝난 후 pivotitem이 위치할 인덱스를 기억 for(i = low + 1; i <= high; i++) if (S[i] < pivotitem) { j++; exchange S[i] and S[j]; } pivotpoint = j; exchange S[low] and S[pivotpoint]; return pivotpoint;

빠른정렬 – 분할 알고리즘 (3/4) low=1, high=8 i j S[1] S[2] S[3] S[4] S[5] S[6] S[7] S[8] 비고 - 2 3 4 5 6 7 8 1 12 23 34 15 22 13 27 12 10 20 25 15 13 22 27 12 10 20 25 15 13 12 27 22 10 20 25 15 13 12 10 22 27 20 25 10 13 12 15 22 27 20 25 초기값 if-true for 종료 최종교환 pivotpoint

만약 S[i] >= pivotitem 이면 if 절이 false: i 값만 증가 빠른정렬 – 분할 알고리즘 (4/4) low j i high < pivotitem >= pivotitem to be investigated 만약 S[i] >= pivotitem 이면 if 절이 false: i 값만 증가 low j i high < pivotitem >= pivotitem to be investigated 만약 S[i] < pivotitem 이면 if 절이 true: j 증가 후, i 위치 값과 j 위치 값 교환 그 다음 i도 증가 low j high < pivotitem > pivotitem to be investigated i

빠른정렬 – 알고리즘 분석 (Worst Case) (1/4) [알고리즘 2.7]의 최악의 경우 시간복잡도 분석 단위연산: S[i]와 pivotitem과의 비교 입력크기: 부분배열이 가지고 있는 항목의 수, n = high - low + 1 분석: 배열의 첫번째 항목만 제외하고 모든 항목을 한번씩 비교하므로, W(n) = n – 1이다.  [주의] 여기서 n은 전체 배열 S의 크기로 고정되는 것이 아니라 partition 함수를 호출할 때의 부분배열 크기를 나타냄

빠른정렬 – 알고리즘 분석 (Worst Case) (2/4) [알고리즘 2.6]의 최악의 경우 시간복잡도 분석 단위연산: partition(low,high)의 호출  결국 S[i]와 pivotitem과의 비교 입력크기: 배열이 S가 가지고 있는 전체 항목의 수, n 분석: 최악의 경우: 배열이 이미 비내림차순으로 정렬이 된 경우 왜 그럴까? 비내림차순으로 정렬되어 있으면 첫번째(기준점) 항목보다 작은 항목은 없으므로, 크기가 0인 부분배열은 왼쪽에 오고, 크기가 n-1인 부분배열은 오른쪽에 오도록 계속 나누어진다. 따라서, 점화식은 다음과 같다. 여기서, W(0) = 0이므로, 최종적으로 점화식은 다음과 같다. W(n) = W(n - 1) + n - 1, if n > 0 W(0) = 0 W(n) = W(0) + W(n - 1) + n - 1

빠른정렬 – 알고리즘 분석 (Worst Case) (3/4) 이 점화식을 풀면, 다음과 같다. 이미 정렬이 되어 있는 경우 알고리즘의 시간복잡도는 n(n–1)/2이 된다.  

빠른정렬 – 알고리즘 분석 (Average Case) (4/4)  

빠른정렬 – 알고리즘 분석 (Average Case) (1/3)  

빠른정렬 – 알고리즘 분석 (Average Case) (2/3) 분석(계속): 양변에 n을 곱하면, n대신 n - 1을 대입하면, (1)에서 (2)를 빼면, 간단히 정리하면, 여기서, 라 하면, 다음과 같은 점화식을 얻을 수 있다. 그러면, 다음 관계가 성립한다.

빠른정렬 – 알고리즘 분석 (Average Case) (3/3) 분석(계속): 따라서, 해는 다음과 같다. 여기에서 오른쪽 항은 임의의 n에 대해 항상 1보다 작은 값이므로 무시한다. 그런데, ln n = logen이고, 이므로, 해는 an  2 ln n이다. 따라서, A(n)은 다음과 같다.  

[실습 4] 빠른 정렬 vs. 합병 정렬 빠른 정렬에 대한 [알고리즘 2.6, 2.7] 를 Java 프로그램으로 작성하고 이전에 작성한 합병 정렬과 속도를 비교해보자. SortMain2.java 를 분석하기 [note] java SortMain2 > out.txt 완성되지 않은 다음 두 함수를 작성한다. public static void quickSort(int low, int high) public static int partition(int low, int high) In-place 합병정렬과 빠른정렬의 수행 시간을 비교해보자. SortMain2 프로그램 자체를 여러 번 수행하여 두 알고리즘의 수행시간을 거듭 분석해보자. 어느 하나의 알고리즘이 다른 알고리즘보다 항상 더 빨리 수행되는가? 만약 그렇지 않다면 num의 크기를 더 늘려서 실험해보자. 만약 그렇다면 그 이유는 무엇일까 고민해보고 자신의 생각을 정리해서 작성하자. [Reference] http://en.wikipedia.org/wiki/Sorting_algorithm