Chapter 9 정렬(sorting) SANGJI University Kwangman KO

Slides:



Advertisements
Similar presentations
1 모터 (Motors) 김원웅. 2 모터 (Motor) □ 모터 응용분야 □ Desktop PC 의 DVD ROM, HDD □ 러닝머신, 전동드릴, 선풍기 등 전력에 의해서 뭔가가 움직이 는 분야에는 거의 모두 모터가 사용 □ 우리가 배울 모터의.
Advertisements

2014년도 주요법령 개정사항 (월) ~ (금) 대한전문건설협회 강원도회.
Computer Network Lab. Keimyung University
Recursion SANGJI University KO Kwangman
슬라이드 1~21까지는 각자 복습! 슬라이드 22부터는 수업시간에 복습
C++ Espresso 제3장 배열과 포인터.
C++ Espresso 제3장 배열과 포인터.
2017 법인관련 개정세법 곽장미 세무사.
배열(Array) 선린인터넷고등학교 정보통신과 유 순 옥.
리더십 역량 개발 계획서 핵심인재 양성 코스를 마치신 여러분, 수고하셨습니다.
시스템 생명 주기(System Life Cycle)(1/2)
알고리즘(Algorithm)  알고리즘 개요 (효율, 분석, 차수) Part 1 강원대학교 컴퓨터과학전공 문양세.
10장 정렬.
[INA470] Java Programming Youn-Hee Han
쉽게 배우는 알고리즘 3장. 정렬Sorting
알고리즘 강의 슬라이드 2 분할정복 강의 슬라이드 #2
시스템 생명 주기(System Life Cycle)(1/2)
배열, 포인터, 참조 배열은 같은 형을 가지는 변수들의 묶음이다..
스택(stack) SANGJI University Kwangman Ko
HW#2 #1과 동일한 방법으로 argc와 argv를 사용함
CHAP 9 : 정렬.
자료구조 김현성.
Internet Computing KUT Youn-Hee Han
C 7장. 배열과 문자열 #include <stdio.h> int main(void) { int num;
Ch. 10 Algorithm Efficiency & Sorting
Ch. 10 Algorithm Efficiency & Sorting
Internet Computing KUT Youn-Hee Han
1과목 데이터베이스 강사 이 민 욱.
CHAP 9:정렬 C로 쉽게 풀어쓴 자료구조 생능출판사 2005.
C언어 응용 제 13 주 그래프2, 정렬.
Chapter 10 그래프(graph) SANGJI University Kwangman KO
프로그래밍실습 제 17 강.
쉽게 풀어쓴 C언어 Express 제10장 배열 C Express Slide 1 (of 32)
제 7 장 정렬.
쉽게 풀어쓴 C언어 Express 제10장 배열 C Express.
12 검색.
정렬과 합병.
CHAP 9:정렬 C로 쉽게 풀어쓴 자료구조 Slide 1 (of 44).
Tree & Heap SANGJI University Kwangman Ko
국가대표 생애주기교육 프로그램 참여방법 안내
자료구조(SCSC) Data Structures
Quiz #7 다음 수들을 합병 정렬과 퀵 정렬 알고리즘을 이용하여 오름 차순으로 정렬하였을 때, 데이터 이동 회수를 각각 구하라. 여러분은 정렬 과정을 단계별로 보이면서 이동 회수를 추적해야 한다. 단, 퀵 정렬시에 피봇으로 배열의 왼쪽 첫 번째 원소를 선택한다. 5.
알고리즘(Algorithm)  알고리즘 개요 (효율, 분석, 차수) Part 년 봄학기
CHAP 9: 정렬 (part 2) 순천향대학교 컴퓨터학부 하 상 호.
Chap. 1 Data Structure & Algorithms
수업 첫 날 교육B 황유미 첫 수업 계획에 대해 알아보도록 하겠습니다..
[CPA340] Algorithms and Practice Youn-Hee Han
선택 정렬 #define SWAP(x, y, t) {(t) = (x); (x) = (y); (y) = (t);}
연결링크 이미지를 마일리지샵 내에 기획전으로 제작하여 오픈/노출 사이즈 가로 1000/세로 상관x 배너사이즈 가로 400
프로그래밍 기초와 실습 Chapter 11 Recursion.
자바 5.0 프로그래밍.
#1 배열 활용 #include int main(void) { int i; int grade[5]; grade[0] = 10; grade[1] = 20; grade[2] = 30; grade[3] = 40; grade[4] = 50; for(i=0;i.
Chapter 02. 소프트웨어와 자료구조.
CHAP 8:우선순위큐.
Chapter 11 해쉬(Hash) SANGJI University Kwangman KO
2010년 연말정산 교육자료 센터운영팀 인사파트
CHAP 12:탐색 C로 쉽게 풀어쓴 자료구조 생능출판사 2005.
CHAP 12 : 탐색.
CHAP 12 : 탐색 C로 쉽게 풀어쓴 자료구조 생능출판사 2011.
CHAP 9:정렬 C로 쉽게 풀어쓴 자료구조 생능출판사 2005.
Internet Computing KUT Youn-Hee Han
정렬(Sorting)과 해싱(Hashing)
알고리즘 강의 슬라이드 2 분할정복 제 2 장 분할정복 도경구역, 알고리즘, 사이텍미디어, 1999.
강의 #11 탐색(Search).
탐색 선형 탐색, 이진 탐색, 이진 탐색 트리.
알고리즘(Algorithm) – Divide and Conquer (분할정복)
CHAP 8:우선순위큐 C로 쉽게 풀어쓴 자료구조 생능출판사 2005.
알기쉽게 해설한 데이터구조 고 갑 승 한남대학교
제 7 장 정렬.
알고리즘 강의 슬라이드 7 정렬문제 알고리즘 해석 강의 슬라이드 #7
Presentation transcript:

