밍의 기록들😉

퀵 정렬 개념원소(pivot(기둥/중심))를 하나 정하여, 해당 원소보다 작은 수들과 큰 수들로 나눈다. 1. pivot의 위치는 확정된 것2. pivot의 왼쪽과 오른쪽의 자리는 바뀌지 않는다. (= 왼쪽과 오른쪽을 따로 정렬해도 된다.) 퀵 정렬의 시간복잡도재귀적으로 구해야 한다.1. pivot을 정한다. = O(1)2. 작거나 같은 값과 큰 값을 분류한다. = O(n)3. 각각을 퀵정렬 한다. * T(n) = n개의 숫자를 퀵 정렬로 정렬하는데 걸리는 시간* T(n) = T(left) + T(right) + O(n) // 점화식 // left = pivot보다 작거나 같은 원소의 개수 // right = pivot보다 큰 원소의 개수 * pivot이 원소의 개수를 절반으로 나눈다고 가정하자* T(n..

합병 정렬 개념배열을 절반으로 나누어 각각을 정렬한 후, 합친다. 합병 정렬의 시간복잡도재귀적으로 구해야 한다.1. 왼쪽 합병정렬 = T(n/2)2. 오른쪽 합병정렬 = T(n/2)3. 합친다 = O(n) * T(n) = n개의 숫자를 합병정렬할 때의 시간복잡도* T(n) = 2 x T(n/2) + O(n) // 점화식 = 2(2T(n/4) + O(n/2)) + O(n) = 4T(n/4) + 2O(n) // 1번 대입 = 4(2T(n/8) + O(n/4)) + 2O(n) = 8T(n/8) + 3O(n) // 2번 대입 ...... // k번 대입 k+1 = log n = n x T(1) + log n x O(n) = n x O(1) + O(n log n) = O(n) + O(n log n) * 합병 정렬..

선택 정렬 구현 코드import java.util.Scanner; public class SortSelection { // 선택 정렬 public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int[] data = new int [100]; for(int i=0; i