[Do it! 알고리즘 코딩테스트 - 자바 편] 05. 정렬

정렬 알고리즘들과 정의

정렬 알고리즘	정의
버블	데이터끼리 인접 요소끼리 비교하고, swap 연산을 수행하며 졍렬하는 방식
선택	대상에서 가장 크거나 작은 데이터를 찾아 선택하는 과정을 반복하면서 정렬하는 방식
삽입	대상을 선택해 정렬된 영역에서 선택 데이터의 적절한 위치를 찾아 삽입하면서 정렬하는 방식
퀵	pivot 값을 선정해 해당 값을 기준으로 정렬하는 방식
병합(합병)	이미 정렬된 부분 집합들을 효율적으로 병합해 전체를 정렬하는 방식
힙	최대 힙 트리나 최소 힙 트리를 구성해 정렬을 하는 방식 (내림차순 정렬-최소 힙 / 오름차순 정렬-최대 힙)
기수	데이터의 자릿수를 바탕으로 비교해 데이터를 정렬하는 방식

 

05-1. 버블 정렬

버블 정렬: 두 인접한 데이터의 크기를 비교해 정렬. 시간 복잡도 O(n^2)으로 다른 알고리즘보다 속도가 느림.

루프를 돌면서 인접한 데이터 간에 swap 연산을 해 정렬.

만약 특정한 루프의 전체 영역에서 swap이 한 번도 발생하지 않았다면 데이터가 모두 정렬되었다는 뜻, 프로세스를 종료해도 된다.

---

[2750번: 수 정렬하기] / 브2

c++로 풀었었어서 생략

#include<iostream>
#include<algorithm>
using namespace std;

int main()
{
    int N;
    cin >> N;
    int* arr = new int[N];
    for (int i = 0; i < N; i++) {
        cin >> arr[i];
    }
    sort(arr, arr + N);
    for (int i = 0; i < N; i++) {
        cout << arr[i] << endl;
    }
    delete[] arr; // 메모리 해제
    return 0;
}

 

직접 구현한다면

 

for(int i=0; i<N-1; i++) {

    for(int j=0; j<n-1-i; j++){

        if(A[j]>A[j+1){

            int temp=A[j];

            A[j]=A[j+1];

            A[j+1]=temp;

        }

    }

}

 

 

[1377번: 버블 소트] / 골2

문제에서 c++ 코드를 제공해주었길래 그대로 출력하도록 했는데, 시간초과가 나서 책을 보고 다시 풀었다...

버블 정렬에서는 한 번의 루프마다 각 원소가 최대 한 칸씩만 왼쪽으로 이동할 수 있다. 따라서 원소가 처음 위치에서 얼마나 멀리 왼쪽으로 이동했는지를 보면, 실제 버블 정렬이 완료되기까지 필요한 최소 루프 횟수를 구할 수 있다.
실제 정렬 자체는 평균 시간 복잡도 O(n log n)인 Arrays.sort()로 빠르게 수행하고,

버블 정렬이 완료되는 최소 루프 횟수는 각 원소의 (정렬 전 인덱스 − 정렬 후 인덱스) 값 중 최댓값에 1을 더해 계산한다.

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

public class Main
{
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[][] A = new int[n][2];
        for(int i=0; i<n; i++) {
            A[i][0] = i; // 정렬 전 인덱스
            A[i][1] = Integer.parseInt(br.readLine()); // 값
        }
        Arrays.sort(A, (a, b) -> {
            if(a[1]!=b[1]) return Integer.compare(a[1], b[1]); // 값 기준 정렬
            return Integer.compare(a[0], b[0]);
        });
        int max=0;
        for(int i=0; i<n; i++) {
            if (max < A[i][0]-i) 
                max = A[i][0]-i;
        }
        System.out.println(max+1);
    }
}

    // 문제에서 제공한 코드, 그러나 이렇게 실행하면 시간초과
    // bool changed = false;
    // for (int i=1; i<=N+1; i++) {
    //     changed = false;
    //     for (int j=1; j<=N-i; j++) {
    //         if (A[j] > A[j+1]) {
    //             changed = true;
    //             swap(A[j], A[j+1]);
    //         }
    //     }
    //     if (changed == false) {
    //         cout << i << '\n';
    //         break;
    //     }
    // }

---

05-2. 선택 정렬

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

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

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

---

[1427번: 소트인사이드] / 실5

예전에 계수 정렬(Counting Sort)로 푼 적 있는 문제였다.

