Algorithm - 정렬 알고리즘

정렬 알고리즘
데이터를 일정한 순서로 나열하는 알고리즘

 

내부 정렬과 외부 정렬

30장의 카드를 한 줄로 늘어놓을 수 있는 책상에서 트럼프 카드를 정렬한다고 가정해보자

만약 카드가 30장 이하라면 모든 카드를 책상에 늘어놓고 한 번에 훑어보면서 작업할 수 있지만, 카드가 500장이라면 책상에

모든 카드를 늘어놓을 수 없기 때문에 큰 책상을 따로 마련해야 합니다.

정렬 알고리즘도 하나의 배열에서 작업할 수 있을 때에는 내부 정렬을 사용하고 하나의 배열에서 작업할 수 없을 땐 외부 정렬을 사용 한다

 

• 내부 정렬 : 정렬할 모든 데이터를 하나의 배열에 저장할 수 있을 때에 사용하는 알고리즘
• 외부 정렬 : 정렬할 데이터가 너무 많아서 하나의 배열에 저장할 수 없을 때에 사용하는 알고리즘

외부 정렬은 내부 정렬을 응용한 것이기에, 외부 정렬을 구현하기 위해선 작업을 위한 별도의 파일이 필요하며 복잡한 알고리즘을 가지고 있다. 그렇기 때문에 내부 정렬만 다룬다.

정렬 알고리즘의 핵심은 교환, 선택, 삽입이다. 대부분의 정렬 알고리즘은 이를 뿌리 삼아 응용하였다.

 

 

버블 정렬

이웃한 두 요소의 대소 관계를 비교하고 필요에 따라 교환을 반복하는 알고리즘으로 단순 교환 정렬이라고도 한다.

1.두 요소를 비교 하여 왼쪽 값이 클 경우 오른쪽 값과 교환

2.두 요소를 비교 하여 왼쪽 값이 작을 경우 패스

3

8

2

5

1

7

6

버블 정렬은 먼저 가장 끝에 있는 두요소 7, 6부터 시작한다

만약 오름차순 정렬을 하고자 한다면 왼쪽 값이 오른쪽 값보다 작아야 하므로 7, 6을 교환한다.

3

8

2

5

1

6

7

그 다음 단계로 1과 6을 비교한다. 작은 값이 왼쪽에 있기 때문에 교환할 필요가 없다.

이와 같은 1, 2의 방식을 이용하여 요솟수가 n개인 배열에서 n-1번 비교, 교환하고 나면 가장 작은 요소가 맨 앞으로 이동한다.

그렇다면 배열은 현재 이와 같은 상태를 가지고 있다

1

3

8

2

5

6

7

가장 작은 수가 제일 왼쪽에 왔지만 모든 정렬이 끝난 것은 아니다.

이번엔 두번째 이후 요소들을 다시 정렬해보자 

1

2

3

8

5

6

7

요솟수가 n개인 배열에서 n-2번 비교한다.

이러한 정렬 1번을 패스라고 하며 패스를 k번 수행하면 앞쪽부터 k개의 요소가 정렬이 된다. 

모든 정렬이 끝나려면 n-1번의 패스가 수행되어야 한다.

• n번의 패스가 아닌 n-1번의 패스가 필요한 이유는 n-1개 요소의 정렬이 끝나면 마지막 요소는 이미 끝에 놓이기 때문이다.

 

이 알고리즘은 위와 같은 방식으로 처리되어 요소들이 정렬이 된다.

하지만 1 2 3 4 5 6 8 7 같은 경우엔 8과 7 1회의 교환만 이루어지면 그 후엔 정렬할 필요가 없다.

즉 많은 비교 연산들이 생략되어 짧은 시간에 정렬을 마칠 수 있다. 

이를 위해 우리는 패스와 관련된 변수 하나를 사용할 것이다.

 

알고리즘 개선하기 1

exchg 변수는 패스 하기 전 값을 0으로 해두고 요소를 교환할 때마다 1씩 증가시킨다.

허나 어떠한 교환도 이루어지지 않았을 경우 = 이미 정렬이 완료되어

더이상 정렬할 필요가 없는 경우엔 반복문을 탈출시켜 함수를 종료시키는 것이다.

import java.util.Scanner;

public class BubbleSort {
    static void swap(int[] a, int idx1, int idx2){
        int t = a[idx1];
        a[idx1] = a[idx2];
        a[idx2] = t;
    }

    static void bubblesort(int[] a, int n){
        int exchg = 0; //패스에서 교환하는 횟수 저장
        for(int i=0; i<n-1; i++){
            for(int j=n-1; j>i; j--){
                if(a[j-1]>a[j]) swap(a, j-1, j);
                exchg++;
            }
            if(exchg==0) break; //교환이 이루어지지 않았을 때 반복문 탈출
        }

    }

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

        System.out.println("버블 정렬(버전1)");
        System.out.println("요솟수");
        int nx = stdIn.nextInt();
        int[] x = new int[nx];

        for(int i=0; i<nx; i++){
            System.out.print("x["+i+"]:");
            x[i]=stdIn.nextInt();
        }

        bubblesort(x, nx);

        System.out.println("오름차순으로 정렬했습니다.");
        for(int i=0; i<nx; i++){
            System.out.println("x["+i+"]=" + x[i]);
        }
        
        stdIn.close();

    }
}

 

알고리즘 개선하기 2

이와 같은 배열이 있다고 생각해보자.

