정보보안 프로젝트 (Sort Algorithm) 학 부 : 컴퓨터 정보공학부, 네트워크 정보 공학부 학 과 : 컴퓨터 전공, 인터넷 정보전공 이 름 : 김명수(98211013), 김명주 (99701126) 날 짜 : 2004. 4. 29(목요일)

Contents  Algorithm Definition  Sort Algorithm Description  Insert sort - Advantage and weak point / Source  Bubble sort  Select sort  Quick sort  Conclusion

Sort Algorithm  Sort algorithm(정렬 알고리즘)  정 의  정 의 - 기억 장소에 저장된 자료를 키(Key)값에 따라서 오름차순(Ascending), 내림차순(Descending)으로 순서 배열하는 것  정렬 알고리즘 선택에 미치는 요인 - 컴퓨터 시스템의 특성 - 정렬할 자료의 량 - 자료의 초기 배열 상태 - 키 비교 횟수 및 자료 교환 횟수 - 정렬할 기억 공간의 크기

BUBBLE SORT  BUBBLE SORT(버블정렬)  정 의 : 주어진 파일에서 서로 인접한 레코드 두 키갑을 비교하여 그 크기에 따라 레코드의 위치를 서로 교환함  장 점 - 알고리즘이 간단하고 플래그를 사용하면 효율적인 수행이 가능 ※플래그 : 이미 정렬된 상태를 파악하기 위해 레코드 위치 교환의                               발생여부를 나타내는 것 - 양이 작은 데이터를 정렬할 때는 빠르며, 사람이 구현하기가 비교적 쉽다  단 점 - 큰 배열을 정렬할 때 쓰기에는 너무 계산량이 많다

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

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;

BUBBLE SORT  Bubble sort time check

INSERT SORT  INSERT SORT(삽입정렬)  정 의 : 한 개의 데이터부터 시작해서 차례로 삽입하고, 다음코드가 삽입될 때 마다 이미 들어 있는 데이터와 비교하여 만족하지 못하면 뒤로 이동 후 삽입하는 정렬 방법이다  장 점 - 인플레이스 정렬(내부정렬)이라는 장점이 있습니다. 즉, 삽입정렬의 최상의 성능으로 작은 자료집합에 대한 오름차순 정렬이라는 특징입니다. - 양이 작은 데이터를 정렬할 때는 버블정렬보다는 조금 빠르며, 사람이 구현하기가 비교적 쉽다  단 점 - 퀵 정렬에 비해 느리면서 뚜렷한 장점이 없다.

INSERT SORT  Insert sort description 39 21 2 5 15 42 21 39 2 5 15 42

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;

INSERT SORT  Insert sort time check

SELECTION SORT  SELECTION SORT(선택정렬)  정 의 : 첫 번째 데이터와 나머지 모든 데이터를 비교하여 위치 교환을 한 후, 다시 두 번째 데이터와 나머지 모든 데이터를 비교하여 위치 교환을 반복하는 방법  장 점 - 버블 정렬 보다 레코드 교환 횟수가 적다 - 큰 레코드와 작은키를 갖는 데이터 정렬에 적합  단 점 - 다중키 정렬시 이전의 정렬 내용이 유지되지 않아 안정성이 없음

SELECTION SORT  Select sort description 23 11 55 38 25 85 48 11 23 55

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;

SELECTION SORT  Selection sort time check

QUICK SORT  QUICK SORT(퀵정렬)  정 의 : 제어키를 이용하는 정렬 방법으로 제어키를 중심으로 제어키보다 큰 데이터는 제어키의 오른쪽에, 제어키보다 작은 데이터는 제어키의 왼쪽으로 이동하는 방법  장 점 - 정렬 방법 중 가장 빠른 방법  단 점 - 제어키가 중간값이 아니거나 데이터들이 이미 정렬된 경우 수행 속도가 대단히 느려진다

QUICK SORT  Quick sort description 17 11 45 38 12 26 17 11 45 12 38

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);

QUICK SORT  Quick sort time check

ALL SORT TIME CHECK  All sort time check

CONCLUSION  내부정렬 알고리즘 비교 ※어떤 문제 해결에 대한 방법에는 많은 알고리즘이 있다. 이 알고리즘을 종 류 방 식 시간 복잡도 평균복잡도 최악의 경우 복잡도 Selection sort 교 환 O(n ) Bubble sort Insert sort 삽 입 Quick sort O(nlog n) 2 2 2 2 2 2 2 ※어떤 문제 해결에 대한 방법에는 많은 알고리즘이 있다. 이 알고리즘을 좋고 나쁨을 평가하는 척도로 복잡도라는 개념을 사용하며 표기법으로는 O표기법을 사용한다. 알고리즘의 기본이 되는 정렬 알고리즘에는 삽입정렬, 버블정럴, 퀵정렬등 다양한 알고리즘이 있으며 이 알고리즘은 각각의 경우에 따라 최상의 알고리즘이 될 수도 있고 최악의 알고리즘이 될 수 도 있다. 따라서 상황에 맞는 알고리즘을 선택해야 한다.