힙 정렬

힙 정렬 힙 정렬은 선택 정렬을 응용한 알고리즘으로 힙의 특성을 이용한 정렬입니다. 힙 : 부모값이 자식값보다 항상 크다(작다)라는 조건을 만족하는 완전이진트리, 힙에 루트는 항상 모든 수 중 가장 큰 값이 위치한다. 트리 root(루트) : 트리에 가장 상위부분 parent(부모), child(자식) : 트리에서 요소의 상하 관계 sibling(형제) : 자식 간의 관계 완전이진트리 : 트리의 한 종류 완전 : 부모가 자식을 왼쪽부터 추가하는 모양을 유지 이진 : 부모가 가질 수 있는 자식의 수가 최대 2개이다. 힙 트리의 한 종류이다. 항상 완전이진트리의 형태를 가져야한다. 힙에서 부모와 자식 사이의 대소관계는 일정하나 형제 간의 대소관계는 일정하지 않을 수 있다. 여기서 일정하다라는 것은 상대적으로..

• format_list_bulleted 정렬 알고리즘
• · 2022. 10. 9.
• textsms

도수 정렬

도수 정렬 요소들의 대소관계를 직접 비교하지 않고 빠르게 정렬할 수 있는 알고리즘. 도수정렬의 경우 정렬기준에 따른 요소들 사이의 직접적인 비교를 할 필요가 없다. 총 4단계 과정을 통하여 요소들을 정렬할 수 있다. 도수분포표 만들기 만들어진 도수분포표를 활용하여 누적 도수분포표 만들기 목표 배열 만들기 배열 복사하기 위에 4개의 단계를 전체적인 코드를 통하여 부분적으로 확인해보고자 한다. //도수정렬 static void countionSort(int[] a, int n , int max){ int[] f = new int[max + 1]; int[] b = new int[n]; for(int i = 0 ; i < n ; i++) f[a[i]]++; for(int i = 1 ; i < f.length;..

• format_list_bulleted 정렬 알고리즘
• · 2022. 10. 8.
• textsms

병합 정렬

병합 정렬 배열 앞부분(영역)과 뒷부분(영역)으로 분할하여 정렬 후 다시 병합(합치기)하는 작업을 반복하며 정렬하는 알고리즘 병합 과정? 위와같이 배열을 앞, 뒤로 나눠서 각자 정렬한 후에 각각의 분할된 배열을 앞에서부터 서로 비교하며 기존 배열에 병합하게 된다. 이때 비교 대상인 두 배열 중 비교 후 값으로 선택되면 그 값이 있던 배열은 다음 요소로 이동하며 비교해나간다. //두 배열 병합하기 static void merge(int[] a,int na,int[] b,int nb, int[] c){ int pa = 0; int pb = 0; int pc = 0; while(pa < na && pb < nb) c[pc++] = a[pa] < b[pb] ? a[pa++] : b[pb++]; // a , b ..

• format_list_bulleted 정렬 알고리즘
• · 2022. 10. 6.
• textsms

퀵 정렬

퀵 정렬 찰스 앤터니 리처드 호어(C. A. R. Hoare)가 알고리즘의 정렬 속도가 매우 빠른 데서 착안해 직접 붙인 이름이다. 범위에 있는 배열 요소들에 대해서 기준 값(=피벗) 하나를 정하고 기준 값과 정렬 조건(작은순, 큰 순 등)에 따라 좌우에 있는 요소들을 교환하며, 정렬을 마칠 때까지 지속적으로 좌우로 범위를 분할해가면서 정렬하는 알고리즘이다. 자세한 부분은 그림을 참고하면 이해를 돕는데 좋을 것이라 생각한다. static void swap(int[] a, int idx1 , int idx2){ int t = a[idx1]; a[idx1] = a[idx2] ; a[idx2] = t; } static void quickSort(int[] a, int left, int right){ int p..

• format_list_bulleted 정렬 알고리즘
• · 2022. 10. 5.
• textsms

셸 정렬

셸 정렬 도날드 셸(D. L. Shell)에 의해 고안되었으며, 퀵 정렬이 나오기 전까지 가장 빠른 정렬 알고리즘이었다. 셸 정렬은 단순 삽입 정렬의 장점은 살리면서 단점은 보완하여 좀 더 빠르게 정렬 가능한 정렬 알고리즘이다. 일정한 간격으로 서로 떨어져 있는 두 요소를 그룹으로 묶어 대략 정렬을 수행하고, 간격을 좁혀 그룹의 수를 줄이면서 정렬을 반복하여 요소의 이동 횟루를 줄이는 정렬 알고리즘이다. 단순 삽입 정렬 장점 : 배열이 이미 많은 부분 정렬되어 있을 시 정렬 속도가 굉장히 빠르다. 단순 삽입 정렬 단점 : 삽입할 곳이 멀리 떨어져 있을 시 거리에 비례해서 이동하는 횟수가 많아진다. -> 삽입할 위치와 현재 위치 사이에 위치한 요소들을 현재 위치까지 모두 한 칸씩 이동 시키고 삽입해야한다...

• format_list_bulleted 정렬 알고리즘
• · 2022. 10. 3.
• textsms

단순 삽입 정렬(straight insertion sort)

단순 삽입 정렬(straight insertion sort) 단순 삽입 정렬은 0 ~ n-1까지 n개의 배열이 있다고 가정했을 때, 1번 위치 요소부터 선택을 시작하여 현재 정렬되지 않은 부분의 첫 번째 요소를 선택하여 선택한 위치 앞 부분 요소들과 비교를 하여 정렬기준에 따라 해당 되는 위치에 삽입을 수행해나가는 정렬 알고리즘이다. 단순 삽입정렬은 셔틀 정렬(shuttle sort)라고도 부른다. // 선택 정렬 부분 static void insertionSort(int[] a, int n){ for(int i = 1; i 0 && a[j-1] > tmp ;..

• format_list_bulleted 정렬 알고리즘
• · 2022. 10. 1.
• textsms