CHAP 9: 정렬 2016. 11. 1 순천향대학교 컴퓨터학부 하 상 호

정렬이란? 정렬은 항목들을 어떤 기준으로 나열하는 것 정렬은 컴퓨터 공학분야에서 가장 기본적이고 중요한 알고리즘중의 하나 오름 차순(ascending order) 내림 차순(descending order) 정렬은 컴퓨터 공학분야에서 가장 기본적이고 중요한 알고리즘중의 하나 정렬은 자료 탐색에 있어서 필수적이다. (예) 만약 사전에서 단어들이 정렬이 안되어 있다면?

정렬의 단위 학생들의 레코드 이름 학번 주소 연락처 필드 필드 필드 필드 레코드 키(key)

정렬 알고리즘의 개요 많은 정렬 알고리즘 존재 정렬 알고리즘의 평가 효율성 관점에 평가 비교횟수 및 이동횟수 단순하지만 비효율적인 방법 -- 삽입정렬, 선택정렬, 버블정렬 등 복잡하지만 효율적인 방법 -- 퀵정렬, 히프정렬, 합병정렬, 기수정렬 등 정렬 알고리즘의 평가 효율성 관점에 평가 비교횟수 및 이동횟수 비교와 이동 회수는 비례하지 않음 빅오 표기법 알고리즘 분석 모든 경우에 최적인 알고리즘은 없음 응용에 맞추어 선택 숫자와 문자열 비교, 숫자와 구조체 이동 고려

정렬 방법(2) 내부 정렬 vs. 외부 정렬 정렬전에 모든 항목이 메모리에 적재되었는지의 여부 외부 정렬은 대부분의 데이터가 외부 기억장치에 존재하고, 일부만 메모리에 적재되어 있는 방식 여기서는 내부 정렬만을 다룸 안전성(stability) 여부 동일한 키 값을 갖는 항목이 여러 개 존재할 경우에, 이들의 상대적 위치가 정렬 후에도 변경되는지의 여부 안정하지 않은 정렬 예 30 30 10 20 : 정렬 전 10 20 30 30 : 정렬 후

선택정렬(selection sort) 선택정렬(selection sort): 정렬이 안된 숫자들중에서 최소값을 선택하는 방식으로 정렬 방법 1: 2개의 리스트 고려 리스트 1 리스트 2 설명 (5, 3, 8, 1, 2, 7) () 초기 상태 (5, 3, 8, 2, 7) (1) 리스트 1의 가장 작은 원소 를 선택 => 리스트2로 이동 (5, 3, 8, 7) (1, 2) (5, 8, 7) (1, 2, 3) ... ...

선택정렬(selection sort) 방법 2: 한 개의 리스트로 해결 가장 작은 원소를 첫번째 배열 원소와 교환 두번째 작은 원소를 두번째 배열 원소와 교환 ….

선택정렬 알고리즘 알고리즘 개략적 버전 selection_sort(A, n) for i←0 to n-2 do least ← A[i], A[i+1],..., A[n-1] 중에서 가장 작은 값의 인덱스; A[i]와 A[least]의 교환; repeat end selection_sort

선택정렬 알고리즘 알고리즘 개략적 버전 selectionSort(a, n) for i←0 to n-2 do least ← A[i], A[i+1],..., A[n-1] 중에서 가장 작은 값의 인덱스; A[i]와 A[least]의 교환; repeat end selection_sort selectionSort(a, n) // a: array of integers, n: size of array for (i=0 to n-2) do least <- i; repeat End selectionSort // i번째 가장 작은 원소를 찾고, 그 원소와 i번째 요소를 교환

선택정렬 알고리즘 분석 알고리즘 분석 비교 회수는? 이동 회수는

삽입정렬(insertion sort) 삽입정렬은 정렬되어 있는 부분에 새로운 레코드를 적절한 위치에 삽입하는 과정을 반복 배열을 정렬된 부분과 정렬 안된 부분으로 구분 삽입정렬의 과정

삽입정렬 알고리즘 알고리즘(개략적 버전) InsertionSort(list, n):         // Input: n개의 정수를 저장하고 있는 배열 list         // Output: 정렬된 배열 list         for i←1 to n-1 do                      정렬된 리스트에서 list[i]보다 더 큰요소들이동;               list[i]를 정렬된 리스트의 적절한 위치에 삽입;         repeat end insertionSort

