[Do it] 알코테 자바 6일차

05-3 삽입 정렬 (Insertion Sort)

삽입 정렬은 이미 정렬된 데이터 범위에 정렬되지 않은 데이터를 적절한 위치에 삽입하여 정렬하는 방식이다.

앞에서부터 정렬된 영역을 하나씩 확장하면서, 새로운 데이터를 올바른 위치에 끼워 넣는 방식으로 동작한다.

즉, 선택한 데이터를 현재 정렬된 데이터 범위 내에서 적절한 위치에 삽입하는 것이 핵심이다.

---

1. 삽입 정렬의 동작 원리

1. 배열의 두 번째 요소부터 시작한다.
2. 현재 값을 정렬된 왼쪽 영역과 비교한다.
3. 현재 값보다 큰 값들은 오른쪽으로 한 칸씩 이동한다.
4. 이동이 끝난 위치에 현재 값을 삽입한다.
5. 이 과정을 배열 끝까지 반복한다.

---

2. 예시 (오름차순 정렬)

초기 배열

8 5 6 2 4

1. 5를 정렬된 영역 [8]에 삽입

5 8 6 2 4

2. 6을 정렬된 영역 [5 8]에 삽입

5 6 8 2 4

3. 2를 정렬된 영역 [5 6 8]에 삽입

2 5 6 8 4

4. 4를 정렬된 영역 [2 5 6 8]에 삽입

2 4 5 6 8

5. 최종 정렬 결과

2 4 5 6 8

---

3. 삽입 정렬 특징

• 앞부분은 항상 정렬된 상태를 유지
• 현재 데이터를 올바른 위치에 삽입하면서 정렬
• 이미 거의 정렬된 배열에서는 매우 빠르게 동작
• 구현이 간단한 정렬 알고리즘

---

4. 시간 복잡도

경우	시간 복잡도
최선 (이미 정렬된 경우)	O(N)
평균	O(N²)
최악 (역순 정렬)	O(N²)

---

5. 공간 복잡도

O(1)

추가적인 메모리를 거의 사용하지 않는 제자리 정렬(In-place sort) 알고리즘이다.

---

6. 한줄 정리

-> 삽입 정렬은 이미 정렬된 부분에 새로운 데이터를 올바른 위치에 삽입하면서 정렬하는 알고리즘이다.

__[018] ATM 인출 시간 계산하기

백준 온라인 져지 11399번 https://www.acmicpc.net/problem/11399

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception {

        // 입력
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());

        int[] arr = new int[n];
        StringTokenizer st = new StringTokenizer(br.readLine());

        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        // 삽입 정렬 (오름차순)
        for (int i = 1; i < n; i++) {
            int key = arr[i];
            int j = i - 1;

            while (j >= 0 && arr[j] > key) {
                arr[j + 1] = arr[j];
                j--;
            }

            arr[j + 1] = key;
        }

        // 누적합 계산
        int sum = 0;
        int total = 0;

        for (int i = 0; i < n; i++) {
            sum += arr[i];   // 현재까지 기다린 시간
            total += sum;    // 전체 합
        }

        // 출력
        System.out.println(total);
    }
}

 

_05-4 퀵 정렬 (Quick Sort)

퀵 정렬은 기준값(Pivot)을 선정한 뒤, 해당 값보다 작은 데이터와 큰 데이터로 분류하는 과정을 반복하여 정렬하는 방식이다.

배열에서 하나의 값을 **pivot(기준값)**으로 선택하고, pivot보다 작은 값은 왼쪽으로, 큰 값은 오른쪽으로 이동시킨다. 이후 나뉜 두 영역에 대해 동일한 과정을 반복하면서 전체 배열을 정렬한다.

즉, pivot을 중심으로 데이터를 두 개의 집합으로 계속 나누면서 정렬하는 것이 핵심이다.

---

1. 퀵 정렬의 동작 원리

1. 배열에서 하나의 값을 pivot으로 선택한다.
2. pivot보다 작은 값은 왼쪽, 큰 값은 오른쪽으로 이동시킨다.
3. pivot을 기준으로 배열이 두 개의 부분 배열로 나뉜다.
4. 나뉜 부분 배열에 대해 동일한 과정을 반복한다.
5. 더 이상 나눌 수 없을 때까지 반복하면 전체 배열이 정렬된다.

---

2. 예시 (오름차순 정렬)

초기 배열

8 5 6 2 4

pivot = 8

5 6 2 4 | 8

왼쪽 배열에서 pivot = 5

2 4 | 5 | 6

정렬 결과

2 4 5 6 8

---

3. 퀵 정렬 특징

• 분할 정복(Divide and Conquer) 방식의 정렬 알고리즘
• pivot을 기준으로 배열을 두 개의 부분 배열로 나누어 정렬
• 평균적으로 매우 빠른 정렬 성능을 가짐
• 대용량 데이터 정렬에 자주 사용됨
• pivot 선택에 따라 성능 차이가 발생할 수 있음

---

4. 시간 복잡도

경우	시간 복잡도
최선	O(N log N)
평균	O(N log N)
최악	O(N²)

최악의 경우는 이미 정렬된 배열에서 pivot을 한쪽 끝 값으로 선택했을 때 발생할 수 있다.

---

5. 공간 복잡도

O(log N)

재귀 호출로 인해 추가적인 스택 공간이 사용된다.

---

6. 한줄 정리

퀵 정렬은 pivot을 기준으로 데이터를 작은 값과 큰 값으로 분할하고, 이를 반복하여 정렬하는 분할 정복 기반 알고리즘이다.

__[019] K번째 수 구하기

백준 온라인 져지 11004번 https://www.acmicpc.net/problem/11004

import java.io.*;
import java.util.*;

public class Main {

    static int[] arr;

    public static void main(String[] args) throws Exception {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        // N, K 입력
        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());

        arr = new int[N];

        // 배열 입력
        st = new StringTokenizer(br.readLine());
        for(int i = 0; i < N; i++){
            arr[i] = Integer.parseInt(st.nextToken());
        }

        // 퀵 정렬
        quickSort(0, N - 1);

        // K번째 수 출력 (0-index)
        System.out.println(arr[K - 1]);
    }

    // 퀵 정렬
    static void quickSort(int start, int end) {

        if(start >= end) return;

        int pivot = partition(start, end);

        quickSort(start, pivot - 1);
        quickSort(pivot + 1, end);
    }

    // 파티션
    static int partition(int start, int end) {

        int pivot = arr[start];
        int left = start + 1;
        int right = end;

        while(left <= right){

            while(left <= end && arr[left] <= pivot) left++;
            while(right > start && arr[right] >= pivot) right--;

            if(left > right){
                swap(start, right);
            }else{
                swap(left, right);
            }
        }

        return right;
    }

    // swap
    static void swap(int i, int j){
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}