반응형 [알고리즘 + 자료구조]43 [알고리즘] 병합 정렬(Merge Sort) 배열을 앞부분과 뒷부분으로 나누어 각각 정렬(병합정렬 재귀)한 다음 병합하는 작업을 반복하여 정렬을 수행하는 알고리즘. 코드 1 (배열공유 X) // 내가 만든 merge_sort void merge_sort(int a[], int n, int c[]) { int mid = (n - 1) / 2; if(n >= 2) { merge_sort(a, mid + 1, c); merge_sort(a + mid + 1, n -(mid + 1), c); int pa = 0, pb = mid + 1, pc = 0; while(pa 2020. 11. 27. [알고리즘] 퀵 정렬(Quick Sort) 퀵 정렬은 가장 빠른 정렬 알고리즘 중 하나로 널리 사용되고 있다. 먼저 전체에서 데이터값 하나(A)를 선택한다. 그리고 A를 기준으로 A보다 큰 그룹과 작은 그룹으로 나눈다. 이때 A(그룹을 나누는 기준)를 피벗(pivot)이라고 한다. 퀵 정렬은 각 그룹에 대해 피벗 설정과 그룹 나눔을 반복하며 모든 그룹이 1명이 되면 정렬을 마친다. ps. 피벗은 마음대로 선택할 수 있고, 피벗은 왼쪽 그룹과 오른쪽 그룹 어디에 들어가도 상관없다. 코드 // 퀵 정렬 함수 void quick (int a[], int left, int right) { int pl = left; // 왼쪽 커서 int pr = right; // 오른쪽 커서 int x = a[(pl + pr) / 2]; // 피벗은 가운데 요소로 선택.. 2020. 11. 27. [알고리즘] 셸 정렬 (Shell Sort) 단순 삽입 정렬의 장점(a)은 살리고 단점(b)은 보완한 정렬 알고리즘. 퀵 정렬이 고안되기 전까지는 가장 빠른 알고리즘으로 알려져 있었다. a: 정렬을 마쳤거나 정렬을 마친 상태에 가까우면 정렬 속도가 매우 빨라진다. b: 삽입할 위치가 멀리 떨어져 있으면 이동(대입)해야 하는 횟수가 많아진다. 정렬할 배열의 요소를 그룹으로 나눠 각 그룹별로 단순 삽입 정렬을 수행하고, 그 그룹을 합치면서 정렬을 반복하여 요소의 이동 횟수를 줄이는 방법이다. 코드 // 셸 정렬 함수 void shell(int a[], int n) { int i, j, h; for(h = n/2; h > 0; h/=2) { for(i = h; i =0 &&.. 2020. 11. 27. [알고리즘] Do it 자료구조와 알고리즘 6장 정리 2/2 Q_19, Q_20 나중에 다시보기 연습문제 Q_12 > 요소의 이동 횟수를 계산할 수 있도록 버전 1과 버전 2를 수정한 프로그램을 작성하세요. 여러 가지 배열을 입력하고 프로그램을 실행하며 이동 횟수를 비교해 보세요. 버전 1 #include #include // 셸 정렬 함수 void shell(int a[], int n) { int i, j, h, count=0; for(h = n/2; h > 0; h/=2) { for(i = h; i =0 && a[j] > tmp; j-=h) { a[j + h] = a[j]; count++; } a[j + h] = tmp; // a[j]가 아닌 a[j + h]인 이유는, 종료 전에 .. 2020. 11. 27. 이전 1 2 3 4 5 6 7 8 ··· 11 다음 반응형