[Coding Test] 정렬 기법

2024년 6월 17일 14 분 소요

정렬된 데이터는 더 빠르고 효율적인 검색과 분석이 가능하도록 도와준다.

이를 위해서 데이터 집합을 특정 기준에 따라 순서대로 배열하는 작업이 정렬이다.

Bubble

인접 요소 끼리 비교하여 하나씩 Swap하며 정렬을 수행하는 기법이다.

시간 복잡도

O(n^2)

간단하게 구현할 수 있지만 다른 알고리즘보다 속도가 느리다.

시간 복잡도가 O(n^2)라는 것에서 알 수 있듯이 중첩 반복문이 들어간다.

아래는 오름차순 정렬 플로우이며, 오름차순으로 정렬 시 왼쪽의 값이 오른쪽보다 크다면 위치를 swap한다.

Bubble Sort https://blog.stackademic.com/understanding-bubble-sort-with-kotlin-sorting-algorithm-2-ed72f4ee22fb

정렬 과정

비교 연산이 필요한 루프 범위를 설정.
인접 데이터와 값 비교.
swap 조건에 부합하다면 swap.
루프 범위가 끝날 때 까지 2~3을 반복.
첫 pass 즉, 루프 범위가 끝났다면 정렬된 영역은 제외한다.((j<arr.length - 1 - i))
비교 대상이 없을 때까지 1~5반복

아래의 문제로 버블 소트를 익혀보자.

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

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt();

        int[] arr = new int[N];

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

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

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

                if(arr[j] > arr[j+1]){
                    int tmp = arr[j];

                    arr[j] = arr[j+1];
                    arr[j+1] = tmp;
                }

            }

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

Selection

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

시간 복잡도

O(n^2)

구현 방법이 복잡하지만 높은 시간 복잡도를 가지고 있기에 코딩 테스트에는 잘 사용하지 않는다.

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

Slection sort https://www.hackerearth.com/practice/algorithms/sorting/selection-sort/tutorial/

과정

남은 정렬 부분에서 최솟값 혹은 최댓값을 찾는다.
남은 정렬 부분에서 가장 앞에 있는 데이터와 선택된 데이터를 swap한다.
가장 앞에 있는 데이터의 위치를 변경해(index++) 남은 정렬 부분의 범위를 축소한다.
전체 데이터 크기만큼 index가 커질 때 까지, 즉 남은 정렬 부분이 없을 때 까지 반복

아래의 문제로 선택 정렬을 익혀보자.

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

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

public class Main {

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

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String N = br.readLine();

        int[] arr = new int[N.length()];

        for(int i = 0; i<N.length(); i++) {
            arr[i] = Integer.parseInt(N.substring(i, i+1));
        }

        for(int i = 0; i < N.length(); i++){
            int max = i;
            for(int j = i+1; j < N.length(); j++){

                if(arr[max] < arr[j]){
                    max = j;
                }
            }

            if(arr[max] > arr[i]){
                int tmp = arr[i];
                arr[i] = arr[max];
                arr[max] = tmp;
            }
        }
        for(int i = 0; i< N.length(); i++){
            System.out.print(arr[i]);
        }


    }
}

Insertion

이미 정렬된 영역에서 정렬 되지 않은 데이터를 적절한 위치에 삽입하면서 정렬하는 기법이다.

시간 복잡도

O(n^2)

평균 시간 복잡도는 높지만 구현하기 쉽다.

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

Insertion sort https://medium.com/austins-software-engineering-journey/insertion-sort-ea0645cc5a23

과정

현재 index에 있는 데이터 값을 선택.
현재 선택한 데이터가 정렬된 데이터 범위에 삽입될 위치를 탐색.
삽입 위치부터 index에 있는 위치까지 shift 연산을 수행.
삽입 위치에 현재 선택한 데이터를 삽입하고 index++.
전체 데이터의 크기만큼 index가 커질 때까지, 즉 선택할 데이터가 없을 때 까지 반복한다.

적절한 삽입 위치를 탐색하는 부분은 Binary Search 등과 같은 탐색 알고리즘을 활용하면 시간 복잡도를 줄일 수 있다.

아래의 문제로 삽입 정렬을 익혀보자.

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

