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

Slides:



Advertisements
Similar presentations
6 장. printf 와 scanf 함수에 대한 고찰 printf 함수 이야기 printf 는 문자열을 출력하는 함수이다. – 예제 printf1.c 참조 printf 는 특수 문자 출력이 가능하다. 특수 문자의 미 \a 경고음 소리 발생 \b 백스페이스 (backspace)
Advertisements

1 08 배열. 한국대학교 객체지향연구소 2 C 로 배우는 프로그래밍 기초 2 nd Edition 배열  동일한 자료유형의 여러 변수를 일괄 선언  연속적인 항목들이 동일한 크기로 메모리에 저장되는 구조  동일한 자료 유형이 여러 개 필요한 경우에 이용할 수 있는.
1. 2 차원 배열  배열은 동일한 데이터 유형으로 여러 개의 변수를 사용할 경우 같은 이 름으로 지정하여 간편하게 사용할 수 있도록 하는 것으로서 앞에서 1 차원 배열을 공부하였습니다.  2 차원 배열은 바둑판을 생각하면 되며, 1 차원 배열에서 사용하는 첨자를 2.
알고리즘 기본 개념 정렬 알고리즘 탐색 알고리즘 알고리즘 복잡도.
Report #5 - due: 4/13 다음 10*5의 희소 행렬 A, B를 고려하라.
연결리스트(linked list).
Report #2 - Solution 문제 #1: 다음과 같이 프로그램을 작성하라.
컴퓨터 프로그래밍 기초 [Final] 기말고사
보고서 #7 (기한: 6/2) 2개의 스택, stk1, stk2를 이용하여 큐를 구현하라.
5장 배열 작성자 : 변재현.
누구나 즐기는 C언어 콘서트 제8장 배열.
정보보안 프로젝트 (Sort Algorithm) 학 부 : 컴퓨터 정보공학부, 네트워크 정보 공학부
자료구조론 11장 정렬(sort).
Chapter 02 순환 (Recursion).
빠른정렬(Quick Sort) – 개요 (1/2)
11장. 포인터 01_ 포인터의 기본 02_ 포인터와 Const.
쉽게 풀어쓴 C언어 Express 제10장 배열 C Express Slide 1 (of 32)
쉽게 풀어쓴 C언어 Express 제10장 배열 C Express.
제8장 배열 1부 8.1 배열 8.2 배열의 초기화 8.3 배열의 응용 8.4 정렬과 탐색 8.5 다차원 배열.
6장. printf와 scanf 함수에 대한 고찰
보고서 #5(제출기한: 10/14) 다음 문제를 해결하시오.
자료구조: CHAP 4 리스트 (3) 순천향대학교 컴퓨터공학과 하 상 호.
PySpark Review 박영택.
11장. 1차원 배열.
CHAP 9: 정렬 (part 2) 순천향대학교 컴퓨터학부 하 상 호.
CHAP 9:정렬 C로 쉽게 풀어쓴 자료구조 Slide 1 (of 44).
제 8 장 정렬.
11 정렬.
프로그래밍 개요
박성진 컴퓨터 프로그래밍 기초 [09] 배열 part 1 박성진
CHAP 9: 정렬 순천향대학교 컴퓨터학부 하 상 호.
자료구조: CHAP 7 트리 –review 순천향대학교 컴퓨터공학과 하 상 호.
Report #3 - due: 4/6 100*100의 2개의 희소 행렬 A, B를 전달 받아서 이들의 덧셈을 구하고, 그 결과의 행렬 C를 반환하는 add_sparse_matrix(A, B, C)를 다음과 같이 작성하라. 희소 행렬은 sparse_matrix 타입으로 표현된다.
Java의 정석 제 5 장 배 열 Java 정석 남궁성 강의 의
Quiz #7 다음 수들을 합병 정렬과 퀵 정렬 알고리즘을 이용하여 오름 차순으로 정렬하였을 때, 데이터 이동 회수를 각각 구하라. 여러분은 정렬 과정을 단계별로 보이면서 이동 회수를 추적해야 한다. 단, 퀵 정렬시에 피봇으로 배열의 왼쪽 첫 번째 원소를 선택한다. 5.
컴퓨터 프로그래밍 기초 - 10th : 포인터 및 구조체 -
2장. 변수와 타입.
컴퓨터 프로그래밍 기초 - 8th : 함수와 변수 / 배열 -
메모리 타입 분석을 통한 안전하고 효율적인 메모리 재사용
5강. 배열 배열이란? 배열의 문법 변수와 같이 이해하는 배열의 메모리 구조의 이해 레퍼런스의 이해 다차원 배열
보고서 #7 (기한: 6/2) 2개의 스택, stk1, stk2를 이용하여 큐를 구현하라.
CHAP 12: 탐색 순천향대학교 컴퓨터학부 하 상 호.
CHAP 12: 탐색 순천향대학교 컴퓨터학부 하 상 호.
CHAP 21. 전화, SMS, 주소록.
Canary value 스택 가드(Stack Guard).
균형이진탐색트리 이진 탐색(binary search)과 이진 탐색 트리(binary search tree)와의 차이점
알고리즘 알고리즘이란 무엇인가?.
데이터 동적 할당 Collection class.
알고리즘: 우선순위 큐(8장) 순천향대학교 컴퓨터 학부 하 상 호.
단축키 기능 1. 단축키 기능 설명 Alt + R 조회 S 저장 I 삽입 A 추가 D 삭제 P 출력 Q 닫기
자료구조론 12장 검색(search).
4장. 데이터 표현 방식의 이해. 4장. 데이터 표현 방식의 이해 4-1 컴퓨터의 데이터 표현 진법에 대한 이해 n 진수 표현 방식 : n개의 문자를 이용해서 데이터를 표현 그림 4-1.
DA :: 퀵 정렬 Quick Sort 퀵 정렬은 비교방식의 정렬 중 가장 빠른 정렬방법이다.
5장. 선택 알고리즘.
빠른정렬(Quick Sort) – 개요 (1/2)
Chapter 10 데이터 검색1.
세션에 대해 알아보고 HttpSession 에 대해 이해한다 세션 관리에 사용되는 요소들을 살펴본다
11장 배열 1. 배열이란? 1.1 배열의 개요 1.2 배열의 선언과 사용.
컴퓨팅 사고력을 키우는 SW 교육 : 스크래치 [강의교안 이용 안내] 본 강의교안의 저작권은 저자인 고광일과 한빛아카데미㈜에 있습니다. 이 자료는 강의 보조자료로 제공되는 것으로 무단으로 전제하거나 배포하는 것을 금합니다.
컴퓨터 프로그래밍 기초 - 9th : 배열 / 포인터 -
7장 연습 문제 풀이 학번 : 이름 :조 재한.
트리 (Logical) Data Structures Linear list Tree Graph Linear structures
제 4 장 Record.
2014년 가을학기 손시운 지도 교수: 문양세 교수님 행렬과 배열 2014년 가을학기 손시운 지도 교수: 문양세 교수님.
개정판 누구나 즐기는 C언어 콘서트 제7장 배열 출처: pixabay.
빠른정렬(Quick Sort) – 개요 (1/2)
                              데이터베이스 설계 및 실습 #6 - SQL 실습 한국외국어대학교 DaPS 연구실                              
(Permutations and Combinations)
C++ Espresso 제15장 STL 알고리즘.
6 객체.
Presentation transcript:

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) 비교 회수 이동 회수