정렬 관련 문제 모음!(버블,선택,삽입,퀵,병합,기수)

1. 버블 정렬

Bubble Sort는 두 인접한 데이터의 크기를 비교해 정렬하는 방법
-> 간단하게 구현가능하지만 시간복잡도는 O(N^2)으로 느린편
-> swap 연산을 통해 정렬 함

코드 예시

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

public class Main {
    static int[] arr;
    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        arr = new int[N];

        for(int i = 0; i < N; i++){
            arr[i] = sc.nextInt();
        }

        for(int i = 0; i < N-1; i++){
            for(int j = 0; j < N-1-i; j++){
                if(arr[j] > arr[j+1]){
                    swap(j,j+1);
                }
            }
        }

        for(int i : arr){
            System.out.println(i);
        }


    }
    private static void swap(int index1, int index2){
        int temp = arr[index1];
        arr[index1] = arr[index2];
        arr[index2] = temp;
    }
}

---

2. 선택 정렬

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

public class Main {
    static int[] arr;
    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner(System.in);
        String str = sc.next();
        int[] A = new int[str.length()];
        for(int i = 0; i < str.length(); i++){
            A[i] = Integer.parseInt(str.substring(i,i+1));
        }

        for(int i = 0; i < str.length(); i++){
            int max = i;
            for(int j = i+1; j < str.length();j++){
                if(A[j] > A[max]){
                    max = j;
                }
            }
            if(A[i] < A[max]){
                int temp = A[max];
                A[max] = A[i];
                A[i] = temp;
            }
        }

        for(int i : A){
            System.out.print(i);
        }
    }
}

---

3. 삽입 정렬

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

	for(int i = 1; i < N; i++){
            int insert_point = i;
            int insert_value = arr[i];

            for(int j = i-1; j >= 0; j--){
                if(arr[j] < arr[i]){
                    insert_point = j+1;
                    break;
                }

                if(j == 0){
                    insert_point = 0;
                }
            }

            for(int j = i; j > insert_point; i--){
                arr[j] = arr[j-1];
            }

            arr[insert_point] = insert_value;
        }

---

4. 퀵 정렬

pivot을 선정해 해당 값보다 작은 데이터와 큰 데이터로 분류하는 것을 반복해 정렬하는 알고리즘
-> 기준 값 선정에 따라 시간복잡도에 영향(운이 나쁜 경우)
-> 평균 nlogn, 최악 n^2

1. 데이터를 분할하는 pivot을 설정

2. pivot을 기준으로 아래 과정 거침
   2-1 start가 가리키는 데이터가 pivot이 가리키는 데이터보다 작으면 start를 오른쪽으로 1칸 이동
   2-2 end가 가리키는 데이터가 pivot이 가리키는 데이터보다 크면 end를 왼쪽으로 한칸 이동
   2-3 start가 가리키는 데이터가 pivot이 가리키는 데이터 보다 크고, end가 가리키는 데이터가 pivot이 가리키는 데이터 보다 작으면 start,end의 데이터를 swap하고 start을 오른쪽, end는 왼쪽으로 한칸씩 이동
   2-4 start와 end가 만날떄까지 1~3 과정 반복
   2-5 start와 end가 만나면 만난 지점에서 가리키는 데이터와 pivot이 가리키는 데이터를 비교하여 pivot이 가리키는 데이터가 크면 만난 지점의 오른쪽에 , 작으면 만난 지점의 왼쪽에 pivot이 가리키는 데이터 삽입

3. 분리 집합에서 각각 다시 pivot을 선정

4. 분리 집합이 1개 이하가 될떄까지 1~3 반복

관련 문제 예시

https://www.acmicpc.net/problem/11004

최대 범위가 5,000,000 이므로 O(nlogn)의 시간 복잡도로 정렬을 수행해야 함

데이터가 대부분 정렬되어 있는 경우에는 앞쪽에 있는 수를 pivot으로 선택하면 불필요한 연산이 만아짐
-> 여기선 배열의 중간 위치를 피봇으로 설정할 것!

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());
        st = new StringTokenizer(br.readLine());

        int[] arr = new int[N];
        for(int i = 0; i < N; i++){
            arr[i] = Integer.parseInt(st.nextToken());
        }
        quickSort(arr,0,N-1,K-1);
        System.out.println(arr[K-1]);
    }

    public static void quickSort(int[] arr, int start, int end, int target){
        if(start < end){
            int pivot = partition(arr,start,end);
            if(pivot == target){
                return;
            }else if(target < pivot){
                quickSort(arr,start,pivot-1,target);
            }else{
                quickSort(arr,pivot+1, end, target);
            }
        }
    }

    public static int partition(int[] arr, int start, int end){
        if(start + 1 == end){
            if(arr[start] > arr[end]){
                swap(arr,start,end);
            }
            return end;
        }

        int M = (start + end) / 2;
        swap(arr,start,M); // 중앙값을 처음으로 이동
        int pivot = arr[start];
        int i = start + 1, j = end;
        while(i <= j){
            while(pivot < arr[j] && j > 0){
                j--;
            }
            while(pivot > arr[i] && i < arr.length-1){
                i++;
            }
            if(i <= j){
                swap(arr,i++,j--);
            }
        }
        // i == j 피벗의 값을 양쪽으로 분리한 가운데에 오도록 설정하기
        arr[start] = arr[j];
        arr[j] = pivot;
        return j;
    }

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