import java.io.BufferedReader;
import java.util.Arrays;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt(); // 수열 길이

        int[] A = new int[N]; // 숫자 배열
        int[] S = new int[N]; // 합 배열

        //수열 생성
        for(int i = 0; i < N; i++){
            A[i] = sc.nextInt();
        }

        // 삽입 정렬
        // 두 번째 요소에서부터 배열의 끝까지 반복
        for(int i = 1; i < N; i++){

            int insert_value = A[i]; // 현재 정렬할 대상의 값을 저장.
            int j = i - 1; // 현재 위치에서 이전 위치를 지정한다.

            // j에서부터 0으로, 오른쪽에서 왼쪽으로 이동하며 비교(역순)
            // 타겟 값이 이전 값보다 작다면
            // 이전 값 위치에 타겟 값을 넣기 위해 shift 연산을 수행한다.
            // A[j] > insert_value로 적절한 위치를 찾는다.
            while (j >= 0 && A[j] > insert_value) {
                A[j + 1] = A[j]; // 요소를 오른쪽으로 이동
                j--;
            }
            A[j + 1] = insert_value; // 삽입 위치에 값 저장
        }

        // 합 배열 만들기.

        // 정렬된 수열의 첫 번째 값을 초기화
        S[0] = A[0];

        for(int i = 1; i<N; i++){
            S[i] = S[i-1] + A[i];
        }

        int sum = 0;
        for(int i = 0; i < N; i++){
            sum += S[i];
        }

        System.out.println(sum);


    }
}

Quick

기준이 되는 Pivot 값을 선정하여 해당 값을 기준으로 작은 값과 큰 값으로 데이터를 분류하는 정렬 방식이다.

시간 복잡도

O(nlogn)

pivot의 선정이 시간 복잡도에 많은 영향을 미친다.

pivot을 기준으로 데이터를 2개의 집합으로 나누는 것이 핵심이다.

quick sort https://www.geeksforgeeks.org/quick-sort-in-c/

과정

데이터의 분할 기준이 될 pivot을 선정한다.
pivot을 기준으로 아래의 과정을 거처 데이터를 2개의 집합으로 분리한다.
start위치의 데이터가 pivot보다 작으면 start를 오른쪽으로 1칸 이동.
end위치의 데이터가 pivot보다 크면 end를 왼쪽으로 1칸 이동.
start에 위치한 데이터가 pivot보단 크고, end의 데이터가 pivot보다 작으면 start, end를 swap하고 start는 오른쪽, end는 왼쪽으로 1칸씩 이동.
start, end가 만날 때 까지 위의 과정을 반복.
start, end가 만난 지점의 데이터와 pivot을 비교하여 pivot이 크면 만난 지점의 오른쪽에, 작으면 만난 지점의 왼쪽에 pivot을 삽입.
분리 집합에서 다시 pivot을 선정한다.
분리 집합이 1개 이하가 될 때까지 위의 과정을 반복한다.

시간 복잡도가 O(nlogn)이기에 코딩 테스트에서도 자주 사용한다.

아래의 문제로 퀵 정렬을 익혀보자.

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

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

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());

        int[] A = new int[N];

        st = new StringTokenizer(br.readLine());

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

        quickSort(A, 0, N-1, K-1);
        System.out.println(A[K-1]);

    }

    //퀵 소트, 재귀로 활용한다.
    public static void quickSort(int[] A, int S, int E, int K){
        // Start는 End보다 작다면 비교를 할 수 있다.
        if(S < E){
            // 피봇 값을 구한다.
            int pivot = partition(A, S, E);

            if(pivot == K){
                return;
            }else if (K < pivot) {
                // K가 작으니 왼쪽 그룹만 정렬
                quickSort(A, S, pivot - 1, K);
            }else{
                // K가 크니 오른쪽 그룹만 정렬
                quickSort(A, pivot + 1, E, K);
            }
        }
    }


    //피벗 구하기
    public static int partition(int[] A, int S, int E){

        // 데이터가 2개인 경우는 바로 비교하여 정렬
        if(S + 1 == E) {
            if (A[S] > A[E]) {
                swap(A, S, E);
            }
            return E;
        }

        // 중앙 값 구하기
        int M = (S + E) / 2;
        // 구한 중앙 값을 A[0]과 바꾸기.
        swap(A,S,M);

        // 바꿨다면 첫 번째 요소가 pivot이 된다.
        int pivot = A[S];

        // 비교는 피벗 이후의 인덱스와 끝까지
        int i = S + 1;
        int j = E;

        // index 끼리 만나기 전까지
        while (i <= j){

            // end에서 왼쪽으로 이동 시 최초의 start 위치까지만
            // 그리고 pivot 보다 작은 수가 나온다면 j--
            while (j >= S + 1 && pivot < A[j]){
                j--;
            }

            // start에서 오른쪽으로 이동 시 최초의 end 위치까지만
            // pivot 보다 큰 수가 나올 때 까지 i++
            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 tmp = A[i];
        A[i] = A[j];
        A[j] = tmp;
    }
}

Merge

Divide and Conqure 즉 분할 정복 방식을 사용하여 데이터를 분할하고, 분할한 집합을 정렬한 뒤 다시 하나로 합치는 정렬 기법이다.