(입력 문자열(str)의 각 숫자 빈도를 numbers[10] 배열에 저장하고, 9부터 0까지 역순으로 출력하므로 내림차순 정렬)

import java.util.Scanner;

public class Main {
    public static void solution() throws Exception {
        Scanner sc = new Scanner(System.in);
        String str = sc.next();
        int[] numbers = new int[10];

        for (int i = 0; i < str.length(); i++) {
            int n = str.charAt(i) - '0'; // 0~9
            numbers[n]++;
        }
        for (int i = 9; i >= 0; i--) {
            for (int j = 0; j < numbers[i]; j++) {
                System.out.print(i);
            }
        }
    }

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

 

 

선택 정렬로 푼다면

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String str = sc.next();
        int n = str.length();
        int[] A = new int[n];

        for (int i = 0; i < n; i++) {
            A[i] = str.charAt(i) - '0';
        }

        // 선택 정렬 (내림차순)
        for (int i = 0; i < n - 1; i++) {
            int maxIdx = i;
            for (int j = i + 1; j < n; j++) {
                if (A[j] > A[maxIdx]) {
                    maxIdx = j;
                }
            }
            // swap
            int tmp = A[i];
            A[i] = A[maxIdx];
            A[maxIdx] = tmp;
        }

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

---

05-3. 삽입 정렬

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

- 평균 시간 복잡도는 O(n^2)으로 느린 편,구현하기 쉬움.

삽입 정렬의 핵심 이론: 선택 데이터를 현재 정렬된 데이터 범위 내에서 적절한 위치에 삽입.

적절한 삽입 위치 탐색하는 데 이진 탐색을 사용하면 시간복잡도를 줄일 수 있다.

---

[11399번: ATM] / 실4

c++로, 정렬 후 누적합을 구하는 방식으로 풀었었다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int solution(int n, int times[]) {
    // 정렬
    sort(times, times + n);
    int sum = 0;
    int curr = 0;
    for (int i = 0; i < n; i++) {
        curr += times[i];
        sum += curr;
    }
    return sum;
}


int main()
{
    int n;
    int times[1000];
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> times[i];
    }
    cout << solution(n, times);
}

 

sort(times, times + n); 이 부분을 삽입 정렬 코드로 교체한다면 아래와 같이 된다.

// 삽입 정렬 (오름차순)
for (int i = 1; i < n; i++) {
    int key = times[i];
    int j = i - 1;
    while (j >= 0 && times[j] > key) {
        times[j + 1] = times[j];
        j--;
    }
    times[j + 1] = key;
}

---

05-4. 퀵 정렬

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

- 기준값을 어떻게 선정하는지가 시간복잡도에 많은 영향을 미침. 평균적인 시간 복잡도는 O(nlogn).

퀵 정렬의 핵심 이론: pivot을 중심으로 계속 데이터를 2개의 집합으로 나누면서 정렬한다.

---

[11004번: K번째 수] / 실5

지난번에는 정렬을 직접 구현하지 않고 sort()를 사용했다.

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

public class Main {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] nk = br.readLine().split(" ");
        int n = Integer.parseInt(nk[0]);
        int k = Integer.parseInt(nk[1]);
        int[] arr = new int[n];
        String[] numbers = br.readLine().split(" ");
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(numbers[i]);
        }
        Arrays.sort(arr);
        System.out.println(arr[k-1]);
    }
}

 

퀵 정렬을 직접 구현한다면 다음과 같이 풀 수 있다. (문제집 코드)

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

public class Main {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] nk = br.readLine().split(" ");
        int n = Integer.parseInt(nk[0]);
        int k = Integer.parseInt(nk[1]);
        int[] arr = new int[n];
        String[] numbers = br.readLine().split(" ");
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(numbers[i]);
        }
        Arrays.sort(arr);
        System.out.println(arr[k-1]);
    }
    
    public static void quickSort(int[] A, int S, int E, int K){
        if (S<E) {
            int pivot=partition(A, S, E);
            
            if (pivot==K) {
                return;
            } else if (K<pivot) {
                quickSort(A, S, pivot-1, K);
            } else {
                quickSort(A, pivot+1, E, K);
            }
        }
    }
    
    public static int partition(int[] A, int S, int E){
        if(S+1==E){
            if(A[S]>A[E]) swap(A, S, E);
            return E;
        }
        int M = (S+E)/2;
        swap(A, S, M);
        int pivot=A[S];
        int i=S+1;
        int j=E;
        while (i<=j) {
            while (j>=S+1 && pivot<A[j]) {
                j--;
            }
            while (i<=E && pivot>A[i]) {
                i++;
            }
            if (i<=j) {
                swap(A, i++, j--);
            }
        }
        A[S]=A[j];
        A[j]=pivot;
        return j;
    }
    
    public static void swap(int[] A, int i, int j){
        int temp=A[i];
        A[i]=A[j];
        A[j]=temp;
    }
}