---

5.병합 정렬

Divide and conquer방식을 사용해 데이터를 분할하고, 분할한 집합을 정렬하며 합치는 알고리즘
-> 평균값 nlogn

전체는 정렬이 안되어도 부분부분은 오름차순으로 정렬이 되어있음

부분 정렬 한번에 N번의 데이터 Access 필요(투포인터로 접근), logn(위 예시의 경우는 3)만큼 일어남

두개의 그룹을 병합하는 원리를 꼭 숙지해야 함

한쪽 그룹이 다써지면, 나머지는 그대로 붙임

https://www.acmicpc.net/problem/2751

public class Main {
    static int[] arr,tmp;
    public static long result;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int N = Integer.parseInt(br.readLine());
        arr = new int[N+1];
        tmp = new int[N+1]; // 정렬할때 사용할 임시 배열
        for(int i = 1; i <= N; i++){
            arr[i] = Integer.parseInt(br.readLine());
        }
        mergeSort(1,N);
        for(int i = 1; i <= N; i++){
            bw.write(arr[i] + "\n");
        }
        bw.flush();
        bw.close();
    }

    private static void mergeSort(int start, int end){
        if(end - start < 1){
            return;
        }

        int middle = (start) + (end-start) / 2;

        mergeSort(start,middle);
        mergeSort(middle+1, end);

        for(int i = start; i <= end; i++){
            tmp[i] = arr[i];
        }

        int k = start;
        int index1 = start; int index2 = middle+1;
        while(index1 <= middle && index2 <= end){
            // 두 그룹을 병합하는 로직
            if(tmp[index1] > tmp[index2]){
                arr[k] = tmp[index2];
                k++; index2++;
            }else{
                arr[k] = tmp[index1];
                k++; index1++;
            }
        }

        while(index1 <= middle){
            arr[k] = tmp[index1];
            k++; index1++;
        }

        while(index2 <= end){
            arr[k] = tmp[index2];
            k++; index2++;
        }
    }
}

---

6. 기수 정렬

기수 정렬은 값을 비교하지 않는 특이한 정렬
-> 값을 비교할 자릿수를 정한 다음 해당 자릿수만 비교
-> 시간 복잡도는 O(kn) -> 여기서 k는 데이터의 자릿수를 의미

데이터 갯수는 크나, 수의 범위가 좁은 경우 ex)0~9999(자릿수 4개)
-> N이 100만이면 400만 연산으로 해결 가능

public class Main {

    public static int[] A;
    public static long result;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int N = Integer.parseInt(br.readLine());
        A = new int[N];

        for(int i = 0; i < N; i++){
            A[i] = Integer.parseInt(br.readLine());
        }
        br.close();
        RadixSort(A,5);

        for(int i = 0; i < N; i++){
            bw.write(A[i] + "\n");
        }
        bw.flush();
        bw.close();
    }

    private static void RadixSort(int[] A, int maxDigit){
        int[] output = new int[A.length];
        int jarisu = 1; int count = 0;

        while(count != maxDigit){
            int[] bucket = new int[10];
            for(int i = 0; i < A.length; i++){
                bucket[(A[i] / jarisu) % 10]++;
            }
            for(int i = 1; i < 10; i++){
                bucket[i] += bucket[i-1]; // 합 배열을 통해 인덱스 계산
            }
            for(int i = A.length-1; i>= 0; i--){
                // 현재 자릿수를 기준으로 정렬
                output[bucket[(A[i]/jarisu % 10)]-1] = A[i];
                bucket[(A[i] / jarisu) % 10]--;
            }
            for(int i = 0; i < A.length; i++){
                // 다음 자릿수를 이동하기 위해 현재 자릿수 기준 정렬 데이터 저장하기
                A[i] = output[i];
            }

            jarisu = jarisu * 10;
            count++;
        }
    }
}

---