Chapter 9 정렬(sorting) SANGJI University Kwangman KO (kkman@sangji.ac.kr)

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

정렬 알고리즘의 개요 정렬 알고리즘 분류 정렬 알고리즘 선택 단순하지만 비효율적인 방법 삽입정렬, 선택정렬, 버블정렬, … 복잡하지만 효율적인 방법 퀵정렬, 히프정렬, 합병정렬, 기수정렬, … 정렬 알고리즘 선택 모든 경우에 최적인 알고리즘은 없음 응용에 맞추어 선택 정렬 알고리즘의 평가 비교횟수 이동횟수

버블(bubble) 정렬 알고리즘 왼쪽부터 0,1,2,3,…,N-1로 가정 0에 있는 막대와 1에 있는 막대를 비교 오른쪽이 왼쪽보다 작으면 자리바꿈 그렇지 않으면 자리를 바꾸지 않음 위치를 오른쪽으로 한자리 이동 위치를 이동한 다음 1과 2를 비교 위 과정 반복

4가지 단계로 정리됨 첫 번째, 두 개의 항목을 비교. 두 번째, 오른쪽 항목이 작으면 자리 바꿈. 세 번째, 오른쪽으로 한 자리 이동. 네 번째, 가장 오른쪽에 한 항목을 비교할 때까지 앞의 3단계를 반복.

버블(bubble) 정렬

가장 왼쪽부터 비교 시작 위치 0와 위치 1을 항목을 비교 33이 11보다 크기 때문에 서로 자리를 바꿈

위치 1과 위치 2를 비교 33이 99보다 작기 때문에 자리를 바꾸지 않음

위치를 오른쪽으로 하나 이동해서 비교 99가 1보다 크기 때문에 자리를 바꿈 99가 22, 88, 55, 44, 66, 77보다 크므로 매번 자리를 바꿈

첫번째 정렬 후 오른쪽 끝의 막대는 정렬된 상태가 됨

두 번째 정렬 후 마지막 막대를 뺀 나머지를 정렬 대상으로 함

버블 정렬 in C #define SWAP(x, y, t) ( (t)=(x), (x)=(y), (y)=(t) ) void bubble_sort(int list[], int n) { int i, j, temp; for(i=n-1; i>0; i--){ for(j=0; j<i; j++) if( list[j] > list[j+1] ) SWAP(list[j], list[j+1], temp); }

버블 정렬 분석 비교 횟수 항목의 개수가 N이면 비교횟수 첫 번째 과정은 N-1번 두 번째 과정은 N-2번 정리 (N-1) + (N-2) + (N-3) + ... + 1 = N * (N-1) / 2 비교횟수는 최상, 평균, 최악의 어떠한 경우에도 항상 일정

