[java] 버블정렬 알고리즘

버블정렬 알고리즘은 배열의 값을 정렬하는 알고리즘이다.

 

<원하는 기능>

1. 0~9 까지 무작위 수 10개를 배열에 넣는다.

2. 버블정렬 알고리즘을 통해서 내림차순으로 정렬하고 출력한다.

 

먼저 버블정렬 알고리즘의 작동 순서를 살펴보자 길이가 8인 배열에 순서대로 숫자가 들어간다고 생각해보자

1

2

3

4

5

6

7

8

 

1. 가장 앞부터 두 숫자씩 순차적으로 작은수가 뒤에 오도록 비교하여 자리를 바꾼다.  (총 7번 비교)

2

3

4

5

6

7

8

1

 

2. 이렇게 하면 맨 뒤에 가장 작은 수가 오게 되므로 마지막 자리를 제외한 자리수를 같은 방법으로 정렬한다. (6번비교)

3

4

5

6

7

8

2

1

 

3. 가장 작은 수와 두번째  작은 수가 자리를 찾았으므로 두자리수를 빼고 같은방법으로 정렬한다. (5번 비교)

4

5

6

7

8

3

2

1

 

4. 위와 같은 방법으로 (4번 비교)

5

6

7

8

4

3

2

1

 

5. (3번 비교) (6 vs7 , 6 vs 8 , 6 vs 5)

6

7

8

5

4

3

2

1

 

6. (2번 비교)

7

8

6

5

4

3

2

1

 

7.(1번 비교 ) >>>>> 정렬 완료

8

7

6

5

4

3

2

1

 

이를 코드로 나타내보자

for (int i=0; i<arr.length; i++) {
    for(int j=0; j< arr.length-1-i; j++) {
        if (arr[j] > arr[j+1]) { // 배열 순서를 바꾸는 방법
            int tmp = arr[j];    // 두 값을 바꾸기 위해서는 임시변수 tmp 필요
            arr[j] = arr[j+1];
            arr[j+1] = tmp;
        }
    }
}

버블 정렬 알고리즘은 (배열의 길이 -1)번 정렬이 반복되고, 

 

각각의 정렬은 가장 처음 (배열의 길이-1)번 에서부터 시행횟수가 증가할 수록 1씩 비교횟수가 감소한다.

 

비교시에는 현재 배열의 값과 다음 배열의 값을 비교하여 크면 두 수의 순서를 바꾼다.

 

이를 이중 for문과 if문을 결합하여 위와 같이 표현할 수 있다.

 

버블정렬을 코드로 구현하였으므로, 랜덤한 값을 가지는 크기 10의 배열을 생성하고 초기화 해보자

int [] arr = new int [10]; // 길이가 10인 배열 생성

for (int i=0; i<arr.length; i++) { 
    arr[i] = (int)(Math.random()*10);  
}   // 0~9 까지의 랜덤한 숫자로 배열 초기화

System.out.println("정렬 전");

for (int i=0; i<arr.length; i++) {
    System.out.print(arr[i]);
} // 버블 정렬을 실시하기 전에 출력문으로 배열에 어떤 값이 들어갔는지 확인

먼저 (int)(Math.random()*10) 으로 0~9 까지의 랜덤한 정수를 구해 배열에 넣어준다. 

 

프로그램을 실행할때마다 10개의 랜덤한 한자리 숫자가 배열에 들어갈 것이다.

 

만들어진 배열은 버블정렬을 실시하기 전에 출력문을 통해 확인하자

 

마지막으로 정렬 된 후 배열을 출력하여 확인하면 다음과 같은 완성된 코드가 나온다.

package chapter06;

import java.util.Scanner;

public class Ch06_6 {
	public static void main(String [] args) {
		int [] arr = new int [10];
		
		for (int i=0; i<arr.length; i++) {
			arr[i] = (int)(Math.random()*10);
		}
		
		System.out.println("정렬 전");
		
		for (int i=0; i<arr.length; i++) {
			System.out.print(arr[i]);
		}
		System.out.println();
		
		for (int i=0; i<arr.length; i++) {
			for(int j=0; j< arr.length-1-i; j++) {
				if (arr[j] > arr[j+1]) {
					int tmp = arr[j];
					arr[j] = arr[j+1];
					arr[j+1] = tmp;
				}
			}
		}
		
		System.out.println("정렬 후");
		
		for (int i=0; i<arr.length; i++) {
			System.out.print(arr[i]);
		}
	}
}

 

시행할 때마다 랜덤한 배열이 생성되고 내림차순으로 정렬되는 것을 볼 수 있다.