1번째 패스 5단계에 1,3,4 는 이미 정렬이 완료 되었다.

그럼 그 다음 패스부터는 1, 3, 4를 제외한 요소들에 관한 것만 교환이 이루어지면 된다.

이러한 사항을 바탕으로 개선한 메소드이다.

    static void bubblesort(int[] a, int n){
        int k = 0;		//a[k]보다 앞쪽은 정렬을 마친 상태
        while(k<n-1){
            int last = n - 1; //마지막으로 요소를 교환한 위치
            for(int j=n-1;j>k;j--){
                if(a[j-1]>a[j]){
                    swap(a, j-1, j);
                    last = j;
                }
            }
            k = last;
        }
    }

 

last는 각 패스에서 마지막으로 교환한 두 요소 가운데 오른쪽 요소(a[j])의 인덱스를 저장하기 위한 변수이다.

교환할 때마다 오른쪽 요소의 인덱스 값을 last에 저장한다.

하나의 패스를 마쳤을 때 last값을 k에 대입하여 다음에 수행할 패스의 범위를 제한한다.

그러면 다음 패스에서 마지막으로 비교할 두 요소는 a[k]와 a[k+1]이 된다.

이 때 처음 메소드가 동작시 k=0으로 선언하는 이유는 첫번째 패스에선 모든 요소를 검사 해야하기 때문이다.

 

 

단순 선택 정렬

단순 선택 정렬은 가장 작은 요소를 맨 앞으로 이동하고, 두번째 작은 요소는 맨 앞에서 두번째로 이동하는 작업을 반복하는 알고리즘이다.

 

다음 배열로 단순 선택 정렬 알고리즘을 적용해보자

6

4

8

3

1

9

7

이 알고리즘은 가장 작은 요소부터 정렬하므로 가장 작은 값인 1과 6의 위치를 바꾼다.

그 후 두번째로 작은 요소인 3을 선택하여 4와 위치를 바꾼다

1

4

8

3

6

9

7

그 다음 과정으로 아직 정렬하지 않은 부분에서 값이 가장 작은 요소를 선택하고 아직 정렬하지 않은 부분의 첫번째 요소와 교환한다

1

3

8

4

6

9

7

위의 과정을 통하여

1

3

4

6

7

8

9

이렇게 정렬이 되는 알고리즘을 단순 선택 정렬이라고 한다.

 

단순 선택 정렬의 교환 과정을 정리해보면

1. 아직 정렬하지 않은 부분에서 가장 작은 키값(a[min])을 선택한다

2.a[min]과 아직 정렬하지 않은 부분의 첫번째 요소를 교환한다

 

이 과정을 n-1회 반복하면 된다.

 

  static void SelectionSort(int[] a, int n){
        for(int i=0;i<n-1;i++){
            int min = i; //min은 a[i]....a[n-1]에서 값이 가장 작은 요소의 인덱스
            for(int j=i+1; j<n; j++){ 
                if(a[j]<a[min]){
                    min = j;
                }
                swap(a, i, min); //아직 정렬되지 않은 부분의 첫 요소와 가장 작은 요소를 교환
            }
        }
    }

 

단순 선택 정렬 알고리즘의 요솟값을 비교하는 횟수는 (n^2-n)/2번이다.

이 알고리즘은 떨어져 있는 요소를 교환하므로 안정적이지 않다.

 

단순 삽입 정렬

단순 삽입 정렬은 트럼프 카드를 한 줄로 늘어놓을 때 사용하는 방법과 비슷한 방법의 알고리즘이다.

6

4

1

7

3

9

8

단순 삽입 정렬은 두 번째 요소부터 선택하여 진행하는데, 이때 4는 6보다 앞쪽에 위치해야 하므로 앞쪽에 삽입한다.

이에 따라 6을 오른쪽으로 옮기게 된다면 다음과 같아진다.

4

6

1

7

3

9

8

이제 3번째 요소 1을 선택해 앞쪽에 삽입한다. 이러한 과정을 반복하여 정렬을 하는 방식인데 쉽게 말하자면

아직 정렬되지 않은 부분의 첫번째 요소를 정렬한 부분의 알맞은 위치에 삽입한다.

 

 

이웃한 요소 7이 선택한 요소 3보다 크면 그 값을 대입하고 앞으로 이동하면서 사진과 같이 작업을 반복한다.

그러다가 선택한 값 3이 그보다 작은 값 1을 만나면 그보다 앞쪽은 검사할 필요가 없으므로 해당 위치에 삽입할 값 3을 대입한다.

    j=i;
    tmp = a[i];
    while(j>0&&a[j-1]>tmp){
        a[j] = a[j-1];
        j--;
    }
    a[j] = tmp;

다시 말해 tmp에 a[i]를 대입하고 반복 제어용 변수 j에 i를 대입한 뒤 다음 두 조건중 하나를 만족할 때까지 j를 1씩 감소시키면서

대입하는 작업을 반복한다.

 

1. 정렬된 열의 왼쪽 끝에 도달한다

2. tmp보다 작거나 같은 key를 갖는 항목 a[j-1]을 발견한다.

 

이때 &&연산자를 사용하였기에

1. j가 0보다 크다

2. a[j-1]값이 tmp보다 크다

두 조건이 만족할 때까지 반복하게 된다.

 

이 과정을 마치고 난 뒤 요소 a[j]에 tmp를 대입하면 한 요소에 대한 단순 삽입 정렬을 마치게 된다.

214