감자튀김 공장🍟

합병 정렬 하나의 리스트를 두 개의 균등한 크기로 분할하고 분할된 부분 리스트를 정렬한 다음, 두 개의 정렬된 부분 리스트를 합하여 전체가 정렬된 리스트를 얻는다. 분할 정복(divide and conquer) 기법에 바탕을 두고 있는 정렬이다. 즉 하나의 리스트를 2개의 작은 문제로 분리하고 각각을 해결한 다음, 결과를 모아서 원래의 문제를 해결한다. 분리된 문제가 해결되지 않는다면 분할 정복 문제를 반복하여 적용한다. (순환 호출) 합병 정렬 단계 분할(Divide): 입력 배열을 같은 크기의 2개의 부분 배열로 분할한다. 정복(Conquer): 부분 배열을 정렬한다. 부분 배열의 크기가 충분히 작지 않으면 순환 호출을 이용하여 다시 분할 정복 기법을 적용한다. 결합(Combine): 정렬된 부분 배..

퀵 정렬 분할-정복법(divide and conquer)에 근거한다. 퀵정렬은 합병 정렬과 비슷하게 전체 리스트를 2개의 부분 리스트로 분할하고, 각각의 부분 리스트를 다시 퀵정렬하는 전형적인 분할-정복법을 사용한다. 합병 정렬과의 다른 점은 리스트를 비균등하게 분할한다는 점이다. 리스트 안의 한 요소를 피벗(pivot)으로 선택하면 피벗보다 작은 요소들은 피벗의 왼쪽으로, 피벗보다 큰 요소들은 피벗의 오른쪽으로 옮겨진다. 이 상태에서 피벗을 제외한 왼쪽 리스트와 오른쪽 리스트를 다시 정렬하게 되면 전체 리스트가 정렬된다. 합병 정렬과 마찬가지로 부분 리스트에 대해 순환 호출된다. 퀵 정렬의 과정 피벗을 5로 설정한 후, 5보다 작은 값은 왼쪽 리스트에, 큰 값은 오른쪽 리스트로 보내는 탐색과 교환 과정..

내용 정리 ➡ https://good-potato.tistory.com/40 [C++] 쉘 정렬 (Shell Sort) 쉘 정렬 쉘 정렬은 삽입 정렬의 O(n^2)보다 빠르다. 셀 정렬은 정렬해야할 리스트를 일정한 기준에 따라 분류하여 연속적이지 않은 여러 개의 부분 리스트를 만들고, 각 부분 리스트를 삽입 정렬 good-potato.tistory.com 코드 정리 # 쉘 정렬 def shell(arr): n = len(arr) h = n // 2 while h > 0: for i in range(h, n): j = i - h tmp = arr[i] while j >= 0 and arr[j] > tmp: arr[j + h] = arr[j] j -= h arr[j + h] = tmp h //= 2

내용 정리 ➡ https://good-potato.tistory.com/38 [C++] 삽입 정렬(Insertion Sort) 삽입 정렬 정렬되어 있는 리스트에 새로운 레코드를 적절한 위치에 삽입하는 과정을 반복한다. 정렬되어 있지 않은 부분의 첫 번째 숫자가 정렬된 부분의 어느 위치에 삽입되어야 하는가를 판 good-potato.tistory.com 코드 정리 #삽입 정렬 def insertion(arr): n = len(arr) for i in range(1, n): j = i temp = arr[i] while j > 0 and arr[j-1] > temp: arr[j] = arr[j - 1] j -= 1 arr[j] = temp

내용 설명 ➡ https://good-potato.tistory.com/37 [C++] 선택 정렬(Selection Sort) 선택 정렬 배열에서 최소값을 발견한 다음, 이 최소값을 배열의 첫번째 요소와 교환한다. 다음에는 첫번째 요소를 제외한 나머지 요소들 중에서 가장 작은 값을 선택하고 이를 두번째 요소와 교 good-potato.tistory.com 코드 # 선택 정렬 def selection(arr): n = len(arr) for i in range(n-1): min = i for j in range(i + 1, n): if arr[j] < arr[min]: min = j arr[i], arr[min] = arr[min], arr[i]

설명은 여기로 ➡ https://good-potato.tistory.com/39 [C++] 버블 정렬(Bubble Sort) 버블 정렬 인접한 2개의 레코드를 비교하여 크기가 순서대로 되어 있지 않으면 서로 교환하는 비교-교환 과정을 리스트의 왼쪽 끝에서 시작하여 오른쪽 끝까지 진행한다. 리스트의 비교-교환 과 good-potato.tistory.com python 코드 #버블 정렬 def bubble_sort(arr): n = len(arr) for i in range(n-1): # range(시작 숫자, 종류 숫자, step) for j in range(n-1, i, -1): if arr[j - 1] > arr[j]: arr[j-1], arr[j] = arr[j], arr[j-1] # 최적화1 - 이..

쉘 정렬 쉘 정렬은 삽입 정렬의 O(n^2)보다 빠르다. 셀 정렬은 정렬해야할 리스트를 일정한 기준에 따라 분류하여 연속적이지 않은 여러 개의 부분 리스트를 만들고, 각 부분 리스트를 삽입 정렬을 이용하여 정렬한다. 모든 부분 리스트가 정렬되면 쉘 정렬은 다시 전체 리스트를 더 적은 개수의 부분 리스트로 만든 후에 알고리즘을 되풀이 한다. 위 과정을 부분 리스트의 개수가 1일 때까지 반복한다. 부분 리스트 구성 방법 주어진 리스트의 각 k번째 요소를 추출하여 만든다. 이 k를 간격(gap)이라고 한다. 각 스텝마다 간격 k를 줄여가므로 수행과정이 반복될 때마다 하나의 부분 리스트에 속하는 레코드들의 개수는 증가된다. 쉘 정렬의 과정 1단계 간격(gap)을 5로 잡고 {10, 3, 16}, {8, 22},..

버블 정렬 인접한 2개의 레코드를 비교하여 크기가 순서대로 되어 있지 않으면 서로 교환하는 비교-교환 과정을 리스트의 왼쪽 끝에서 시작하여 오른쪽 끝까지 진행한다. 리스트의 비교-교환 과정(스캔)이 한번 완료되면 가장 큰 레코드가 리스트의 오른쪽 끝으로 이동된다. 버블 정렬의 과정 5와 3을 비교하면 5가 더 크므로 서로 교환하고, 다음으로 5와 8을 비교하게 되면 8이 더 크므로 교환 없이 다음 단계로 진행된다. 한 번의 스캔에 의해 가장 큰 레코드가 리스트의 오른쪽 끝으로 이동하게 된다. 스캔의 실행 횟수는 원칙적으로는 (데이터 개수 - 1)번 만큼 실행되지만 중간에 정렬이 끝났다면 계속 실행하지 않는다. 구현 코드 #include using namespace std; void bubbleSort(i..

선택 정렬 배열에서 최소값을 발견한 다음, 이 최소값을 배열의 첫번째 요소와 교환한다. 다음에는 첫번째 요소를 제외한 나머지 요소들 중에서 가장 작은 값을 선택하고 이를 두번째 요소와 교환한다. 이 절차를 (개수 - 1)만큼 되풀이한다. 선택 정렬의 과정 구현 코드 #include using namespace std; void swap(int& a, int& b) { int tmp; tmp = a; a = b; b = tmp; } void SelectionSort(int* arr, int len) { int min_idx; for (int i = 0; i < len - 1; i++) { min_idx = i; for (int j = i + 1; j < len; j++) { if (arr[min_idx] ..