목록CS/알고리즘 (2)
HS_development_log
병합 정렬(Merge Sort) 병합 정렬 이란? 합병 정렬이라고도 부르며, 분할 정복 방법을 통해 구현 안정 정렬 이다 Process 원소 개수가 1 또는 0 이 될 때 까지 두 부분으로 쪼갠다 쪼갠 순서의 역순으로 크기를 비교해 병합해 나간다 Java Code import java.util.*; public class Main { public static void main(String[] args) { int[] arr = {43, 51, 76, 60, 73, 82, 36, 98,10,23,1,100}; mergeSort(arr, 0, arr.length-1); System.out.println(Arrays.toString(arr)); } public static void mergeSort(int[]..
퀵 정렬(Quick Sort) 퀵 정렬 이란? 퀵 정렬은 분할 정복(divide and conquer) 방법을 통해 주어진 배열을 정렬한다 불안정 정렬 이다 다른 원소와의 비교만으로 정렬을 수행하는 비교 정렬이다 Process 배열 가운데서 하나의 원소를 고른다. 이렇게 고른 원소를 피벗(pivot)이라고 한다 피벗을 고르는 방법은 여러가지가 있지만,이 글에서는 맨 오른쪽 원소를 피벗으로 잡는다 피벗을 어떻게 고르느냐에 따라 속도 차이가 많이 난다 피벗보다 작은 원소는 모두 왼쪽, 큰 원소는 모두 오른쪽으로 오게하고, 배열을 분할한다 분할을 마친 뒤에 피벗은 더 이상 움직이지 않는다 분할된 두 개의 작은 배열에 대해 재귀(Recursion)적으로 이 과정을 반복한다 재귀 호출이 한번 진행될 때마다 최소한..