삽입정렬 알고리즘 알고리즘 insertionSort(a, n) // a: array of integers, InsertionSort(list, n)         // Input: n개의 정수를 저장하고 있는 배열 list         // Output: 정렬된 배열 list         for i←1 to n-1 do                      정렬된 리스트에서 list[i]보다 더 큰요소들이동;               list[i]를 정렬된 리스트의 적절한 위치에 삽입;          repeat end insertionSort 알고리즘 insertionSort(a, n) // a: array of integers, // n: size of array for (i=1 to n-1) do // i번째 원소를 이미 정렬된 상태가 유지되게 삽입 key <- a[i]; // 삽입 대상 원소 repeat end insertionSort // key의 삽입 위치를 탐색하고 그곳에 삽입

삽입정렬 알고리즘 분석 최악의 경우는? 비교 회수: 이동 회수: 최선의 경우는?

버블정렬(bubble sort) 인접한 2개의 항목을 비교하여 크기가 순서대로 되어 있지 않으면 교환 이를 비교-교환 과정이라 한다. 비교-교환과정을 리스트의 왼쪽 끝부터 오른쪽 끝까지 진행 비교-교환 과정이 한번 완료되면, 가장 큰 항목이 어디에 위치하는가? 전체가 정렬될 때까지 비교/교환 과정 계속

버블정렬 알고리즘 알고리즘(개략적 버전) 위의 알고리듬을 완성하면? bubbleSort(A, n) for i←n-1 to 1 by -1 do// 비교할 원소의 마지막 인덱스 for j←0 to i-1 do // 비교할 원소의 인덱스 범위 + 1 j와 j+1번째의 요소가 크기순이 아니면 교환 repeat end bubbleSort

버블정렬 알고리즘 분석 비교횟수 최악의 경우는 최상의 경우는? 이동횟수 최악의 경우는? 최상의 경우는

버블정렬 알고리즘 분석 평가 단순하지만 교환 회수가 많다 거의 사용되지 않음

예제: 정렬 알고리즘 비교 다음 수들을 오름차순으로 정렬하고자 한다. 다음 각 정렬방법을 적용하였을 때, 비교 회수와 이동 회수를 구하라. (7, 4, 9, 6, 3, 8, 7, 5) 선택 정렬 삽입 정렬 버블 정렬

쉘정렬(Shell sort) Donald L. Shell이 고안 삽입정렬이 어느 정도 정렬된 배열에 대해서는 대단히 빠른 것에 착안 개념 리스트를 연속적이지 않은 여러 개의 부분 리스트로 분할 부분 리스트는 리스트의 각 k번째 요소를 추출하여 구성 => 이를 k-간격이라 함 각 부분 리스트를 삽입 정렬을 이용하여 정렬 더 적은 개수의 부분 리스트로 분할 (k-간격에서 k값을 줄인다) 위의 과정을 부분 리스트의 크기가 1이 될 때까지 반복

쉘정렬(Shell sort) 다음 리스트에 대해서 적용 리스트: (10, 8, 6, 20, 4, 3, 22, 1, 0, 15, 16) Gap = 5일 때, Gap = 3일 때, Gap = 1일 때,

쉘정렬 알고리즘(1) for (gap = n/2; gap > 0 ; gap = gap/2) do ShellSort(a, n) // a: array of integers, n: size of array end shellSort for (gap = n/2; gap > 0 ; gap = gap/2) do if (gap % 2 ==0 ) then // gap이 짝수이면 gap++; // gap은 홀수가 좋은 것으로 분석 endif for (i = 0; i < gap; i++) do insertionSort2(a, i, n-1, gap); repeat

쉘정렬 알고리즘 insertionSort2(a, first, last, gap) // a: array of integers, first, last, gap: integer // first: 첫번째 원소 인덱스, last: 마지막 원소 인덱스, gap: 간격 end shellSort

쉘 정렬 알고리즘 분석 최악의 경우 평균적인 경우 쉘 정렬의 장점은? O(n2) O(n1.5) (실험적 연구결과) 자료 교환이 큰 거리로 이동하여 이동 회수를 줄인다 부분 리스트는 어느정도 정렬된 상태, 삽입 정렬이 거의 정렬된 상태에서 빠르게 수행되는 효과를 이용

예제: 쉘 정렬 다음 수들을 오름차순으로 쉘 정렬방법을 적용하였을 때, 비교 회수와 이동 회수를 구하라. (7, 4, 9, 6, 3, 8, 7, 5) 비교 회수 이동 회수