오름차순/내림차순 정렬하기_Bubble Sort

숫자배열의 오름차순, 내림차순 정렬에 가장 기본적인 방법은 버블소트를 활용하는 것이다.

 

1. 버블정렬이란

서로 이웃한 데이터를 1:1로 비교하여 가장 큰 데이터를 가장 뒤로 보내는 정렬 방식이다.

[a, b, c, d, e]의 정렬되지 않은 숫자 배열이 있다고 하면, 

a부터 순서대로 a<->b 비교 후, a>b일 경우 자리 이동 > b<->c 비교 후 b>c일 경우 자리이동을 하는 식을 전개된다.

 

실제 데이터의 움직임을 보면,

정렬되지 않은 배열 [33, 2, 42, 9]

 

첫번째값인 33부터 바로 왼쪽값과 비교하여 더 큰 수가 왼쪽으로 오도록 정렬한다.

--> 자리값을 기준으로 0-1 / 1-2 / 2-3 을 비교

[2, 33, 42, 9]  33>2임으로 자리 변경

[2, 33, 42, 9]  33<42임으로 자리 유지

[2, 33, 9, 42]  42>9임으로 자리 변경

 

: 첫번째 세트 비교 종료, 가장 마지막에 가장 큰 수가 오게 정렬이 되었다

 

그렇기 때문에, 다음정렬에서는 가장 마지막 수를 제외한 n-1번 비교를 하면 된다

--> 자리값을 기준으로 0-1 / 1-2 비교

[2, 33, 9, 42]  2<33임으로 자리 유지

[2, 9, 33, 42]  33>9임으로 자리 변경

 

: 두번째 세트 비교 종료, n-1자리에 두번째로 큰 수가 오게 된다

 

그렇기 때문에, 다음정렬에서는 마지막 두 개의 수를 제외한 n-2번 비교를 하면 된다.

--> 자리값을 기준으로 0-1 비교

[2, 9, 33, 42]  2<9임으로 자리 유지

 

총 4(n)개의 수를 비교하는데 3(i)번의 정렬세트가 필요하고, 각 세트 안에는 n-1-i번의 버블 비교가 필요함을 알 수 있다.

 

2. 로직

숫자 배열 선언

 

for(배열의 숫자 갯수만큼){

   for(j = 배열의 숫자 갯수 - 이미 완료된 세트 - 1) // 가장 마지막 수는 다음 수와 비교할 필요가 없기 때문에

      if( j번째 숫자 > j+1의 숫자) {

                  j번째 숫자 <-> j+1번째 숫자 자리 변경

          }

     }

}

 

숫자의 자리 변경을 위해서는 임시로 값이 저장되는 변수 temp을 사용하여 

temp<-j  /  j<-j+1 / j+1<- temp의 값을 넣는 형태로 변환한다.

 

3. 다섯개의 수를 입력받아 오름차순으로 정렬하는 코드

import java.util.Scanner;

public class BubbleSort {

	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		int[] nums = new int[5];

		for(int i=0; i<nums.length; i++) {
			System.out.print((i+1)+"번째 정수 입력 : ");
			nums[i] = scan.nextInt();
		}
		
		int temp=0;
		for(int i = 0; i<nums.length; i++) {
			for(int j=0; j<nums.length-1-i; j++) {
				if(nums[j]>nums[j+1]) {
					temp = nums[j];
					nums[j]=nums[j+1];
					nums[j+1]=temp;
				}
			}
		}

		System.out.print("정렬된 결과 : "+Arrays.toString(nums));

	}//main end

}//class end

- 값을 입력 받아 사용하는 Scanner 변수가 쓰이고 있음으로 Scanner Class 임포트가 필요하다

- if 문에서 a[j]<a[j+1]로 바꾸면 내림차순 정렬이 가능하다.

 

결과값

버블연산을 더 잘보기 위해 프린트구문을 좀 더 추가했다. 실제로 연산안에 프린트를 넣게 되면 코드가 많이 느려지게 됨으로 위에 코드에서는 편집하고 올렸다.

1번째 정수 입력 : 21
2번째 정수 입력 : 86
3번째 정수 입력 : 39
4번째 정수 입력 : 16
5번째 정수 입력 : 9
입력된 값은 : [21, 86, 39, 16, 9]
[21, 86, 39, 16, 9]
[21, 39, 86, 16, 9]
[21, 39, 16, 86, 9]
[21, 39, 16, 9, 86]
[21, 39, 16, 9, 86]
[21, 16, 39, 9, 86]
[21, 16, 9, 39, 86]
[16, 21, 9, 39, 86]
[16, 9, 21, 39, 86]
[9, 16, 21, 39, 86]
정렬된 결과 : 9 16 21 39 86 

 

4. 버블정렬의 한계

코드로직을 직접 하나하나 따라가 보면 알 수 있듯이, 버블 정렬을 사용할 경우 이미 오름차순으로 정렬이 되어 있어도, for문을 통해 다시 한 번 끝까지 비교를 하는 것을 강제받는다.

만약, 이미 정렬된 코드가 들어왔다고 하더라도 모든 과정을 거쳐야만 한다는 점에서 한계점이 있다.