---

05-5. 병합 정렬

병합 정렬: 분할 정복(divide and conquer) 방식을 사용해 (1) 데이터를 분할하고 (2) 분할한 집합을 정렬하며 합치는 알고리즘.

- 시간복잡도 평균값 O(nlogn).

병합 정렬의 핵심 이론: (1) 가장 작은 데이터 집합으로 분할 (2) 2개씩 그룹을 합치면서 오름차순 정렬 반복

2개의 그룹을 병합하는 과정: 투 포인터 개념을 사용해 왼쪽, 오른쪽 그룹을 병합한다.

- 왼쪽 포인터와 오른쪽 포인터의 값을 비교하여, 작은 값을 결과 배열에 추가하고 포인터를 오른쪽으로 1칸 이동시킨다.

---

[2751번: 수 정렬하기 2] / 실5

예전에는 그냥 sort()로 했었는데 병합 정렬을 구현하면 다음과 같이 할 수 있다. (문제집 코드)

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class Main {
  public static int[] A, 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());
    A = new int[N + 1];
    tmp = new int[N + 1];
    for (int i = 1; i <= N; i++) {
      A[i] = Integer.parseInt(br.readLine());
    }
    mergeSort(1, N); // 병합정렬 수행하기
    for (int i = 1; i <= N; i++) {
      bw.write(A[i] + "\n");
    }
    bw.flush();
    bw.close();
  }

  private static void mergeSort(int s, int e) {
    if (e - s < 1)
      return;
    int m = s + (e - s) / 2;
    // 재귀함수 형태로 구현
    mergeSort(s, m);
    mergeSort(m + 1, e);
    for (int i = s; i <= e; i++) {
      tmp[i] = A[i];
    }
    int k = s;
    int index1 = s;
    int index2 = m + 1;
    while (index1 <= m && index2 <= e) { // 두 그룹을 Merge 해주는 로직
      if (tmp[index1] > tmp[index2]) {
        A[k] = tmp[index2];
        k++;
        index2++;
      } else {
        A[k] = tmp[index1];
        k++;
        index1++;
      }
    }
    // 한쪽 그룹이 모두 선택된 후 남아있는 값 정리하기
    while (index1 <= m) {
      A[k] = tmp[index1];
      k++;
      index1++;
    }
    while (index2 <= e) {
      A[k] = tmp[index2];
      k++;
      index2++;
    }
  }
}

 

 

[1517번: 버블 소트] / 플5

 

N개의 수로 이루어진 수열 A[1], A[2], …, A[N]이 있다. 이 수열에 대해서 버블 소트를 수행할 때, Swap이 총 몇 번 발생하는지 알아내는 프로그램을 작성하시오.
버블 소트는 서로 인접해 있는 두 수를 바꿔가며 정렬하는 방법이다. 예를 들어 수열이 3 2 1 이었다고 하자. 이 경우에는 인접해 있는 3, 2가 바뀌어야 하므로 2 3 1 이 된다. 다음으로는 3, 1이 바뀌어야 하므로 2 1 3 이 된다. 다음에는 2, 1이 바뀌어야 하므로 1 2 3 이 된다. 그러면 더 이상 바꿔야 할 경우가 없으므로 정렬이 완료된다.

 

아까 문제와 마찬가지로, 제목이 버블 정렬이지만 버블 정렬로 풀면 시간 초과가 나는 문제. (N 최대 범위 500,000 -> O(nlogn) 필요)

병합 정렬을 이용해야 한다. 두 그룹을 병합하는 과정에 버블 정렬의 swap이 쓰인다.

 

마지막 병합 전의 데이터 [ 24 32 42 60 ] [ 5 15 45 90 ] 를 생각하자.

최종 정렬된 데이터는 [ 5 15 24 32 42 45 60 90 ].

5는 앞 그룹의 4개 데이터를 제치므로 버블 정렬에서 swap을 4번 하는 것과 동일하다.

45는 앞 그룹의 1개 데이터를 제치므로 버블 정렬에서 swap을 1번 하는 것과 동일하다.

 

