본문 바로가기
반응형

프로그래머의 길157

쉘 정렬(Shell sort) u 삽입 정렬을 간단하게 변형 u 멀리 떨어진 원소끼리 교환이 가능하게 하여 정렬 속도를 향상시킴 u h-정렬 화일 : 모든 h번째 원소를 정렬한 화일 u 증가 순서의 예 : …, 1093, 364, 121, 40, 13, 4, 1 u 특징 Ø 순열 h가 1, 4, 13, 40, … 일 때, 쉘 정렬의 비교회수는 N 3/2 을 넘지 않음 Ø 안정적인 제자리 정렬 ShellSort(a[], n) for (h ← 1; h 0; h ← h/3) do { // h 값을 감소시키며 진행 for (i ← h + 1; i ≤ n; i ← i+1) do { v ← a[i]; j ← i; while (j >h and a[j-h] >v) do { a[j] ← a[j-h]; j ← j-h; } // while A[j] ← .. 2007. 4. 3.
삽입 정렬(Insertion Sort) ■ 삽입 정렬 개념 • 삽입정렬은 매우 간단한 정렬 방법으로 소량의 자료를 처리하는데 유용 • 파일을 구성하고 있는 부파일(subfile)의 레코드들이 이미 정렬이 되어 있다고 가정 • 한 번에 한 개의 새로운 레코드를 입력하여 정렬되어 있는 사이트의 적당한 위치를 찾아서 레코드를 삽입 • 따라서 새롭게 삽입된 레코드를 포함하여 파일은 항상 정렬된 상태를 유지 ■ 삽입 정렬 과정 ① 두 번째 키를 기준으로 하여 첫 번째 키를 비교하여 키 값에 따라 순서대로 나열 ② 세 번째 키를 기준으로 하여 두 번째 키와 첫 번째 키를 비교하여 키 값에 따라 순서대로 나열 ③ 계속하여 n번째 키를 앞의 n-1개의 키와 비교하여 삽입될 적당한 위치를 찾아 삽입한다. 30 15 20 17 40 ------> 초기상태 30.. 2007. 4. 3.
합병 정렬(Merge Sort) 구현 #include #include #include void merge(int, int, int *, int *, int *); void mergesort(int n, int *); void multiplication(); void mergesort(int n, int *S) { int h = n/2; int m = n-h; int *U = (int *)malloc(h*sizeof(int)); int *V = (int *)malloc(m*sizeof(int)); if(n>1) { int i; for(i=0; i 2007. 4. 2.
합병 정렬(Merge Sort) u 두 개의 정렬된 화일을 하나의 큰 정렬된 화일로 합병함 u 합병 정렬은 퀵 정렬과 마찬가지로 분할 정복 방식의 알고리즘임 u 두 부분배열의 크기가 동일하도록 분할함 u 최악의 경우에도 N 개의 원소를 가진 화일을 정렬하는 N logN 에 비례하는 시간이 소요됨 u 순차적 방식에 의해 데이터를 접근함 u 연결 리스트와 같이 순차 접근이 유일한 접근 방법일 경우 사용 가능 u N 에 비례하는 추가 기억장소가 필요함 u 안정적이지만 제자리 정렬은 아님 MergeSort(a[], l, r) if (r > l) then { m ← (r+l)/2; MergeSort(a[], l, m); MergeSort(a[], m+1, r); Merge(a[], l, m, r); } end MergeSort() Merge(a.. 2007. 4. 2.
버블 정렬 구현 #include #define MAX 100 void zigzag(int *,int, int *, int *); void main() { int table[MAX], num, rep_no, exchg_no,i; rep_no = exchg_no=0; printf("Input Data Number : "); scanf("%d", &num); printf("\n Input Data \n"); for(i=0;i 2007. 4. 2.
버블 정렬(Bubble Sort) 2. 버블정렬 Bubble Sort는 가장 기본적이고 초보적인 Sorting 방법으로써, 서로 인접한 데이터들을 뒤에서부터 자리바꿈하면서 정렬하는 방법이다. (Selection Sort는 앞에서부터 정렬한다.) 효율성은 떨어지나, 구현이 간단하여 속도가 별로 중요하지 않은 경우에 널리 쓰이는 방법이다. 입력자료 : 4 7 3 1 5 8 2 6 1. 4와7을 비교한다. 7이 더 크므로 변화 없다. --> 4 7 3 1 5 8 2 6 ↑ ↑ 2. 7과 3을 비교한다. 3이 더 작으므로 바꾼다. --> 4 7 3 1 5 8 2 6 ↑ ↑ 3. 7과 1을 비교한다. 1이 더 작으므로 바꾼다. --> 4 3 7 1 5 8 2 6 ↑ ↑ 4. 7과 5를 비교한다. 5가 더 작으므로 바꾼다. --> 4 3 1 7 5.. 2007. 4. 2.
반응형

티스토리툴바