정렬 알고리즘

void bubbleSort(int[] arr) { for (int i = 0; i < arr.length - 1; i++) { for (int j = 0; j < arr.length - i - 1; j++) { if (arr[j] > arr[j + 1]) { swap(arr, j, j + 1); } } } }

array=[7, 5, 9, 0, 3, 1, 6, 2, 4, 8] def bubbleSort(data): for i in range(len(data)-1, 0, -1): for j in range(i): if data[j] > data[j+1]: data[j], data[j+1] = data[j+1], data[j] # 스와프 bubbleSort(array) print(array)

void selectionSort(int[] arr) { for (int i = 0; i < arr.length - 1; i++) { int minIdx = i; for (int j = i + 1; j < arr.length; j++) { if (arr[j] < arr[minIdx]) { minIdx = j; } } swap(arr, i, minIdx); } }

array=[7, 5, 9, 0, 3, 1, 6, 2, 4, 8] def selectionSort(data): for i in range(len(data)): min_index=i # 가장 작은 원소의 인덱스 for j in range(i+1, len(array)): if data[min_index] > data[j]: min_index=j data[i], data[min_index] = data[min_index], data[i] # 스와프 selectionSort(array) print(array)

void insertionSort(int[] arr) { for (int i = 1; i < arr.length; i++) { int tmp = arr[i]; int j = i - 1; while (j >= 0 && tmp < arr[j]) { arr[j + 1] = arr[j]; j--; } arr[j + 1] = tmp; } }

array=[7, 5, 9, 0, 3, 1, 6, 2, 4, 8] def insertionSort(data): for i in range(1, len(data)): for j in range(i, 0, -1): if data[j] < data[j-1]: # 한 칸씩 왼쪽으로 이동 data[j], data[j-1] = data[j-1], data[j] else: # 자기보다 작은 데이터를 만나면 그 위치에서 멈춤 break insertionSort(array) print(array)

// 병합 정렬 함수 public static void mergeSort(int[] arr, int left, int right) { if (left < right) { // 중간점 찾기 int mid = (left + right) / 2; // 왼쪽 반 정렬 mergeSort(arr, left, mid); // 오른쪽 반 정렬 mergeSort(arr, mid + 1, right); // 정렬된 두 부분을 병합 merge(arr, left, mid, right); } } // 병합 함수 public static void merge(int[] arr, int left, int mid, int right) { // 두 부분을 나누기 int n1 = mid - left + 1; int n2 = right - mid; // 임시 배열 생성 int[] leftArray = new int[n1]; int[] rightArray = new int[n2]; // 임시 배열에 데이터 복사 for (int i = 0; i < n1; ++i) leftArray[i] = arr[left + i]; for (int j = 0; j < n2; ++j) rightArray[j] = arr[mid + 1 + j]; // 임시 배열들을 병합 int i = 0, j = 0; int k = left; while (i < n1 && j < n2) { if (leftArray[i] <= rightArray[j]) { arr[k] = leftArray[i]; i++; } else { arr[k] = rightArray[j]; j++; } k++; } // 남은 요소들을 복사 while (i < n1) { arr[k] = leftArray[i]; i++; k++; } while (j < n2) { arr[k] = rightArray[j]; j++; k++; } }

array=[6, 5, 3, 1, 8, 7, 2, 4] def merge(left, right): result=[] while len(left) > 0 and len(right) > 0: # 왼쪽 & 오른쪽 배열이 모두 존재한다면 if left[0] <= right[0]: # 왼쪽이 더 작으면 왼쪽을 추가 result.append(left[0]) left=left[1:] else: # 아니라면 오른쪽 추가 result.append(right[0]) right=right[1:] if len(left) > 0: result += left if len(right) > 0: result += right #result.extend([*left, *right]) return result def mergeSort(data): if len(data) <=1: # 배열의 길이가 1보다 작거나 같으면(원소의 개수가 1이면) return data mid = len(data)//2 # 배열을 1/2로 나누기 위해 배열의 중간 인덱스를 구함 left = mergeSort(data[:mid]) # 왼쪽 배열 병합하기 위한 호출 right = mergeSort(data[mid:]) # 오른쪽 배열 병합하기 위한 호출 result = merge(left, right) # 왼쪽 배열과 오른족 배열을 합칠 임시 배열 result 선언 return result print(mergeSort(array))

