선택정렬(Selection Sort)

선택정렬(Selection Sort)

정렬 알고리즘은 데이터를 특정한 기준에 따라 순서대로 나열한 것을 말한다. 프로그램에서 데이터를 가공할 떄 오름차순이나 내림차순 등 대부분 어떤 식으로든 정렬해 사용하는 경우가 많아서 가장 많이 사용되는 알고리즘이다. 데이터를 정렬하면 이진탐색(Binary Search)이 가능하다.

 

선택 정렬은 가장 원시적인 방법으로 컴퓨터가 데이터를 정렬할때를 생각해보면된다. 데이터가 무작위로 여러가지 있을 때 데이터 중에서 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸고, 그 다음 작은 데이터를 선택해 앞에서 두번째 데이터와 바꾸는 과정을 반복하는것이다. 즉, 매번 가장 작은 것을 선택한다는 의미에서 선택정렬이라고 한다.

1. 주어진 배열에서 가장 작은 값을 찾는다.
2. 찾은 가장 작은 값과 맨 첫번째 값으로 교체한다.
3. 교체한 첫번째 위치 원소 값을 제외한 값 중에서 가장 작은 값을 찾는다.
4. 두번째 원소와 찾은 가장 작은 값을 교체한다.
5. 반복한다.

Java code

public class SelectionSort {
    //오름차순
    public static void main(String[] args) {
        int[] arr = {3, 4, 6, 8, 7, 5, 0, 2, 1};

        for (int i = 0; i < arr.length; i++) {

            int minIdx = i; //최소값을 저장할 idx

            //한바퀴를 돌고 가장 작은 값을 찾은 후에 교체
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[j] < arr[minIdx]) {
                    minIdx = j;
                }

                //교체
                int tmp = arr[minIdx];
                arr[minIdx] = arr[i];
                arr[i] = tmp;
            }
        }
        System.out.print("Sorted Array :" + Arrays.toString(arr));
    }
}

선택정렬의 시간 복잡도

데이터의 개수가 N개 라고 했을 때,

• 첫번째 회전에서의 비교 횟수 : 1 ~ (N-1) ⇒ n-1
• 두번째 회전에서의 비교 횟수 : 2 ~ (N-1) ⇒ n-2

이므로 (N-1) + (N-2) + … + 2 + 1 = n(n-1)/2 이다.

따라서 시간복잡도는 O(N^2)이다. 이때 최선, 평균, 최악의 경우 모두 다 동일하다.

선택정렬의 공간복잡도

주어진 배열 안에서 교환을 하므로 O(N)이다.

선택정렬의 특징

1. 제자리 정렬 알고리즘(in-place sorting)의 하나로 배열이외의 다른 추가 메모리를 요구하지 않는다.
2. 비교 횟수는 많지만 실제로 교환하는 횟수는 적다. 따라서 교환이 많이 발생하는 자료상태라면 효율적이다.
3. 시간복잡도가 O(N^2)이므로 만약에 정렬해야 할 개수가 100배 늘어나면 수행시간은 10,000배로 늘어나기때문에 비효율적이다.

 

2. 버블정렬(Bubble Sort)

서로 인접한 두 원소를 비교하고, 조건에 맞지 않다면 자리를 교환해 정렬하는 알고리즘이다

과정

1. 1회전에 첫번째 원소와 두번째원소, 두번째 원소와 세번째 원소를 비교해 마지막-1 원소와 마지막 원소까지 비교해 조건에 맞지 않을때 서로 교환한다.
2. 1회전을 수행하면 가장 큰 값이 맨 뒤로 이동하므로 2회전에서는 맨 끝에 있는 원소를 제외하고 반복 수행한다.

java code

public static int[] solution(int n, int[] arr) {

        // i와 j는 항상 0이어야함. 오름차순 기준으로 한 턴이 돌때마다 끝이 고정되므로
        //n이 4라는 건 n번 돈다는 것

        //n이 아닌 n-1을 하는건 마지막 턴은 다 오름차순으로 정렬되어서 굳이 돌 필요없어서
        //n-1 이 아닌 n-1-i를 하는건 턴을 돌때마다 가장 큰수가 끝으로 정렬이 이미 되어서 굳이 확인할 필요가 없어서
        for (int i = 0; i < n -1 ; i++) {
            for (int j = 0; j < n-1 -i; j++) {
                //내림차순
                if (arr[j] > arr[j + 1]) {
                    int tmp = arr[j + 1];
                    arr[j + 1] = arr[j];
                    arr[j] = tmp;
                }
            }
        }

        return arr;
    }

버블정렬의 시간복잡도

데이터의 개수가 N이라고 했을 때 ,

첫번재 회전 (i == 0) 에서의 비교횟수는 : 1 ~ (n-1)= > n-1

두번째 회전 (i == 1)에서의 비교횟수는 : 2 ~ (n-1) ⇒ n-2

…

즉, (n-1) + (n-2) + .... + 2 + 1 => n(n-1)/2 이다.

따라서 n개의 주어진 배열을 정렬하는데 **O(n^2)**의 시간이 걸린다.

버블정렬은 정렬이 되어있건, 안 되어있건 2개의 원소를 계속 비교하기 때문에 최선, 평균, 최악의 경우 모두 시간 복잡도가  O(n^2) 이다.

버블정렬의 특징

• 구현이 간단하고 ,코드가 직관적이다.
• 제자리 정렬 알고리즘(in-place sorting)의 하나로 배열 이외의 다른 추가 메모리를 요구하지 않는다.
• 동일한 값을 가지는 원소들의 본래 순서가 유지되기때문에 안정적이다.
• 시간복잡도가 O(n^2) 이므로 비효율적이다.
• 정렬되어있는지 원소를 정렬시키기 위한 교환연산(Swap)이 많이 일어난다.

 

 

+ 안정정렬

여기서 배열이 안정적이라는 말은 안정 정렬이라는 뜻으로 ,

정렬 전 동일한 키 값의 요소 순서가 정렬 후 유지가 될때 안정정렬이라고한다.