회고장

개요 최대 Heap 자료 구조를 이용해서 최대값을 pop하고 해당 값을 뒤부터 적재하며 정렬. 복잡도 최악 평균 최소 Big O 표기법 O(nlogn) O(nlogn) O(nlogn) 알고리즘 절차 모든 요소를 최대 heap 자료 구조로 만들 수 있도록 heapify 시킴. 최대 heap 에서 pop을 하고 마지막 요소와 swap함. 이 과정을 모든 요소가 정렬이 되도록 계속 반복함. 자바 코드 class Heap { public static void main(String[] args) { int[] testCase1 = {1, 26, 9, 67,653,452,2,3,46,87,356543}; heapSort(testCase1); for (int item : testCase1) { System.out.p..

개요 우선 전체 요소를 각 부분 집합의 크기가 1개가 될 때까지 반절로 재귀적으로 쪼갠다. 그리고 쪼개진 부분 집합들을 역순으로 조립해나간다. 이 때, 조립은 2 개씩 진행하며 2개를 조립할 때 각 부분 집합을 큐로 취급하여 두 큐의 맨 앞 요소 중 가장 작은 값을 선택하고 pop하며 차곡차곡 조립한다. 이 과정을 재귀적으로 진행하면 결국 전체적으로 정렬이 된다. 복잡도 최악 평균 최소 Big O 표기법 O(nlogn) O(nlogn) O(nlogn) 알고리즘 절차 합병 정렬을 준비하기 위해 정렬할 배열[arr]와 크기가 똑같은 빈 배열[tmp]을 생성한다. 정가운데 요소를 기준으로 arr를 반으로 잘라내고 각 부분을 재귀적으로 합병 정렬한다. 이 때, 정렬은 후위 순회를 하며 진행한다. 실제 정렬 방법..

개요 특정 값[A]을 기준으로 (A 앞은 A 값 이하의 값들)[B]을, (A 뒤는 A 값 이상의 값들)[C]을 배치한다. 이를 각각 B와 C에 대해 재귀적으로 실행하면 결국 전체에 대해 정렬하게 된다. 복잡도 최악 평균 최소 Big O 표기법 O(n^2) O(n log n) O(n log n) 알고리즘 절차 임의의 특정 값[A]을 기준으로 잡고 A를 제외한 부분의 양쪽 값부터 검사를 진행한다. 즉, 포인터 start와 end를 설정해 특정 규칙에 맞게 start와 end 인덱스의 값들을 Swap한다. 특정 규칙이란, A값을 기준으로 특정 인덱스[pivot]을 기준으로 pivot 앞의 요소들은 A값보다 작아야 하고 pivot 뒤의 요소들은 A값보다 커야 한다는 것을 의미한다. 포인터 start는 맨 앞의 ..

개요 삽입 정렬을 보완한 형태의 정렬. 삽입 정렬은 때에 따라 오른쪽 끝에 있는 요소를 왼쪽 끝으로 옮기기 위해 불필요한 Swap을 수행해야 할 수도 있다. 이를 막기 위해 Swap을 1 칸 단위로 수행하는 것이 아닌 그 이상의 값으로 수행하는 정렬. 복잡도 최악 평균 최소 Big O 표기법 O(n^2) O(n^1.5) O(n) 알고리즘 절차 gap을 설정할 때, 전체 길이의 반절부터 시작해서 다음 단계에서는 그 길이의 반절, 그 다음에서는 또 그 길이의 반절로 설정을 하면 된다. 단, 해당 길이가 짝수일 경우, +1을 해 홀수로 만들어 준다. 해당 gap이 결정되면 모든 범위를 커버할 수 있도록 인덱스 0부터 gap-1까지 반복합니다. 시작점과 gap을 가지고 insertSort를 수행하면 됨. 자바 ..

개요 손 안의 카드 뭉치를 정리하는 것과 같은 원리. 특정 카드가 해당 카드의 앞 카드 뭉치 중 적절한 위치에 삽입하는 방법의 정렬. 복잡도 최악 평균 최소 Big O 표기법 O(n^2) O(n^2) O(n) 알고리즘 절차 첫번째 요소는 스킵하고 2 번째 요소부터 검사를 시작함. i 번째 요소를 임시로 tmp 변수에 담아놓는다. i 번째 요소를 i-X 번째 요소와 비교한다. 만약 i 번째 요소가 더 작다면 i-X 번째 요소에 i-X+1 번째 위치에 놓아 빈 공간을 마련해줌. 이 경우, X값을 +1해서 다시 수행한다. 만약 i 번째 요소가 더 크다면 i-X+1위치에 tmp에 저장한 값을 위치시킴. 이 경우, 3번의 루프를 탈출한다. 자바 코드 class Insert { public static void m..

개요 최소값의 인덱스값을 찾고 해당 위치와 타겟 위치를 Swap하며 정렬하는 방법. 복잡도 최악 평균 최소 Big O 표기법 O(n^2) O(n^2) O(n^2) 알고리즘 절차 타겟 인덱스를 0으로 설정함. 타겟 인덱스부터 끝까지 선형 탐색하며 최소값의 인덱스값을 기억함. 타겟 인덱스와 최소값의 인덱스를 활용해서 Swap함. 타겟 인덱스값을 1로 설정하고 1~3 과정을 다시 반복함. 모든 요소가 정렬되면 종료. 자바 코드 class Selection { public static void main(String[] args) { int[] testCase1 = {1, 26, 9, 67,653,452,2,3,46,87,356543}; selectionSort(testCase1); for (int item : ..

개요 너비가 2인 Window를 (n-1)번 정도 움직이며 Window의 내에서 Swap하며 정렬하는 방법. 복잡도 최악 평균 최소 Big O 표기법 O(n^2) O(n^2) O(n^2) 알고리즘 절차 인덱스 0부터 인덱스 n-2까지 움직이는 크기가 2인 Window를 운용한다. 이 때, 윈도우를 움직일 때마다 크기가 정렬되어 있지 않다면 Swap하기. 1번의 결과로 n-1에는 최대값이 위치하게 되고 다시 인덱스 0부터 인덱스 n-3까지 움직이는 Window를 운용한다. 이 과정을 모든 요소가 정렬될 때까지 진행한다. 자바 코드 class Bubble { public static void main(String[] args) { int[] testCase1 = {1, 26, 9, 67,653,452,2,3..