선택(selection) 정렬 선택 정렬 버블 정렬의 자리바꿈 횟수 감소 목적 정렬이 안된 숫자들중에서 최소값을 선택하여 배열의 첫번째 요소와 교환

알고리즘 단계 첫 번째 항목을 기준으로 다른 항목과 비교 가장 작은 것과 기준 항목과 치환(교환) 0에 있는 막대와 1~9까지의 막대를 비교 가장 작은 막대를 0에 있는 막대와 치환

단계 기준 항목을 오른쪽으로 하나 이동 위치1에 있는 막대와 2~9까지의 막대를 비교 가장 작은 막대를 위치1에 있는 막대와 치환

선택 정렬 in C static int[] selectionSort (int[] arr) { int min;    for (int i=0; i<arr.length-1; i++) { // 항목 선택          min = i;          for(int j=i+1 ; j<arr.length; j++) {            if (arr[j] < arr[min])  {                min = j;       // 가장 작은 값을 변경            }        }        swap(arr, i, min);          displayArray(arr);        System.out.println();    }    return arr; }

10개의 자료에 대한 선택 정렬 결과 33, 11, 99, 1, 22, 88, 55, 44, 66, 77 *INPUT : 33 11 99 1 22 88 55 44 66 77 STEP 1 : 1 11 99 33 22 88 55 44 66 77 STEP 2 : 1 11 99 33 22 88 55 44 66 77 STEP 3 : 1 11 22 33 99 88 55 44 66 77 STEP 4 : 1 11 22 33 99 88 55 44 66 77 STEP 5 : 1 11 22 33 44 88 55 99 66 77 STEP 6 : 1 11 22 33 44 55 88 99 66 77 STEP 7 : 1 11 22 33 44 55 66 99 88 77 STEP 8 : 1 11 22 33 44 55 66 77 88 99 STEP 9 : 1 11 22 33 44 55 66 77 88 99

선택 정렬 분석 비교 횟수 자리바꿈 횟수 버블 정렬과 항목의 비교횟수는 동일 10개의 항목의 경우 비교회수는 N*(N-1)/2=45로 동일 자리바꿈 횟수 버블 정렬보다 작음 자리바꿈 횟수는 10회 이하

삽입(insertion) 정렬 특성 정렬되어 있는 부분에 새로운 레코드를 적절한 위치에 삽입하는 과정을 반복 세개의 기본 정렬 기법중에서 가장 큰 효율성 버블 정렬보다 2배, 선택 정렬보다 약간 빠름. 0 1 2 3 4 5 6 7 8 9

과정_1 위치 6의 막대보다 4, 5의 막대가 크므로 4, 5에 위치한 막대를 오른쪽으로 1칸 이동.

과정_2 위치6에 있던 막대를 위치4에 있던 막대의 왼쪽에 삽입(insert) 이러한 방법으로 나머지 막대도 적절한 위치에 삽입.

삽입 정렬 in C // 삽입정렬 void insertion_sort(int list[], int n) { int i, j, key; for(i=1; i<n; i++){ key = list[i]; for(j=i-1; j>=0 && list[j]>key; j--) list[j+1] = list[j]; list[j+1] = key; }

10개의 자료에 대한 삽입 정렬 결과 33, 11, 99, 1, 22, 88, 55, 44, 66, 77 *INPUT : 33 11 99 1 22 88 55 44 66 77 STEP 1 : 11 33 99 1 22 88 55 44 66 77 STEP 2 : 11 33 99 1 22 88 55 44 66 77 STEP 3 : 1 11 33 99 22 88 55 44 66 77 STEP 4 : 1 11 22 33 99 88 55 44 66 77 STEP 5 : 1 11 22 33 88 99 55 44 66 77 STEP 6 : 1 11 22 33 55 88 99 44 66 77 STEP 7 : 1 11 22 33 44 55 88 99 66 77 STEP 8 : 1 11 22 33 44 55 66 88 99 77 STEP 9 : 1 11 22 33 44 55 66 77 88 99

삽입 정렬 분석 최상의 경우: 이미 정렬되어 있는 경우 최악의 경우: 역순으로 정렬 모든 단계에서 앞에 놓인 자료 전부 이동 비교: n-1번 이동: 2(n-1)번 최악의 경우: 역순으로 정렬 모든 단계에서 앞에 놓인 자료 전부 이동

기본 정렬 비교 버블 정렬 선택 정렬 가장 간단함 비효율적 정렬대상이 적을 경우 사용하는 것이 바람직함 자리바꿈 횟수를 최소화 비교횟수는 여전히 많음 정렬할 대상이 적거나, 자리바꿈시간이 비교시간 보다 상대적으로 클 때 사용하는 것이 유용

삽입 정렬 정렬의 위해 필요한 메모리의 양 ? 정렬 알고리즘에 대한 수행속도를 비교 정렬 대상이 적은경우 부분적으로 정렬이 된 경우에 효율적 정렬의 위해 필요한 메모리의 양 ? 정렬 알고리즘에 대한 수행속도를 비교 http://cg.scs.carleton.ca/~morin/misc/sortalg/

쉘(shell) 정렬 특징 삽입 정렬의 단점을 극복하고 장점을 이용하여 만든 정렬 전체 N개라는 하나의 배열을 일정한 간격(interval)으로 나눔 작은 자료의 개수로 이루어진 하위 배열을 각각 삽입 정렬 더 좁은 간격으로 하위 배열로 나누고 최종적으로 전체 배열을 삽입 정렬

3가지 단계로 정리됨 N개의 항목으로 이루어진 하나의 배열을 일정한 간격으로 나눔 여러 개의 하위 배열로 구성. 여러 개의 하위 배열에 대해 각각 삽입 정렬 보다 작은 간격을 두어 여러 개의 하위 배열을 구성 위 단계 반복.

[22, 1, 11, 88, 55, 99, 77, 66, 44, 33] 간격 '4' 로 나눈 4개의 하위배열로 구분

4-sort 과정 [22, 1, 11, 66, 44, 33, 77, 88, 55, 99]로 변화

4-sort 과정 종료 '4'가 아닌 간격 '1'로 줄여 삽입 정렬 알고리즘 적용 간격 '1‘, 삽입 정렬과 동일한 의미

쉘 정렬 in C inc_insertion_sort(int list[], int first, int last, int gap){ int i, j, key; for(i=first+gap; i<=last; i=i+gap){ key = list[i]; for(j=i-gap; j>=first && key<list[j];j=j-gap) list[j+gap]=list[j]; list[j+gap]=key; } void shell_sort( int list[], int n ) { // n = size int i, gap; for( gap=n/2; gap>0; gap = gap/2 ) { if( (gap%2) == 0 ) gap++; for(i=0;i<gap;i++) // 부분 리스트의 개수는 gap inc_insertion_sort(list, i, n-1, gap);

항목이 더 많아진다면 간격 조정 ? 10개의 항목을 정렬하기 위해 처음에는 간격을 '4'로 사용 최적의 성능을 보일 수 있는 간격 크누스 방식(Knuth’s interval sequence) 개발자 스스로 좋은 아이디어가 있으면 적용

퀵(quick) 정렬 특징 C.A.R Hoare, 1962 정렬 알고리즘 중 가장 우수한 평균 수행 속도 분할 알고리즘(partition algorithm) 사용 2개의 그룹으로 분할 배열의 양끝 방향 즉, 왼쪽 끝에서 오른쪽으로 그리고 오른쪽 끝에서 왼쪽으로 탐색 각각 피봇 값보다 큰 값과 작은 값을 발견하면 그 값들을 서로 치환하는 방식

분할 알고리즘 정렬하고자 하는 배열을 2개의 하위 배열로 분할 각각의 하위 배열에서 다시 재귀적으로 자신의 배열을 분할 멀리 떨어진 자료를 직접적으로 치환함으로써 정렬의 수행속도를 개선

퀵 정렬 알고리즘 피봇(pivot) 배열을 2개의 하위 배열로 분할 왼쪽 하위 배열은 피봇 값 보다 작은 값으로 이루어진 배열 오른쪽 하위 배열은 피봇 값 보다 큰 값으로 이루어진 배열. 왼쪽 하위 배열에 퀵 정렬을 다시 실행 오른쪽 하위 배열에 퀵 정렬을 다시 실행 피봇(pivot) 하위 배열로 분할하는 특정 값.

퀵 정렬 과정 배열 [1, 11, 88, 55, 99, 77, 66, 44, 22, 33] 피봇 값을 가장 우측의 값인 33 왼쪽에서 오른쪽으로 피봇 값보다 큰 값을 탐색 오른쪽에서 왼쪽으로 피봇 값보다 작은 값을 탐색 찾은 값끼리 서로 치환 이 과정을 계속해서 진행하되 서로의 자리 값이 엇갈리면 피봇 값과 왼쪽에서 찾은 값을 서로 바꿈

2개의 하위 배열로 분할된 상태 피봇 값 선정 다시 퀵 정렬 재귀적 적용 피봇 값을 배열의 가장 오른쪽에 위치한 값으로 선택 퀵 정렬에서는 피봇 값을 선정하는 작업이 아주 중요.

피봇 값 선정 방식 중간 값(median of three) 선택 방식 배열의 첫 번째 왼쪽 값, 중간 값 그리고 마지막 오른쪽 값을 정렬해서 중간 값을 피봇으로 사용

퀵 정렬 in C void quick_sort(int list[], int left, int right) { if(left<right){ int q=partition(list, left, right); quick_sort(list, left, q-1); quick_sort(list, q+1, right); }

특징 정렬할 범위가 2개 이상의 데이터이면 partition 함수를 호출하여 피벗을 기준으로 2개의 리스트로 분할 정렬할 범위가 2개 이상의 데이터이면  partition 함수를 호출하여 피벗을 기준으로 2개의 리스트로 분할 partition 함수의 반환 값은 피봇의 위치 left에서 피봇 위치 바로 앞까지를 대상으로 순환 호출(피봇은 제외). 피봇 위치 바로 다음부터 right까지를 대상으로 순환 호출(피봇은 제외).

분할 함수 피봇(pivot) 두개의 변수 가장 왼쪽 숫자라고 가정 low와 high를 사용 정지된 위치의 숫자를 교환 low와 high가 교차하면 종료

int partition(int list[], int left, int right) { int pivot, temp; int low,high; low = left; high = right+1; pivot = list[left]; do { do low++; while(low<=right && list[low]<pivot); high--; while(high>=left && list[high]>pivot); if(low<high) SWAP(list[low], list[high], temp); } while(low<high); SWAP(list[left], list[high], temp); return high; }

퀵 정렬 분석 퀵 정렬 알고리즘 분할 알고리즘을 기본으로 하는 방식 분할 알고리즘의 시간 복잡도는 O(N) 각각의 하위 배열은 처음에 2개, 그 다음 4, 8, 16, … 퀵 정렬을 재귀적 실행을 위한 시간 복잡도 O(N * logN)

최악의 경우 불균등한 리스트로 분할되는 경우 패스 수: n 각 패스안에서의 비교횟수: n 총비교횟수: n2 총이동횟수: 비교횟수에 비하여 무시가능

최선의 경우 거의 균등한 리스트로 분할되는 경우 패스 수: log2n 각 패스안에서의 비교횟수: n 총비교횟수: n log2n 총이동횟수: 비교횟수에 비하여 무시가능

기수(radix) 정렬 특성 정렬할 대상에 대한 기본적인 가정을 가지고 출발 음수가 아닌 숫자(digit)로 이루어져 있을 때만 기수 정렬 알고리즘이 사용 가능 각각의 항목을 여러 자리로 나누어 각각의 자리에서의 숫자를 정렬 자료 항목 간 비교하는 단계는 존재하지 않음

알고리즘 3개의 숫자로 이루어진 자료가 5개 있다고 할 때 이를 정렬하기 위해서 기수 정렬 규칙. 각각의 자료를 3개의 자리수로 나눈다. 1 단위 자리에서 각각의 자료의 숫자를 확인해 재배열. 10 단위 자리에서 각각의 자료의 숫자를 확인해 재배열, 1 단위 자리에서 재배열한 상태를 유지한 채 10 단위 재배열을 한다. 100 단위 자리에서 각각의 자료의 숫자를 확인해 재배열 하면 기수 정렬이 완성.

한자리수의 기수 정렬 (8, 2, 7, 3, 5)

두자리수의 기수 정렬 (28, 93, 39, 81, 62, 72, 38, 26)

문제점 복잡도 배열의 전체 크기와 동일한 크기의 기수 테이블을 위한 메모리가 필요 음수, 부동소수점처럼 특수한 비교 연산이 필요한 자료에는 적용 불가능 복잡도 복사 횟수는 자료 항목의 개수와 비례 O(N)