다나리

합병 정렬 (Merge Sort) 분할 정복 알고리즘 (Divide & Conquer) 이다. 주어진 배열을 원소 하나하나로 쪼갠다. 쪼갠 원소들을 정렬하면서 다시 합친다. 퀵 정렬 (Quick Sort) 분할 정복 알고리즘 (Divide & Conquer) 이다. 임의의 원소로 pivot을 정한다. pivot을 기준으로 pivot보다 작은 수끼리, pivot보다 큰 수끼리 새로운 배열을 만든다. 새로운 배열에서 다시 pivot을 정하고 같은 과정을 반복한다. 힙 정렬 (Heap Sort) 힙 자료구조를 사용한다. 오름차순으로 정렬할 땐 최소 힙 트리, 내림차순으로 정렬할 땐 최대 힙 트리를 사용한다. 오름차순으로 정렬하는 경우, 완전 이진 트리 형태의 최소 힙을 만든다. 삭제연산을 수행한다 -> 최댓값..

버블 정렬 (Bubble Sort) 인접한 두 요소를 비교하여 왼쪽 요소가 오른쪽 요소보다 크면 서로 바꾼다. 배열의 끝까지 비교하면 마지막 요소는 그 위치가 최종적으로 정렬된 요소이다. 다시 처음으로 돌아와서 두 요소끼리 비교하며 자리를 바꾼다. 배열의 크기가 N이라면, (N-1) + (N-2) + ... + 1 = N * (N-1) / 2번 비교를 수행한다. 시간복잡도: O(N^2) 자바 코드 import java.util.Scanner; public class BubbleSort { public static void main(String[] args) { Scanner scn = new Scanner(System.in); int n = scn.nextInt(); int[] arr = new int[..