키리Kirri's IT노트

도수 정렬 요소의 대소 관계를 비교할 필요가 없음 도수분포표 작성, 누적도수분포표 작성, 목적 배열 만들기, 배열 복사의 4단계로 이루어짐 [10점 만점의 테스트에서 학생 9명의 점수 도수 정렬] 1단계. 도수분포표 만들기 학생 점수 배열 a를 바탕으로 '각 점수에 해당하는 학생이 몇 명인지'를 나타내는 도수분포표 작성 모든 요소의 값을 초기화한 배열 f에 배열 a를 처음부터 스캔하면서 도수분포표 작성 예를 들어, a[0]이 5점이면 f[5]를 1만큼 증가시키고 a[1]이 7점인 경우 f[7]을 1만큼 증가시키는 작업을 반복 for(int i = 0; i < n; i++) f[a[i]]++; 2단계. 누적도수분포표 만들기 '0점부터 점수 n까지 몇 명의 학생이 있는지' 누적된 값을 나타내는 누적도수분포표..

힙이란? 힙(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..