[알고리즘] 정렬(버블, 선택, 삽입) 알고리즘 (1)

그놈의 정렬

알고리즘을 공부하며 정말 많이 찍먹하였던 정렬 알고리즘. 그만큼 중요하다는 뜻이겠지만,

이제는 그 끝 마무리를 하려한다.

 

정렬은 데이터를 정해진 기준에 따라 배치해 의미 있는 구조로 재설정하는 것을 의미한다.

 

그렇다면 왜 중요한 것인가?

 

결국은 "효율성"이다.

시간 복잡도가 작을 수록 더 빠르고 효과적인 프로그램을 만들기 쉽다.

정렬에 대한 알고리즘은 이러한 효율성을 증진시키기 위해, 수 많은 똑똑한 사람들이 만들어 낸 것이다.

 

조금은 과장일 지라도 정렬에 대한 알고리즘을 제대로 사용할 줄 안다면 코딩 좀 하는 개발자가 될 수 있을 것이라 생각한다.

 

 

정렬의 종류

 

버블 : 데이터의 인접 요소를 비교하고, swap 연산을 수행하며 정렬
선택 : 대상에서 가장 크거나 작은 데이터를 찾아가 선택하며 정렬
삽입 : 대상을 선택하여, 적절한 위치에 삽입
퀵 : pivot 값을 선정해 해당 값 기준으로 정렬
병합 : 이미 정렬된 부분 집합들을 효율적으로 병합
기수 : 데이터의 자릿수를 비교해 데이터를 정렬

 

크게 정렬 알고리즘의 종류로 위와 같이 6개로 나눈다.

이번 포스팅에서는 비 효율적인 정렬 알고리즘이나 때에 따라 사용할 곳이 있는 "버블", "선택", "삽입" 알고리즘에 대해 사용한다.

 

 

 

 

 

버블 정렬

 

버블 정렬은 우리가 생각할 수 있는 가장 쉬운 정렬 알고리즘이다. 인접한 요소를 비교하고, swap을 진행하는 것.

코드의 구조 또한 간단하여 몇 번 보다 보면 바로 작성할 정도이다.

 

예시로 백준 2750번 문제를 살펴보자.

 

2750번: 수 정렬하기

 

 

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(bf.readLine());

        int[] A = new int[n];

        for(int i=0; i<n; i++) {
            A[i] = Integer.parseInt(bf.readLine());
        }

        // 정렬 결과 출력
        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;
                }
            }
        }

        for(int a : A) {
            System.out.println(a);
        }


    }
}

 

n개의 요소가 있으므로, 비교 자체는 n-1번 진행한다는 것을 기억해 두자.

 

단, 버블 정렬은 O(n^2)의 비효율적인 시간 복잡도를 지닌다. 입력 값의 사이즈와 시간 제한을 꼭 고려해야한다.

만약 시간 제한이 1초인 경우에는 사용하지 않는 것을 추천한다.

 

 

 

 

 

 

선택 정렬

 

선택 정렬은 데이터 요소들 중에서 최대 혹은 최소 데이터를 선택하여 사용한다. 하지만, 구현 방법이 복잡하고 시간 복잡도도 O(n^2)으로 효율적이지 않다. 따라서 코딩 테스트에서는 사용하지 않으나, 왜 사용하지 않는지는 알아야 하므로 문제를 통해 그 이유를 살펴보자.

 

백준 1427번 문제를 참고하였다.

 

1427번: 소트인사이드

 

 

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

public class Main {
    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[i];
                A[i] = A[Max];
                A[Max] = temp;
            }
        }

        for(int i=0; i<str.length(); i++) {
            System.out.print(A[i]);
        }


    }
}

 

천천히 읽어보면, 정렬을 위해서 Max(혹은 Min) 값을 찾아야 함을 알 수 있다.

 

그리고, 제일 처음 인덱스로 부터 그 Max혹은 Min값을 차례대로 넣어 정렬하는 방식이다.

 

 

 

 

 

삽입 정렬

 

삽입 정렬은 정렬된 데이터 범위에 정렬되지 않은 데이터를 적절히 삽입하여 넣는 방법을 말한다.

 

이 알고리즘은 평균 시간 복잡도가 O(n^2)으로 느린 편이나 구현하기 쉽다는 장점이 있다.

 

 

예시 문제로는 백준 11399번 문제를 참고하자.

 

11399번: ATM

 

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

public class Main {
    public static void main(String[] args) throws IOException {
        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=0; i<n; i++) {
            int insert_point = i;
            int insert_value = A[i];
            for(int j=i-1; j>=0; j--) {
                if(A[j] < A[i]) {
                    insert_point = j+1;
                    break;
                }
                if (j == 0) {
                    insert_point = 0;
                }
            }
            for(int j = i; j > insert_point; j--) {
                A[j] = A[j-1];
            }
            A[insert_point] = 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 = sum+ S[i];
        }
        System.out.println(sum);


    }
}

 

 

해당 문제는 정렬 이외에도 그리디 알고리즘, 합 배열 공식이 사용되었다.

그리디 알고리즘은 당장의 최선의 선택이 최고의 선택이라고 여기는 알고리즘이다.

 

문제 상황에서 가장 적게 인출하는 사람을 앞에 두는 것이 최고의 선택이 되므로 그리디 알고리즘을 사용하는데 적합하다고 할 수 있다.

 

코드를 보면 알 수 있듯이, 정렬 되어 있는 부분을 탐색하며 삽입 위치를 찾는다.

그리고 삽입 위치가 위치가 선정되었다면, 삽입 위치 이후의 요소들부터 기존의 삽입 대상 위치까지 하나씩 옮겨주어야 한다.

 

삽입 할 때에는 위 처럼 그 이후의 요소들에 대해 하나씩 당겨주어야 한다는 번거로움이 있는 듯 하다.

 

 

 

Reference

- Do it! 코딩 테스트 - 기초 편