[Java] 배열의 활용 : 정렬하기 - 버블정렬 (bubble sort)

 

 

 

int[] numArr = new int[] { 5, 1, 3, 4, 2 };

위 같은 배열을 { 1, 2, 3, 4, 5 }처럼

최소값에서 최대값 순서로 정렬하면 오름차순,

반대로 { 5, 4, 3, 2, 1 }처럼

최대값에서 최소값 순서로 정렬하면 내림차순이라 한다.

 

이렇게 원하는 순서대로 정렬을 하려고 할 때

여러 가지 방식이 있는데,

그동안 배운 반복문과 조건문을 이용하여

쉽게 '버블 정렬'(거품 정렬이라고도 한다)을

코딩할 수 있다.

 

 

 

<버블 정렬의 원리>

 

우선 버블 정렬의 원리는 다음과 같다.

오름차순으로 정렬하는 경우,

 

(i=0) 1회 차에 

(j=0) { 5, 1, 3, 4, 2 } 배열의 1번과 2번 요소를 비교하여 

　　 값을 비교하여 더 작은 수를 1번에 저장하고

　　 더 큰 수를 2번에 저장하여

　　 { 1, 5, 3, 4, 2 }로 정렬한다.

(j=1) 다시 2번과 3번을 비교하여

　　 더 작은 수를 2번에 저장하고

　　 더 큰 수를 3번에 저장하여

　　 { 1, 3, 5, 4, 2 }로 정렬한다.

(j=2) 그다음은 3번과 4번을 비교하여

　　 { 1, 3, 4, 5, 2 }로

(j=3) 그다음은 4번과 5번을 비교하여

　　 { 1, 3, 4, 2, 5 }로 정렬한다.

 

(i=1) 2회 차에서는 다시 처음으로 돌아가

(j=0) 1번과 2번을 비교하여

　　 { 1, 3, 4, 2, 5 }로 (변화 없음)

(j=1) 2번과 3번을 비교하여

　　 { 1, 3, 4, 2, 5 }로 (변화 없음)

(j=2) 3번과 4번을 비교하여

　　 { 1, 3, 2, 4, 5 }로 정렬하고

　　 이미 0회 차에서 가장 큰 수를

　　 마지막 요소에 정렬되었기 때문에

　　 비교할 필요 없이 맨 앞으로 돌아간다.

　　(2회 차가 1회 차보다 1회 덜 비교한다)

 

(i=2) 3회 차에서는 

(j=0) { 1, 3, 2, 4, 5 }로 (변화 없음)

(j=1) { 1, 2, 3, 4, 5 }로 정렬한다.

　　 이미 1회 차에서 그다음 큰 수를

　　 4번째 요소에 정렬되었기 때문에

　　 비교할 필요 없이 맨 앞으로 돌아간다.

　　 ((3회 차가 2회 차보다 1회 덜 비교한다)

 

(i=3) 4회 차에서는 

(j=0) 1번과 2번을 비교하고

　　 { 1, 2, 3, 4, 5 }로 (변화 없음)

　　 정렬한 다음 최종적으로 정렬을 끝낸다.

 

 

 

<버블 정렬의 정의>

 

정리하자면, 버블정렬은

2번째와 3번째, ..., n-1번째와 n번째를 정렬한 뒤,

다시 처음으로 돌아가 이번에는 n-2번째와 n-1번째까지를 반복하여

최대 n(n−1)/2​번 정렬하는 방식이다.

 

버블 정렬은 가장 손쉽게 구현하여 사용할 수 있지만,

만들기가 쉽고 직관적일 뿐이지

알고리즘적 관점에서 보면 굉장히 비효율적인 정렬 방식이다. 

이미 정렬된 자료를 다시 비교하여 정렬하기 때문이다.

하지만 정렬 알고리즘은

자료가 정렬되어 있는지 아닌지는 모르고 작동하기 때문에 의미가 있다.

 

 

 

▼ 참고 영상

 

 

 

<버블 정렬의 오름차순 코딩>

 

Java에서 버블 정렬의 오름차순을 코딩하면 다음과 같다.

public class P201_ArrayEx10 {
	public static void main(String[] args) {
		int[] numArr = new int[10];			// 길이가 10인 배열 선언 및 생성
		for (int i = 0; i < numArr.length; i++) {	// 배열에 0~9사이의 임의의 수 저장
			System.out.print(numArr[i] = (int)(Math.random() * 10));
		}
		System.out.println();
		
		for (int i = 0; i < numArr.length; i++) {
			boolean changed = false;			// --- ①
			for (int j = 0; j < numArr.length-1-i; j++) {	// --- ②
				if(numArr[j] > numArr[j+1]) {	// 다음 요소의 값이 작으면 자리를 바꾼다.
				int temp = numArr[j];
				numArr[j] = numArr[j+1];
				numArr[j+1] = temp;
				changed = true;			// 자리바꿈이 발생했으니 true로
			}
		}
		if (!changed) break;				// 자리바꿈이 없으면 반복문을 벗어난다.
		for (int k = 0; k < numArr.length; k++)
			System.out.print(numArr[k]); 		// 정렬된 결과를 출력한다.
		System.out.println();
		}
	}
}

 

① boolean changed = false;는

　 초반에 원하는 대로 정렬이 된 경우

　 불필요한 연산을 줄이기 위해

　 자리바꿈이 발생하지 않으면

　 반복문을 벗어나기 위해 추가했다.

　 (생략 가능. 생략 시 changed = true;와 if (!changed) break; 함께 생략)

 

② 조건식 j < numArr.length-1-i은

　 앞 회차에서 이미 정렬된 요소에 대한

　 연산을 줄이기 위해 -i를 했다. (생략 가능)

　 j > numArr.length-1-i와 같이

　 부등호를 방향을 바꾸면

　 내림차순이 된다.