키리Kirri's IT노트

힙이란? 힙(heap)을 사용해 정렬하는 알고리즘 힙은 '부모의 값이 자식보다 항상 크다'는 조건을 만족하는 완전이진트리 부모의 값이 자식보다 항상 작아도 힙이라고 함(부모와 자식 요소의 관계만 일정하면 됨) 완전이진트리 → 힙 힙은 루트가 가장 큰(혹은 작은) 값이어야 함 즉, 모든 부모와 자식의 관계는 항상 부모의 값 >= 자식의 값이 성립되어야 함 힙에서 부모와 자식 관계는 일정하지만 형제 사이의 대소 관계는 일정하지 않음 힙의 요소를 배열에 저장 부모와 자식의 인덱스 사이에는 다음과 같은 관계 성립 1. 부모는 a[(i - 1) / 2] 2. 왼쪽 자식은 a[i * 2 + 1] 3. 오른쪽 자식은 a[i * 2 + 2] 힙 정렬 '가장 큰 값이 루트에 위치'하는 특징을 이용하는 정렬 알고리즘 힙에..

정렬을 마친 배열의 병합 : 정렬을 마친 각 배열에서 선택한 요소의 값을 비교해 작은 값의 요소를 꺼내 새로운 배열에 넣는 작업을 반복하여 정렬 [그림] 배열 a와 b를 앞에서부터 차례로 비교하여 작은 값을 꺼내 비에 넣음 [실습 코드] 1 2 3 4 5 6 7 8 9 10 11 12 13 14 static void merge(int[] a, int na, int[] b, int nb, int[] c) { int pa = 0; int pb = 0; int pc = 0; while(pa

퀵 정렬 살펴보기 가장 빠른 정렬 알고리즘 중 하나 피벗 설정과 그룹 나눔을 반복해 모든 그룹의 요소가 한 개가 되면 정렬을 마침 피벗은 마음대로 선택 가능, 양쪽 그룹 어느 곳에 포함시켜도 상관 없음 배열을 두 그룹으로 나누기 피벗: x 왼쪽 커서: pl 오른쪽 커서: pr ※ 피벗 이하의 요소를 배열 왼쪽으로, 이상의 요소를 배열 오른쪽으로 옮기기 위해 수행해야 할 작업 1. a[pl] >= x가 성립하는 요소를 찾을 때까지 pl을 오른쪽으로 스캔 2. a[pr] pr + 1인 경우에는 다음과 같은 그룹이 생길 수 있음 피버새과 일치하는 값을 가지는 그룹: a[pr + 1], ..., a[pl - 1] [실습 코드] 1 2 3 4 5 6 7 do { while(a[pl] x) pr--; if(pl

단순 삽입 정렬의 특징 a. 정렬을 마쳤거나 정렬을 마친 상태에 가까우면 정렬 속도가 매우 빨라진다(장점) b. 삽입할 위치가 멀리 떨어져 있으면 이동(대입)해야 하는 횟수가 많아진다(단점) 셸 정렬은 이러한 단순 삽입 정렬의 장점을 살리고 단점은 보완한 알고리즘이다. 셸 정렬 : 단순 삽입 정렬의 장점(a)은 살리고 단점(b)은 보완한 정렬 알고리즘으로, 도널드 셸(D. L. Shell)이 고안 먼저, 정렬할 배열의 요소를 그룹으로 나눠 각 그룹 별로 단순 삽입 정렬을 수행 각 그룹을 합치면서 정렬을 반복해 요소의 이동 횟수를 줄임 [예시] 먼저, 배열을 ※4개의 그룹으로 나누고 각 그룹별로 정렬 (4-정렬) ※4칸씩 떨어져있는 요소들로 묶음({8, 7}, {1, 6}, {4, 3}, {2, 5}) 4..

단순 삽입 정렬 선택한 요소를 그보다 더 앞쪽의 알맞은 위치에 '삽입하는' 작업을 반복해 정렬하는 알고리즘 단순 선택 정렬과 비슷하지만, 단순 선택 정렬은 값이 가장 작은 요소를 선택해 알맞은 위치로 옮긴다는 점이 다름 셔틀 정렬(shuttle sort)이라고도 함 2번째 요소부터 선택해 진행 4는 6보다 작으므로 6보다 앞쪽에 삽입, 그 다음에는 3번째 요소 1을 선택해 앞쪽에 삽입 아직 정렬되지 않은 부분의 첫 번재 요소를 정렬된 부분의 알맞은 위치에 삽입 위와 같은 작업을 n - 1회 반복하면 정렬을 마침 [알고리즘 개요] for(int i = 1; i < n; i++) { //tmp tmp; j--) { a[j] = a[j - 1]; } a[j] = tmp; } } Colored by Color ..