JAVA 자료구조 : 버블정렬

스터디사이트 : https://www.hackerrank.com

JAVA 자료구조 : 버블정렬

버블정렬 원리를 이용하여 아래의 Output이 나오게 코딩하라.

버블정렬이란,

입력받은 숫자 데이터가 저장되어 있는 배열을 일반적으로 오름차순으로 정렬하기 위해서 사용하는 정렬방식 중 하나이다.

예를 들어 ,

1 번째 자리와 2번째 자리를 비교하여 1번째 데이터가 2번째 데이터 값보다 크면 서로 위치를 교환한다.

2 번째 자리와 3번째 자리를 비교하여 2번째 데이터가 3번째 데이터 값보다 크면 서로 위치를 교환한다.

...

n-1 번째 자리와 n번째 자리를 비교하여 n-1번째 데이터가 n번째 데이터 값보다 크면 서로 위치를 교환한다.

상기와 같은 작업이 끝나면 1 사이클을 돈 것이다.

이후에 n-1 사이클을 돌리면 버블정렬은 끝이 난다.

↓ 버블정렬의 원리를 코딩으로 표현 ↓

for (int i = 0; i < n; i++) {
    int numberOfSwaps = 0;
    
    for (int j = 0; j < n - 1; j++) {
        if (a[j] > a[j + 1]) {
            swap(a[j], a[j + 1]);
            numberOfSwaps++;
        }
    }
    
    if (numberOfSwaps == 0) {
        break;
    }
}

버블정렬에서 i 와 j 중,

i는 첨자변수가 아니고,

i는 버블정렬의 회전수를 카운트하기 위한 변수일 뿐이다.

실제 비교하는 것은 j와 j+1을 비교하는 것이다.

 A(j) ↔ A(j+1) 

1회전 ( i = 1 )이 끝나고 2회전이 ( i = 2 ) 되었을 때,

2회전 첫 시작 시 j값은 다시 1부터 시작한다.

ex) 5 x 5 정렬

i = 1 (회전)

i = 1, 4, 1

j = 1, 5-i, 1

※ 조건

입력받는 값의 조건

n : 입력받을 배열의 자릿수

a[] : 입력받는 값을 저장해 놓는 배열

numberOfSwaps :  i 번째자리와 i+1 번째 자리를 비교해서  a[i] > a[i+1] 일때 Swap한다고 하며, 총 Swap한 횟수를 표현하는 int.

입력 1

3

1 2 3

출력 1

Array is sorted in 0 swaps.        ← 이미 오름차순으로 정렬되어 있기 때문.

First Element: 1

Last Element: 3

입력 2

3

3 2 1

출력 2

Array is sorted in 3 swaps.

First Element: 1

Last Element: 3

디버깅 1

버블정렬 시 

a[i] > a[i+1]

이 발생하게 되었을 때 swap을 하는 것에 대해 연구해 보면 된다.

1차원 배열이기 때문에 두 개의 데이터를 맞바꾸려면 다른 차원에서 온 변수를 새로 정의해서

3개의 변수를 이용하면 swap을 쉽게 해낼 수 있다.

아래 그림의 코딩에서 화살표를 그린 것은 거의 swap 코딩의 공식과 같은 것이니 알아 두면 좋다.

결과

public static void main(String[] args) { /* Variable Definition */ Scanner scan = new Scanner(System.in); int n = scan.nextInt(); int[] a = new int[n]; for(int i=0; i<n; i++){ a[i] = scan.nextInt(); } int numberOfSwaps=0; int temp=0; /* Bubble Sort */ for (int i = 0; i < n; i++) { for (int j = 0; j < n - 1; j++) { if (a[j] > a[j + 1]) { temp = a[j]; a[j] = a[j+1]; a[j+1] = temp; numberOfSwaps++; } } //end for j if (numberOfSwaps == 0) { break; } } // end for i /* Output */ System.out.println("Array is sorted in " + numberOfSwaps + " swaps."); System.out.println("First Element: " + a[0]); System.out.println("Last Element: " + a[a.length-1]); }

결과 :  3 1 2 3 Array is sorted in 0 swaps. First Element: 1 Last Element: 3