Download presentation
Presentation is loading. Please wait.
1
정보보안 프로젝트 (Sort Algorithm) 학 부 : 컴퓨터 정보공학부, 네트워크 정보 공학부
학 과 : 컴퓨터 전공, 인터넷 정보전공 이 름 : 김명수( ), 김명주 ( ) 날 짜 : (목요일)
2
Contents Algorithm Definition Sort Algorithm Description
Insert sort - Advantage and weak point / Source Bubble sort Select sort Quick sort Conclusion
3
Sort Algorithm Sort algorithm(정렬 알고리즘) 정 의
정 의 - 기억 장소에 저장된 자료를 키(Key)값에 따라서 오름차순(Ascending), 내림차순(Descending)으로 순서 배열하는 것 정렬 알고리즘 선택에 미치는 요인 - 컴퓨터 시스템의 특성 - 정렬할 자료의 량 자료의 초기 배열 상태 키 비교 횟수 및 자료 교환 횟수 정렬할 기억 공간의 크기
4
BUBBLE SORT BUBBLE SORT(버블정렬)
정 의 : 주어진 파일에서 서로 인접한 레코드 두 키갑을 비교하여 그 크기에 따라 레코드의 위치를 서로 교환함 장 점 - 알고리즘이 간단하고 플래그를 사용하면 효율적인 수행이 가능 ※플래그 : 이미 정렬된 상태를 파악하기 위해 레코드 위치 교환의 발생여부를 나타내는 것 - 양이 작은 데이터를 정렬할 때는 빠르며, 사람이 구현하기가 비교적 쉽다 단 점 - 큰 배열을 정렬할 때 쓰기에는 너무 계산량이 많다
5
BUBBLE SORT Bubble sort description 20 8 52 35 23 69 42 8 20 52 35
가장 큰 수가 맨 마지막에 정렬되며 다시 앞과정을 마지막 정렬 과정을 제외 하고 반복하여 정렬 8 20 35 23 52 69 42 8 20 35 23 52 69 42 8 20 35 23 52 42 69 8 20 35 23 52 42 69
6
BUBBLE SORT Bubble sort source
double bubble_sort(int arrayB[], int max){ double start, end; double total; int i=0; int j=max-1; int temp=0; //임시 저장 장소 start = clock(); //마지막에서 부터 내려간다. for(j;j>0;j--){//i부터 j까지 루프 반복 for(i=0;i<j;i++){ //arrayB[i] > arrayB[i+1] 비교 if(arrayB[i] > arrayB[i+1]){ // 배렬 위치 교환 temp = arrayB[i]; arrayB[i] = arrayB[i+1]; arrayB[i+1] = temp; } end = clock(); total=((double)(end-start)/CLOCKS_PER_SEC); cout << "버블 소팅 시간 : "<< total << "초" << endl; return total;
7
BUBBLE SORT Bubble sort time check
8
INSERT SORT INSERT SORT(삽입정렬)
정 의 : 한 개의 데이터부터 시작해서 차례로 삽입하고, 다음코드가 삽입될 때 마다 이미 들어 있는 데이터와 비교하여 만족하지 못하면 뒤로 이동 후 삽입하는 정렬 방법이다 장 점 - 인플레이스 정렬(내부정렬)이라는 장점이 있습니다. 즉, 삽입정렬의 최상의 성능으로 작은 자료집합에 대한 오름차순 정렬이라는 특징입니다. - 양이 작은 데이터를 정렬할 때는 버블정렬보다는 조금 빠르며, 사람이 구현하기가 비교적 쉽다 단 점 - 퀵 정렬에 비해 느리면서 뚜렷한 장점이 없다.
9
INSERT SORT Insert sort description 39 21 2 5 15 42 21 39 2 5 15 42
10
INSERT SORT Insert sort source
double insert_sort (int arrayI[], int max){ double start, end; double total; int i, j, k; //i, j, k 선언 start = clock(); for (i=1; i<max; i++) { //i번째 값을 k에 저장 k = arrayI[i]; for (j=i-1; j>=0 && k<arrayI[j]; j--) arrayI[j+1] = arrayI[j]; // k값을 arrayI[j+1] 저장 arrayI[j+1] = k; } end = clock(); total=((double)(end-start)/CLOCKS_PER_SEC); cout << "삽입 소팅 시간 : "<< total << "초" << endl; return total;
11
INSERT SORT Insert sort time check
12
SELECTION SORT SELECTION SORT(선택정렬)
정 의 : 첫 번째 데이터와 나머지 모든 데이터를 비교하여 위치 교환을 한 후, 다시 두 번째 데이터와 나머지 모든 데이터를 비교하여 위치 교환을 반복하는 방법 장 점 - 버블 정렬 보다 레코드 교환 횟수가 적다 - 큰 레코드와 작은키를 갖는 데이터 정렬에 적합 단 점 - 다중키 정렬시 이전의 정렬 내용이 유지되지 않아 안정성이 없음
13
SELECTION SORT Select sort description 23 11 55 38 25 85 48 11 23 55
14
SELECTION SORT Selection sort source
double select_sort(int arrayS[], int max){ double start, end; double total; int i=0,j=0; int tempL=0; //작은값의 위치 int temp=0; start = clock(); for(j=0;j<max;j++){ // 시작 값과 위치를 temp에 저장 tempL = j; for(i=j+1;i<max;i++){ // 작은 값을 찾는 if문 if(arrayS[tempL] > arrayS[i]){ tempL = i; } temp = arrayS[tempL]; // 작은 값은 차례대로 저장 arrayS[tempL] = arrayS[j]; arrayS[j] = temp; end = clock(); total=((double)(end-start)/CLOCKS_PER_SEC); cout << "선택 정렬 시간 : "<< total << "초" <<endl; return total;
15
SELECTION SORT Selection sort time check
16
QUICK SORT QUICK SORT(퀵정렬) 정 의 : 제어키를 이용하는 정렬 방법으로 제어키를 중심으로 제어키보다
큰 데이터는 제어키의 오른쪽에, 제어키보다 작은 데이터는 제어키의 왼쪽으로 이동하는 방법 장 점 - 정렬 방법 중 가장 빠른 방법 단 점 - 제어키가 중간값이 아니거나 데이터들이 이미 정렬된 경우 수행 속도가 대단히 느려진다
17
QUICK SORT Quick sort description 17 11 45 38 12 26 17 11 45 12 38
18
QUICK SORT Quick sort source
void quick_sort(int a[], int left, int right){ int i, j, k, temp; /*k는 기준키*/ if (left < right) { i = left; j = right + 1; k = a[left]; do { do i++; while (a[i] < k); do j--; while (a[j] > k); if (i < j) { temp = a[i]; a[i] = a[j]; a[j] = temp; } } while (i < j); /*i과j가 엇갈린 부분에서 기준키와 작은 값(a[j])을 교환*/ temp = a[left]; a[left] = a[j]; a[j] = temp; /*좌측 리스트에 대해 재귀호출*/ quick_sort (a, left, j-1); /*우측 리스트에 대해 재귀호출*/ quick_sort (a, j+1, right);
19
QUICK SORT Quick sort time check
20
ALL SORT TIME CHECK All sort time check
21
CONCLUSION 내부정렬 알고리즘 비교 ※어떤 문제 해결에 대한 방법에는 많은 알고리즘이 있다. 이 알고리즘을
종 류 방 식 시간 복잡도 평균복잡도 최악의 경우 복잡도 Selection sort 교 환 O(n ) Bubble sort Insert sort 삽 입 Quick sort O(nlog n) 2 2 2 2 2 2 2 ※어떤 문제 해결에 대한 방법에는 많은 알고리즘이 있다. 이 알고리즘을 좋고 나쁨을 평가하는 척도로 복잡도라는 개념을 사용하며 표기법으로는 O표기법을 사용한다. 알고리즘의 기본이 되는 정렬 알고리즘에는 삽입정렬, 버블정럴, 퀵정렬등 다양한 알고리즘이 있으며 이 알고리즘은 각각의 경우에 따라 최상의 알고리즘이 될 수도 있고 최악의 알고리즘이 될 수 도 있다. 따라서 상황에 맞는 알고리즘을 선택해야 한다.
Similar presentations