Nanarin🙃

계수 정렬 (Counting Sort) 알고리즘 : 계수 정렬 = 도수 정렬 = 카운팅 정렬 요소의 대소 관계를 판단하지 않고 빠르게 정렬할 수 있는 알고리즘 1. 배열 내 요소 값들의 개수를 저장하는 카운팅 배열을 만든다 2. 카운팅 배열의 요소에 직전 요소의 값을 더해준다. 3. 배열과 같은 크기의 출력 배열을 만들고 입력 배열의 역순으로 출력 배열에 요소들을 채워넣는다. 3-1. 배열 a의 맨 뒷 요소 8을 꺼내 counting[8]을 확인 3-2. 배열 b의 counting[8]-- 후 counting[8] 자리에 8을 저장 4. 배열 b를 배열 a로 복사한다 메소드 countingSort() : 배열 a를 카운팅 정렬 매개변수 : int[] a, int n - 카운팅 정렬 : void count..

힙 정렬 (Heap Sort) 알고리즘 : '부모의 값이 자식의 값보다 항상 크다 or 작다' 를 만족하는 완전이진트리 힙 의 특성을 이용하여 정렬 수행. 선택 정렬 을 응용한 알고리즘 메소드 swap() : a[idx1] 과 a[idx2] 를 교환 매개변수 : int[] a, int idx1, int idx2 메소드 donwHeap() : 배열 a의 index left 부터 right 까지 요소를 힙으로 만든다 매개변수 : int[] a, int left, int right 메소드 heapSort() : 길이가 n인 배열 a를 힙 정렬 매개변수 : int[] a, int n - 힙 정렬 : void swap(int[]a, int idx1, int idx2) { int t = a[idx1]; a[idx1..

합병 정렬 (Merge Sort) 알고리즘 : 배열을 앞부분과 뒷부분으로 나누어 각각 정렬한 다음 병합하는 작업을 반복하여 정렬을 수행하는 알고리즘 int[] merge = {8, 1, 4, 2, 7, 6, 3, 5} 1. 배열을 반으로 나눈다 2. 앞부분을 합병정렬로 정렬한다 3. 뒷부분을 합병정렬로 정렬한다 4. 앞부분과 뒷부분을 병합한다 4-1. 앞부분을 배열 buff에 복사 4-2. 배열 buff와 뒷부분을 배열 a에 병합 4-3. 배열 buff의 나머지 요소를 배열 a에 복사 메서드 mergeSort() : 배열 a의 크기 n과 같은 크기의 배열 buff를 선언하고, mergetSort()를 실행 후 정렬이 끝나면 배열 buff를 해제 매개변수 : int[] a, int n 메서드 mergeSo..

퀵 정렬 (Quick Sort) 알고리즘 : 분할 정복 알고리즘 중의 하나로, 매우 빠른 속도를 자랑하는 알고리즘 1. 배열 안의 한 요소를 선택하여 이를 피벗이라 하고, 배열의 맨 첫번째 요소와 교환 2. 배열의 왼쪽 끝에서부터 피벗보다 큰 요소를, 오른쪽 끝에서부터 피벗보다 작은 요소를 탐색 3. 왼쪽에서 발견한 피벗보다 큰 요소와 오른쪽에서 발견한 피벗보다 작은 요소를 교환 3. 왼쪽과 오른쪽에서 탐색하던 커서가 만나면 중지, 피벗과 교환 => 두 커서가 만난 위치 왼쪽에는 피벗보다 작은 요소가, 오른쪽에는 큰 요소가 위치하게 된다 4. 피벗을 기준으로 왼쪽 그룹과 오른쪽 그룹을 각각 다시 퀵 정렬 5. 각 그룹이 더이상 분할이 불가능할 때 까지 반복 -> 그룹 배열의 크기가 0이나 1이면 중지 i..

셸 정렬 (Shell Sort) 알고리즘 : 삽입 정렬 의 장점은 살리고 단점은 보완하여 좀 더 빠르게 정렬하는 알고리즘, 불안정 정렬. 정렬할 배열의 요소를 그룹으로 나눠 각 그룹별로 삽입 정렬을 수행하고, 그 그룹을 합치면서 정렬을 반복하여 요소의 이동 횟수를 줄임 삽입 정렬의 장/단점 장점 : 정렬을 마쳤거나 정렬을 마친 상태에 가까우면 정렬 속도가 빨라진다 단점 : 삽입할 위치가 멀리 떨어져 있으면 이동(삽입)해야 하는 횟수가 많아진다 셸 정렬은 전체의 배열을 한번에 정렬하지 않고 정렬해야 할 배열을 일정한 기준에 따라 분류하여 연속적이지 않은 여러 개의 부분 그룹을 만들어 각 그룹을 삽입 정렬한다. 부분 그룹을 구성할 때 주어진 배열의 각 K번째 요소를 추출하여 만드는데, 이 K를 간격(gap)..

삽입 정렬 (Insertion Sort) 알고리즘 : 선택한 요소를 그보다 더 앞쪽의 정렬된 부분의 알맞은 위치에 삽입하여 정렬하는 알고리즘 트럼프 카드를 한 줄로 늘어놓을 때 사용하는 방법과 유사 1. 아직 정렬되지 않은 부분의 첫번째 요소 selection[i]를 선택 2. 정렬된 부분에서 selection[i]의 알맞은 위치를 찾아 삽입 2-1. 정렬된 부분의 요소를 한칸씩 뒤로 밀어낸다 2-2. 정렬된 부분의 왼쪽 끝에 도달하거나 selection[i]보다 작거나 같은 수를 만날 때 까지 2-3. 알맞은 자리에 selection[i] 삽입 메서드 insertionSort() : 길이가 n인 배열 a를 삽입 정렬 매개변수 : int[] a, int n - 삽입 정렬 void insertionSort..

선택 정렬 (Selection Sort) 알고리즘 : 가장 작은 요소부터 선택해 알맞은 위치로 옮겨서 순서대로 정렬하는 알고리즘 1. 아직 정렬되지 않은 부분에서 가장 작은 요소 selection[i]를 선택 2. selection[i]와 아직 정렬되지 않은 부분의 첫번째 요소를 교환 3. n-1회 반복 메서드 swap() : a[idx1] 과 a[idx2] 를 교환 매개변수 : int[] a, int idx1, int idx2 메서드 selectionSort() : 길이가 n인 배열 a를 선택 정렬 매개변수 : int[] a, int n - 선택 정렬 void swap(int[] a, int idx1, int idx2) { int t = a[idx1]; a[idx1] = a[idx2]; a[idx2] ..

칵테일 셰이커 정렬 (Cocktail Shaker Sort) 알고리즘 : 칵테일 셰이커 정렬(Cocktail Shaker Sort) = 양방향 버블 정렬(Bidirectional Bubble Sort) = 셰이커 정렬(Shaker Sort) = 칵테일 정렬(Cocktail Sort) 버블 정렬 의 변형. 버블 정렬과는 달리 매 패스마다 리스트의 순서를 바꿔 정렬 홀수 번째의 패스는 가장 작은 요소를 맨 앞으로, 짝수 번째의 패스는 가장 큰 요소를 맨 뒤로 정렬 or 홀수 번째의 패스는 가장 큰 요소를 맨 뒤로, 짝수 번째의 패스는 가장 작은 요소를 맨 앞으로 정렬 첫번째 패스가 완료되면 가장 작은 요소가 맨 앞으로 이동하기 때문에 두번째 패스는 맨 앞의 요소를 제외하고 앞 -> 뒤 방향으로 진행되고, 두..

버블 정렬 (Bubble Sort) 알고리즘 : 서로 이웃한 두 요소의 대소 관계를 비교하여 교환을 반복하는 정렬 알고리즘 요소의 개수가 n개인 배열은 총 n-1회의 패스를 거치며, i번째 패스에서 각각 n-i번의 정렬을 수행한다 ( 패스의 횟수가 n-1회인 이유는 n-1회의 정렬이 끝나면 마지막 요소 하나가 남는데, 이미 정렬된 상태이기 때문 ) int[] bubble = {6, 4, 5, 1, 2} 1. 첫번째 패스 : bubble[0] ~ bubble[4] 중 가장 큰 요소가 맨 뒤로 이동 1-1. bubble[0]과 bubble[1]을 비교, bubble[0]이 bubble[1]보다 크므로 교환 {4, 6, 5, 1, 2} 1-2. bubble[1]과 bubble[2]을 비교, bubble[1]이..

에라토스테네스의 체 (Sieve of Eratosthenes) 알고리즘 : 고대 그리스 수학자 에라토스테네스가 발견한 방법으로 소수를 찾는 알고리즘 체로 치듯이 숫자를 걸러내는 방식. 소수의 배수를 모두 지우면 나머지는 소수가 된다 ex ) 2 ~ 120 사이의 소수를 구하는 방법 1. 2부터 소수를 구하고자 하는 구간의 모든 수를 나열한다. 그림에서 회색 사각형으로 두른 수들이 여기에 해당한다. 2. 2는 소수이므로 오른쪽에 2를 쓴다. (빨간색) 3. 자기 자신을 제외한 2의 배수를 모두 지운다. 4. 남아있는 수 가운데 3은 소수이므로 오른쪽에 3을 쓴다. (초록색) 5. 자기 자신을 제외한 3의 배수를 모두 지운다. 6. 남아있는 수 가운데 5는 소수이므로 오른쪽에 5를 쓴다. (파란색) 7. 자..