반응형 정렬 알고리즘8 합병 정렬(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. 버블 정렬(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. heap 정렬 u 히프(heap)를 이용해 정렬 ･ 히프 : 우선순위 큐의 일종 Ø 정렬할 원소를 모두 공백 히프에 하나씩 삽입 Ø 한 원소씩 삭제 →제일 큰 원소가 삭제됨 Ø 이 원소를 리스트의 뒤에서부터 차례로 삽입 Ø 오름차순으로 정렬된 리스트를 생성 HeapSort(a[]) n ← a.length - 1; // n은 히프 크기(원소의 수) // a[0]은 사용하지 않고 a[1 : n]의 원소를 오름차순으로 정렬 for (i ← n/2; i ≥ 1; i ← i-1) do // 배열 a[]를 히프로 변환 heapify(a, i, n); // i는 내부 노드 for (i ← n-1; i ≥ 1; i ← i-1) do { // 배열 a[]를 오름차순으로 정렬 temp ← a[1]; // a[1]은 제일 큰 원소 a[1.. 2007. 3. 13. 선택 정렬 (Selection Sort) a[] = ( 3, 2, 5, 1, 4 ) void Selectionsort::sorting() { int i, j, min; for(i=1;i 2007. 2. 28. 이전 1 2 다음 반응형
