Hackerrank Day 20 Sorting

알고리즘 연습 사이트

www.hackerrank.com

Day 20:Sorting

 20일차는 Bubble sort에 대해 간략히 배웠다. 

 정렬되는 모습이 마치 거품처럼 위로 이동하는 것 처럼 보이기 때문에 Bubble이라는 말이 붙었다. 
 버블 정렬은 실제 현실세상에서 써먹기에는 그리 효율이 좋지 않기 때문에 학습 용도로만 배운다.

 버블정렬은 간단히 말하면 정렬을 할 때 인접한 두개의 값을 서로 비교하여 큰 값이 작은 값보다 앞에 있다면 두 값의 위치를 서로 바꾸는 것이다.


키 포인트는 최초 1회 비교에서 가장 큰 값은 마지막에 위치하게 된다.


 배열의 시작 지점부터 바로 인접한 변수를 계속 비교하여, swap하거나 그대로 두면서 배열의 끝까지 계속 비교해야 한다.
 그리고 2 싸이클에서 다시 배열의 처음으로 되돌아와서 다시 순서대로 비교한다. 

 규칙을 찾아내보면 배열의 길이에서 1을 뺀 만큼 도는 바깥 반복문 1개와, 그 내부에 인접한 두개의 변수를 비교하면서 배열의 위치를 계속 이동시키는 반복문이 필요하다. 


버블소트 기본 동작을 이해하고 나서 코드를 보면 이해가 쉽다.

오늘 문제는 버블소트를 구현하고 몇 번 swap이 일어났는지와 첫번째와 마지막 요소를 출력하는 것이다.

첫번째 버전은 마지막으로 스왑이 일어난 지점을 endPosition에 저장하고 endPosition만큼만 반복을 한다. 

이렇게 되면 어차피 마지막 값이 최대값이 들어있는 부분은 검사를 안하게 되는 이점이 있다.
그리고 endPosition이 0이 되면 while 반복문을 탈출하게 된다. 


(1) 첫번째 버블소트

public static void bubbleSort(int[] x) {
    printArray("Initial", x);

    int endPosition = x.length - 1;
    int swapPosition;

    while( endPosition > 0 ) {
        swapPosition = 0;

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

            if( x[i] > x[i + 1] ){
                // Swap elements 'i' and 'i + 1':
                int tmp = x[i];
                x[i] = x[i + 1];
                x[i + 1] = tmp;

                swapPosition = i;
            } // end if

        } // end for

        endPosition = swapPosition;
    } // end while
} // end bubbleSort

(2) 두번째 버블소트

public class Solution {

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] a = new int[n];
        for(int a_i=0; a_i < n; a_i++){
            a[a_i] = in.nextInt();
        }
        
        int numSwaps = 0; //Swap이 일어난 total 횟수
        int firstElement = 0; //첫번째 배열 데이터 저장
        int lastElement =0; //마지막 배열 데이터 저장
        int tmp = 0; 
        for(int i =0 ; i < a.length ; i++){ 
            for(int j = 0 ; j < a.length -1 ; j++){
                if(a[j] > a[j+1]){
                   tmp = a[j+1];
                   a[j+1] = a[j];
                   a[j] = tmp;
                   numSwaps++; 
                }
            }
        }
        System.out.println("Array is sorted in "+numSwaps+" swaps.");
        System.out.println("First Element: "+a[0]);
        System.out.println("Last Element: "+a[a.length-1]);
    }
}

두번째는 모든 루프에서 배열 전체를 다 검사하는 단순한 버블소트이다.