시간 복잡도

O(nlogn)

코딩 테스트의 정렬 관련 문제에 자주 등장한다.

Merge sort https://en.wikipedia.org/wiki/Merge_sort

두 개의 그룹을 하나로 합치면서 새로운 그룹을 만들고 이를 다른 그룹과 계속 병합하는 과정을 거쳐야한다.

그러므로 두 개의 그룹을 병합 하는 것이 알고리즘의 핵심이 될 수 있으며, 오름차순 정렬 시에는 1그룹과, 2그룹에서 가장 작은 값들을 하나씩 비교해가며 병합을 해야한다.

투 포인터의 개념을 차용하여 1그룹에서 작은 값이 발견되었다면 1그룹의 포인터를 한 칸 이동하고, 2그룹에서 발견되었다면 2그룹의 포인터를 하나씩 옯기는 방식으로 구현할 수 있다.

아래의 문제로 병합 정렬을 익혀보자.

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

import java.io.*;

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());

		    // 1부터 시작하여 편의를 주기 위해 +1과 최초 s에 1을 제공한다.
        A = new int [N+1];

        tmp = new int[N+1];

        for(int i = 1; i <= N; i++){
            A[i] = Integer.parseInt(br.readLine());
        }

        merge_sort(1, N);

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

    }

    private static void merge_sort(int s, int e){

        //현재 요소가 하나라면 더 이상 진행하지 않는다.
        if( e - s < 1){
            return;
        }

        // 그룹을 나눌 중간 위치 파악.
        int m = s + (e-s) / 2;

        //그룹을 나눈다.
        merge_sort(s, m); // 시작~중간
        merge_sort(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){

            // 양쪽 그룹의 index가 가리키는 값을 비교하여 더 작은 수를 배열에 저장.
            // 선택된 데이터 그룹의 index를 이동

            //왼쪽 그룹의 앞에 있는 값이 더 크다면
            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++;
        }

    }
}

Radix

값을 직접적으로 비교하지 않고 비교할 자릿수를 정한 다음 해당 자릿수만 비교하는 방법으로 정렬하는 기법이다.

시간 복잡도

O(kn)

k는 데이터의 자릿수를 의미한다.

기수정렬은 정렬 알고리즘 중 시간 복잡도가 가장 짧기에 데이터 개수가 너무 많을 때 활용할 수 있다.

하지만 소수에서 활용하기에는 적합하지 않다.

낮은 자릿수에서부터 높은 자리수 까지 정렬하는 LSD(Least Significant Digit)와 높은 자리수부터 낮은 자리수까지 정렬하는 MSD(Most Significant Digit)가 있다.

여기서는 LSD를 기준으로 설명할 것이다.

10진수 기준으로 선입선출의 Queue를 10개 사용하여 Bucket을 구성하고 기수의 정렬 순서대로 Bucket에 넣어준다.

하지만 Queue의 개념을 차용하여 Queue를 사용하지 않고도 배열로도 구현이 가능하다.

이후 1번 Bucket에서 부터 pop을 진행하여 정렬을 마치고 마지막 기수까지 해당 과정을 반복한다.

radix sort https://www.geeksforgeeks.org/c-program-for-radix-sort/

아래의 문제로 기수 정렬을 익혀보자.

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

import java.io.*;

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();

        //10,000의 자리수까지 비교하기 위해 max_size에 5를 준다.
        Radix_Sort(A, 5);

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

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

    //기수 정렬
    public static void Radix_Sort(int[] A, int max_size) {
        int[] output = new int[A.length];

        int jarisu = 1;

        int count = 0;

        while (count != max_size) // 최대 자리수 만큼 반복
        {
            // 값을 넣었다 빼낼 bucket
            int[] bucket = new int[10];

            // 일의 자리 부터 시작하여 jarisu에 따라 자리수 이동하기.
            for (int i = 0; i < A.length; i++) {
                bucket[(A[i] / jarisu) % 10]++; 
            }
            
            //count만으로는 어떤 위치에 값이 들어가야하는지 모르기 떄문에 합배열을 이용하여 index 계산
            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++;
        }
    }
}

Ref.

Do it! 알고리즘 코딩 테스트 - 자바 편, 이지스퍼블리싱/김종관 저

재훈맨

[Coding Test] 정렬 기법

Bubble

시간 복잡도

정렬 과정

Selection

시간 복잡도

과정

Insertion

시간 복잡도

과정

Quick

시간 복잡도

과정

Merge

시간 복잡도

Radix

시간 복잡도

참고

[Architecture] 소프트웨어 아키텍처 패턴

[Database] 데이터의 기본 탐색 기법과 구조

[Database] Database Index - 적용 part 2.

[Database] Database Index - 적용 part 1.