[Coding Test] inflearn(5)

1. 버블 정렬 (Bubble sort)

버블 정렬은 두 인접한 데이터의 크기를 비교해 정렬하는 방법이다.

버블 정렬의 핵심 이론

• 간단하게 구현할 순 있지만, 시간 복잡도는 O(n^2)으로 다른 정렬 알고리즘보다 속도가 느린 편이다.
  

2. 선택 정렬 (Selection sort)

선택 정렬은 대상 데이터에서 최대나 최소 데이터를 데이터가 나열된 순으로 찾아가며 선택하는 방법이다.

선택 정렬의 핵심 이론

• 최솟값 또는 최댓값을 찾고, 남은 정렬 부분의 가장 앞에 있는 데이터와 swap하는 것이 선택정렬의 핵심이다.

• 구현 방법이 복잡하고, 시간 복잡도도 O(n^2)으로 효율적이지 않아 코딩 테스트에서는 많이 사용하지 않는다.

3. 삽입 정렬 (Insertion sort)

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

삽입 정렬의 핵심 이론

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

4. 퀵 정렬 (Quick sort)

퀵 정렬은 기준값(pivot)을 선정해 해당 값보다 작은 데이터와 큰 데이터로 분류하는 것을 반복해 정렬하는 방식이다.

퀵 정렬의 핵심 이론

• 기준값이 어떻게 선정되는지가 시간 복잡도에 많은 영향을 미치고, 평균 시간 복잡도는 O(nlogn)이며 최악의 경우에는 시간 복잡도가 O(n^2)이 된다.
• pivot을 중심으로 계속 데이터를 2개의 집합으로 나누면서 정렬하는 것이 퀵 정렬의 핵심이다.

5. 병합 정렬 (Merge sort)

병합 정렬은 분할 정복 방식을 사용해 데이터를 분할하고 분할한 집합을 정렬하며 합치는 방식이다.

병합 정렬의 핵심 이론

• 병합 정렬의 시간 복잡도는 O(nlogn)이다.

2개의 그룹을 병합하는 과정

6. 기수 정렬 (Radix sort)

기수 정렬은 값을 비교하지 않는 특이한 정렬이다.
기수 정렬은 값을 놓고 비교할 자릿수를 정한 다음 해당 자릿수만 비교한다.

기수 정렬의 핵심 이론

• 기수 정렬의 시간 복잡도는 O(kn)으로, 여기서 k는 데이터의 자릿수를 말한다.
• 기수 정렬은 10개의 큐를 이용한다. 각 큐는 값의 자릿수를 대표한다.

7. 실전 문제

수 정렬하기 (백준 2750) - 버블 정렬 풀이

import java.util.Scanner;

public class P2750_수정렬하기 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int[] num = new int[N];
        for (int i = 0; i < N; i++) num[i] = sc.nextInt();
        for (int j = 0; j < N - 1; j++) {
            int swap = 0;
            for (int i = 0; i < N - 1 - j; i++) {
                if (num[i] > num[i + 1]) {
                    int hap = num[i + 1];
                    num[i + 1] = num[i];
                    num[i] = hap;
                    swap++;
                }
            }
            if (swap == 0) break;
        }
        for (int i = 0; i < N; i++) System.out.println(num[i]);
    }
}

---

소트인사이드 (백준 1427) - 선택 정렬 풀이

import java.util.Scanner;

public class P1427_소트인사이드 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String str = sc.next();
        int[] in = new int[str.length()];
        for (int i = 0; i < in.length; i++)
            in[i] = Integer.parseInt(str.substring(i, i + 1));

        for (int i = 0; i < in.length; i++) {
            int max = i;
            for (int j = i + 1; j < in.length; j++) {
                if (in[max] < in[j]) max = j;
            }
            if (in[i] < in[max]) {
                int temp = in[i];
                in[i] = in[max];
                in[max] = temp;
            }
        }
        for (int i = 0; i < in.length; i++)
            System.out.printf("%d", in[i]);
    }
}

수 정렬하기 (백준 2750) - 삽입 정렬 풀이

import java.util.Scanner;

public class P2750_수정렬하기 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int[] num = new int[N];
        for (int i = 0; i < N; i++) num[i] = sc.nextInt();
        int key;
        for (int i=1; i<N; i++){
            int j;
            key = num[i];
            for (j=i-1; j>=0; j--){
                if(num[j] > key)
                    num[j+1] = num[j];
                else break;
                num[j] = key;
            }
        }
        for (int i=0; i<N; i++)
            System.out.println(num[i]);
    }
}

---

K번째 수 (백준 11004) - 퀵 정렬 풀이

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

public class NOTE01 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());


        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());
        int[] arr = new int[N];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) arr[i] = Integer.parseInt(st.nextToken());
        quickSort(arr, 0, N - 1, K);
        bw.write(arr[K - 1] + "");


        bw.flush();
        bw.close();
        br.close();
    }

    public static void quickSort(int[] arr, int L, int R, int K) {
        if (L >= R) return;
        int pi = partition(arr, L, R);
        if (pi + 1 == K) return;

        quickSort(arr, L, pi - 1, K);
        quickSort(arr, pi + 1, R, K);
    }

    public static int partition(int[] arr, int L, int R) {
        int pivot = arr[L];
        int i = L;
        int j = R;
        while (i < j) {
            while (pivot < arr[j]) j--;
            while (i < j && pivot >= arr[i]) i++;
            int temp = arr[j];
            arr[j] = arr[i];
            arr[i] = temp;
        }
        arr[L] = arr[i];
        arr[i] = pivot;
        return i;
    }
}

---

K번째 수 (백준 11004) - 병합 정렬 풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class P11004_K번째수2 {
    static int N;
    static int K;
    static int[] sorted;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
        int[] A = new int[N];
        sorted = new int[N];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) A[i] = Integer.parseInt(st.nextToken());
        mergeSort(A, 0, N - 1);
        System.out.println(A[K - 1]);
    }

    static void merge(int[] a, int m, int middle, int n) {
        int i = m;
        int j = middle + 1;
        int k = m;

        while (i <= middle && j <= n) {
            if (a[i] <= a[j]) {
                sorted[k] = a[i];
                i++;
            } else {
                sorted[k] = a[j];
                j++;
            }
            k++;
        }
        if (i > middle) {
            for (int t = j; t <= n; t++) {
                sorted[k] = a[t];
                if ( k <= N-1) k++;
            }
        } else {
            for (int t = i; t <= middle; t++) {
                sorted[k] = a[t];
                if ( k <= N-1) k++;
            }
        }
        for (int t = m; t <= n; t++) {
            a[t] = sorted[t];
        }
    }

    static void mergeSort(int[] a, int m, int n) {
        if (m < n) {
            int middle = (m + n) / 2;
            mergeSort(a, m, middle);
            mergeSort(a, middle + 1, n);
            merge(a, m, middle, n);
        }
    }
}

---