병합 정렬을 동일하게 진행하는데, 정렬 과정에서 index가 이동한 거리를 result에 저장하자.

각 그룹을 정렬하는 과정에서 원소가 앞으로 이동한 거리만큼 result에 더하기.

 

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

public class Main {
    static int[] A, tmp;
    static long result;
  
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        A = new int[n+1];
        tmp = new int[n+1];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i=1; i<=n; i++) {
            A[i] = Integer.parseInt(st.nextToken());
        }
        result = 0;
        mergeSort(1, n);
        System.out.println(result);
    }
    
    private static void mergeSort(int s, int e) { 
        if (e-s < 1)
            return;
        int m = s + (e-s)/2;
        //재귀함수 (왼쪽, 오른쪽)
        mergeSort(s, m); 
        mergeSort(m+1, e);
        
        for (int i=s; i<=e; i++) {
            tmp[i] = A[i];
        }
        int k = s; // 병합 결과를 A에 저장하기위한 위치 인덱스
        int index1 = s; // 왼쪽 그룹의 현재 원소 위치
        int index2 = m + 1; // 오른쪽 그룹의 현재 원소 위치
        // 병합 로직 (작은 값을 A[k]에 넣으며 병합)
        while (index1 <= m && index2 <= e) {
            if (tmp[index1] > tmp[index2]) { // 뒤쪽 데이터 값이 작다면 역전 발생
                A[k] = tmp[index2];
                result += (index2 - k); // 오른쪽 원소가 왼쪽 원소 몇 개를 앞질렀는지
                k++;
                index2++;
            } else {
                A[k] = tmp[index1];
                k++;
                index1++;
            }
        }
        // 두 부분 중 한 쪽이 먼저 소진되었을 때, 남은 원소 병합
        while (index1 <= m) {
            A[k] = tmp[index1];
            k++;
            index1++;
        }
        while (index2 <= e) {
            A[k] = tmp[index2];
            k++;
            index2++;
        }
    }
}

---

05-6. 기수 정렬

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

- 시간복잡도: O(kn). // k: 자릿수. 시간복잡도가 가장 짧은 정렬임.

기수 정렬의 핵심 이론: 10개의 큐를 이용. 각 큐는 값의 자릿수를 대표함.

 

기수 정렬 수행 방식

원본 배열: 16 80 18 77 03 24 88 23

(1) 일의 자릿수 기준으로 배열 원소를 큐에 집어넣는다. 그런 다음 0번째 큐부터 9번째 큐까지 pop을 진행한다.

-> 결과: 90 03 23 24 16 77 18 88

(2) 이어서 십의 자릿수를 기준으로 같은 과정을 진행한다.

(3) 마지막 자릿수를 기준으로 정렬할 때까지 앞의 과정을 반복.

 

일반적인 기수 정렬은 우선순위 큐를 사용해 비교적 간단하게 구하는 방법이 있지만, 시간 복잡도를 느리게 하는 요소가 있어 구간 합을 이용하는 것이 더욱 효율적이다.

---

[10989번: 수 정렬하기 3] / 브1

이전에는 계수 정렬로 풀었었다.

기수 정렬로는 다음과 같이 풀이할 수 있다.

import java.io.*;

public class Main {
    static int[] A;
    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); //수의 범위가 <=10000
        for (int i = 0; i < N; i++) {
            bw.write(A[i] + "\n");
        }
        bw.flush();
        bw.close();
    }

    private static void radixSort(int[] A, int maxSize) {
        int[] output = new int[A.length];
        int digit = 1;
        int count = 0;
        while (count != maxSize) { // 최대 자리수 만큼 반복
            int[] bucket = new int[10];
            for (int i = 0; i < A.length; i++) {
                bucket[(A[i] / digit) % 10]++; // 일의 자리 부터 시작
            }
            for (int i = 1; i < 10; i++) { // 합배열을 이용하여 index 계산
                bucket[i] += bucket[i - 1];
            }
            for (int i = A.length - 1; i >= 0; i--) { // 현재 자리수 기준으로 정렬
                output[bucket[(A[i] / digit % 10)] - 1] = A[i];
                bucket[(A[i] / digit) % 10]--;
            }
            for (int i = 0; i < A.length; i++) {
                A[i] = output[i]; // 다음 자리 수 이동을 위해 현재 자리수 기준 정렬 데이터 저장
            }
            digit *= 10; // 자리수 증가
            count++;
        }
    }
}

bucket 배열로 현재 자리를 기준으로 정렬하는 방식 잘 확인하기.