static int partition(int[] arr, int lo, int hi) { // 가장 마지막 인덱스를 피벗으로 설정 int pivot = arr[hi]; int left = lo; // 피벗 기준으로 작은 값 왼쪽, 큰 값 오른쪽으로 정렬 수행. for (int right = lo; right < hi; right++) { if (arr[right] < pivot) { // 현재 left 위치의 값과 right 위치의 값을 교환 int temp = arr[left]; arr[left] = arr[right]; arr[right] = temp; left++; // left 포인터를 오른쪽으로 이동 } } // 피벗 정렬 int temp = arr[left]; arr[left] = arr[hi]; arr[hi] = temp; // 피벗의 위치 반환 return left; } // 재귀 수행 static int[] Quicksort(int[] arr, int lo, int hi) { // 배열의 범위 (lo ~ hi)가 유효한 경우에만 정렬 수행 if (lo < hi) { // partition을 수행하고 피벗의 최종 위치 얻음 int pivot = partition(arr, lo, hi); // 피벗 기준 왼쪽 부분 배열을 재귀적으로 정렬 Quicksort(arr, lo, pivot - 1); // 피벗 기준 오른쪽 부분 배열을 재귀적으로 정렬 Quicksort(arr,pivot + 1, hi); } return arr; }

array=[5, 7, 9, 0, 3, 1, 6, 2, 4, 8] def quickSort(data, start, end): if start >= end: # 원소가 1개인 경우 종료 return pivot = start # 피벗은 첫 번째 원소 left = start +1 right = end while left <= right: while left <= end and data[left] <= data[pivot]: # 피벗보다 큰 데이터를 찾을 때까지 반복 left += 1 while right > start and data[right] >= data[pivot]: # 피벗보다 작은 데이터를 찾을 때까지 반복 right -= 1 if left > right: # 엇갈렸다면 작은 데이터와 피벗을 교체 data[right],data[pivot]=data[pivot],data[right] else: # 엇갈리지 않았다면 작은 데이터와 큰 데이터를 교체 data[left],data[right]=data[right],data[left] quickSort(data, start, right-1) # 분할 이후 왼쪽 부분과 오른쪽 부분에서 각각 정렬 수행 quickSort(data, right+1, end) quickSort(array, 0, len(array)-1) print(array)

array=[5, 7, 9, 0, 3, 1, 6, 2, 4, 8] def quickSort(data): if len(data) <= 1: # 리스트가 하나 이하의 원소만을 담고 있다면 종료 return data pivot=data[0] # 피벗은 첫 번째 원소 tail=data[1:] # 피벗을 제외한 리스트 left_side=[x for x in tail if x <= pivot] # 분할된 왼쪽 부분 right_side = [x for x in tail if x > pivot] # 분할된 오른쪽 부분 result= quickSort(left_side) + [pivot] + quickSort(right_side) return result # 분할 이후 왼쪽 부분과 오른쪽 부분에서 각각 정렬을 수행하고, 전체 리스트를 반환 print(quickSort(array))

array=[5, 7, 9, 0, 3, 1, 6, 2, 4, 8] def quickSort(data, start, end): pivot = data[(start+end)//2] # 피벗은 가운데 원소 left, right = start, end while True: while data[left] < pivot: left += 1 while data[right] > pivot: right -= 1 if left >=right: break data[left], data[right] = data[right], data[left] if start < right: quickSort(data, start, right) if left < end: quickSort(data, right+1, end) quickSort(array, 0, len(array)-1) print(array)

void heapSort(int[] arr) { for (int i = arr.length / 2 - 1; i < arr.length; i++) { heapify(arr, i, arr.length - 1); } for (int i = arr.length - 1; i >= 0; i--) { swap(arr, 0, i); heapify(arr, 0, i - 1); } } void heapify(int[] arr, int parentIdx, int lastIdx) { int leftChildIdx; int rightChildIdx; int largestIdx; while (parentIdx * 2 + 1 <= lastIdx) { leftChildIdx = (parentIdx * 2) + 1; rightChildIdx = (parentIdx * 2) + 2; largestIdx = parentIdx; if (arr[leftChildIdx] > arr[largestIdx]) { largestIdx = leftChildIdx; } if (rightChildIdx <= lastIdx && arr[rightChildIdx] > arr[largestIdx]) { largestIdx = rightChildIdx; } if (largestIdx != parentIdx) { swap(arr, parentIdx, largestIdx); parentIdx = largestIdx; } else { break; } } }

array=[16, 9, 8, 14, 12, 10, 3] def heapify(data, n, i): # 힙을 구성하는 함수 largest = i # 루트 노드를 가장 큰 값으로 설정 left = 2*i+1 # 왼쪽 자식 노드 right = 2*i+2 # 오른쪽 자식 노드 if left < n and data[i] < data[left]: # 왼쪽 자식 노드가 부모 노드보다 큰 경우 largest=left if right < n and data[largest] < data[right]: # 오른쪽 자식 노드가 부모 노드나 가장 큰 자식 노드보다 큰 경우 largest = right if largest != i: # 가장 큰 노드를 부모 노드로 설정하고, 재귀적으로 힙을 구성 data[i], data[largest] = data[largest], data[i] heapify(data, n, largest) def heapSort(data): # 힙 정렬 함수 n=len(data) for i in range(n//2-1, -1, -1): # 최대 힙을 구성 heapify(data, n, i) for i in range(n-1, 0, -1): # 힙에서 요소를 하나씩 추출하여 정렬된 리스트에 추가 data[i], data[0] = data[0], data[i] # 루트 노드와 맨 마지막 요소를 교환 heapify(data, i, 0) # 힙 구성 heapSort(array) print(array)

import heapq def heapsort(iterable): h = [] result = [] for value in iterable: # 모든 원소를 차례대로 힙에 삽입 heapq.heappush(h, value) for i in range(len(h)): # 힙에 삽입된 원소를 차례대로 꺼내어 담기 result.append(heapq.heappop(h)) return result result = heapsort([7, 5, 9, 0, 3, 1, 6, 2, 4, 8]) print(result)

from heapq import heappush, heappop array=[7, 5, 9, 0, 3, 1, 6, 2, 4, 8] def heapSort(iterable): h=[] for value in iterable: heappush(h, value) return [heappop(h) for i in range(len(h))] print(heapSort(array))

def heapsort(iterable): h = [] result = [] for value in iterable: # 모든 원소를 차례대로 힙에 삽입 heapq.heappush(h, -value) for i in range(len(h)): # 힙에 삽입된 원소를 차례대로 꺼내어 담기 result.append(-heapq.heappop(h)) return result result = heapsort([7, 5, 9, 0, 3, 1, 6, 2, 4, 8]) print(result)

array=[7, 5, 9, 0, 3, 1, 6, 2, 9, 1, 4, 8, 0, 5, 2] count=[0] * (max(array)+1) for i in range(len(array)): # 각 데이터에 해당하는 인덱스 값 증가 count[array[i]] += 1 for i in range(len(count)): # 리스트에 기록된 정렬 정보 확인 for j in range(count[i]): print(i, end=' ') # 띄어쓰기를 구분으로 등장한 횟수만큼 인덱스 출력

array=[7, 5, 9, 0, 3, 1, 6, 2, 9, 1, 4, 8, 0, 5, 2] def countingSort(array): count = {} result =[] for num in array: count[num] = count.get(num,0)+1 for num in range(min(array), max(array)+1): while num in count and count[num] != 0: result.append(num) count[num] -= 1 return result print(countingSort(array))

array=[7, 5, 9, 0, 3, 1, 6, 2, 4, 8] result1=sorted(array) result2=sorted(array, reverse=True) print(result1) print(result2)

array=[7, 5, 9, 0, 3, 1, 6, 2, 4, 8] array.sort() print(array)

array=[('바나나',2),('사과',5),('당근',3)] def setting(data): return data[1] result=sorted(array, key=setting) print(result)

array=[[0, 4], [0, 2], [1, 3], [2, 1]] def second(x): return x[1] print(sorted(array, key=second)) print(sorted(array, key=lambda x: x[1]))

n=int(input()) array=[] for i in range(n): array.append(int(input())) array=sorted(array, reverse=True) for i in array: print(i, end=' ')

n = int(input()) array = [] for i in range(n): data = input().split() array.append((data[0], int(data[1]))) array.sorted(array, key=lambda student: student[1]) for student in array: print(student[0], end=' ')