Computer >> 컴퓨터 >  >> 프로그래밍 >> Java

자바 버블 정렬 완벽 가이드: 원리 이해부터 코드 구현까지

자바 버블 정렬 작성 방법

프로그래머들이 '버블 정렬(bubble sort)'이라고 말할 때, 이는 우리가 일상에서 불어 본 물방울(거품)을 의미하는 것이 아닙니다. 버블 정렬은 리스트의 항목들을 순서대로 정렬하는 데 사용되는 정렬 알고리즘을 가리킵니다.

이 가이드에서는 버블 정렬의 개념과 작동 방식을 살펴보고, 자바로 버블 정렬을 직접 구현해 보면서 알고리즘이 실제 코드로 어떻게 변환되는지 이해해 보겠습니다. 그럼 바로 시작해 보겠습니다!

자바 버블 정렬이란?

버블 정렬은 인접한 두 요소를 비교하고, 순서가 잘못되어 있다면 서로 위치를 교환(swap)하는 방식으로 값을 정렬하는 알고리즘입니다.

이 과정은 리스트의 모든 항목이 올바른 순서로 정렬될 때까지 반복됩니다. 버블 정렬은 오름차순과 내림차순 모두로 리스트를 정렬하는 데 활용할 수 있습니다.

버블 정렬은 알고리즘 수업에서 가장 먼저 배우는 정렬 방식입니다. 삽입 정렬이나 선택 정렬 같은 다른 정렬 알고리즘보다 이해하기 쉽고, 정렬 알고리즘 학습의 좋은 출발점이 되기 때문입니다.

다만 버블 정렬은 데이터가 이미 거의 정렬되어 있는 경우에 가장 효과적입니다. 데이터가 전혀 정렬되어 있지 않다면 다른 정렬 알고리즘이 더 효율적일 수 있습니다.

버블 정렬의 작동 원리

코드를 작성하기 전에, 이 알고리즘이 실제로 어떻게 동작하는지 먼저 이해해야 합니다. 다음 리스트를 살펴보겠습니다.

5927

버블 정렬은 리스트의 첫 번째 요소와 두 번째 요소를 비교하는 것부터 시작합니다.

첫 번째 요소가 두 번째 요소보다 크면 두 요소의 위치를 교환합니다. 이 예시에서 5는 9보다 크지 않으므로, 두 요소는 그대로 유지됩니다.

그다음, 정렬은 리스트에서 다음 두 항목을 비교합니다. 9는 2보다 크므로, 두 숫자의 위치가 교환됩니다.

5297

이 과정은 리스트의 모든 항목이 비교될 때까지 반복됩니다. 여기서는 마지막 비교가 하나 남아 있습니다. 9가 7보다 큰가요? 그렇습니다. 따라서 두 숫자의 위치가 교환됩니다.

5279

이제 리스트가 거의 정렬되었습니다. 모든 항목의 비교가 끝나면, 버블 정렬은 리스트가 완전히 정렬될 때까지 처음부터 다시 비교를 시작합니다.

5는 2보다 크므로, 두 숫자의 위치가 교환됩니다.

2579

이제 리스트가 올바르게 정렬되었습니다. 버블 정렬은 리스트의 끝까지 계속 비교한 후, 더 이상 교환이 필요 없으면 멈춥니다. 버블 정렬은 익숙해지면 정말 쉽게 사용할 수 있는 알고리즘입니다.

자바 버블 정렬 작성하기

이론을 아는 것도 중요하지만, 결국 자바 버블 정렬을 구현하는 방법을 알아야겠죠. 자바에서 버블 정렬을 구현하는 방법을 살펴보겠습니다.

버블 정렬에는 두 가지 유형이 있습니다.

  • 표준 버블 정렬
  • 최적화된 버블 정렬

표준 버블 정렬은 배열이 이미 정렬되어 있더라도 가능한 모든 비교를 수행합니다. 이로 인해 실행 시간이 길어져 정렬 효율성이 떨어집니다.

반면 최적화된 버블 정렬은 추가 변수를 사용해 리스트의 정렬 상태를 추적합니다. 덕분에 리스트가 정렬되는 즉시 정렬을 중단할 수 있습니다.

먼저 표준 버블 정렬부터 작성해 보겠습니다.

표준 버블 정렬

먼저 코드에 Arrays 라이브러리를 임포트합니다. 나중에 정렬된 숫자 목록을 콘솔에 출력할 때 이 라이브러리를 사용하게 됩니다.

import java.util.Arrays;

이제 본격적으로 알고리즘을 작성해 보겠습니다.

자바 프로그램의 코드를 담는 BubbleSort라는 클래스와, 정렬을 수행하는 함수를 정의하는 것부터 시작합니다.

class BubbleSort {
	void sortNumbers(int array[]) {
		int size = array.length;

		for (int item = 0; item < size - 1; item++) {
			for (int j = 0; j < size - item - 1; j++) {
				if (array[j] > array[j + 1]) {
					int temporary = array[j];
					array[j] = array[j + 1];
					array[j + 1] = temporary;
				}
			}
		}
	}
}

변수를 매개변수로 받는 sortNumbers라는 함수를 선언했습니다. 이 함수는 먼저 지정된 숫자 리스트의 크기를 계산합니다.

크기가 계산되면 for 루프가 초기화됩니다. 이 루프는 배열의 모든 항목을 순회합니다. 그리고 각 항목을 비교할 수 있도록 또 다른 for 루프를 초기화합니다.

왼쪽 항목이 오른쪽 항목보다 크면 두 값의 위치가 교환됩니다. 그렇지 않으면 아무 일도 일어나지 않습니다.

이 교환은 왼쪽 값을 'temporary'라는 변수에 할당하는 방식으로 수행됩니다. 그다음 오른쪽 값에 원래 왼쪽에 있던 값을 할당하고, 왼쪽 값에는 temporary 변수의 값을 할당합니다.

예를 들어 6과 5를 비교한다면 두 숫자가 교환되어 리스트는 5, 6 순서가 됩니다.

하지만 지금은 프로그램이 아무것도 실행하지 않습니다. 함수를 호출하고 정렬할 리스트를 전달하는 메인(main) 프로그램을 아직 작성하지 않았기 때문입니다.

코드에서 sortNumbers 함수 아래에 다음 코드를 추가하세요.

public static void main(String args[]) {
	int[] toSort = { 5, 9, 2, 7 };
	BubbleSort sortingAlgorithm = new BubbleSort();
	sortingAlgorithm.sortNumbers(toSort);
	System.out.println(Arrays.toString(toSort));
}

정렬하려는 값들의 리스트를 저장하는 toSort라는 변수를 선언했습니다. 그런 다음 BubbleSort 클래스의 인스턴스인 sortingAlgorithm을 선언하고, 이를 사용해 다음 줄에서 sortNumbers 함수를 호출합니다. 이 함수가 호출되면 리스트가 정렬됩니다.

마지막으로 Arrays.toString() 메서드를 사용해 리스트를 문자열로 변환하여 콘솔에 출력합니다. 코드의 실행 결과는 다음과 같습니다.

[2, 5, 7, 9]

이제 정렬된 배열을 얻었습니다!

최적화된 버블 정렬

코드를 더 효율적으로 만들 방법이 있습니다. 현재 코드는 가능한 모든 비교를 마칠 때까지 정렬을 계속 진행합니다. 즉, 배열이 이미 정렬되어 있어도 모든 비교가 완료될 때까지 정렬이 계속 실행됩니다.

새로운 변수를 코드에 추가하면 이런 동작을 방지할 수 있습니다. 이를 통해 리스트가 이미 정렬되어 있다면 정렬을 조기에 중단할 수 있습니다. 앞서 작성한 sortNumbers 함수에 이 변수를 추가해 보겠습니다.

class BubbleSort {
	void sortNumbers(int array[]) {
		int size = array.length;

		for (int item = 0; item < size - 1; item++) {
			boolean hasSwapped = false;
			for (int j = 0; j < size - item - 1; j++) {
				if (array[j] > array[j + 1]) {
					int temporary = array[j];
					array[j] = array[j + 1];
					array[j + 1] = temporary;

					hasSwapped = true;
				}
			}

			if (hasSwapped == false) {
				break;
			}
		}
	}
}

코드에 세 가지 변경 사항이 있습니다. 첫 번째 for 루프 안에 'hasSwapped'라는 변수를 선언했습니다. 이 변수는 교환(swap)이 발생했는지 여부를 추적합니다. 기본값은 'false'이며, 교환이 발생하면 'true'로 설정됩니다.

for 루프의 끝에는 hasSwapped가 false인지 확인하는 if 문을 추가했습니다. 교환이 한 번도 발생하지 않았다면 배열은 이미 정렬된 상태입니다. hasSwapped가 false이면 'break' 키워드를 사용해 루프 실행을 중단합니다.

앞서 작성한 메인 프로그램으로 코드를 실행해 결과를 확인해 보겠습니다.

[2, 5, 7, 9]

리스트가 정렬되었고, 이번에는 알고리즘이 더 효율적입니다. 더 많은 값으로 이루어진 큰 리스트를 정렬한다면 이 알고리즘의 우수한 성능이 더욱 분명해질 것입니다. 이것으로 자바에서 최적화된 버블 정렬을 성공적으로 작성했습니다!

결론

버블 정렬은 리스트를 오름차순 또는 내림차순으로 정렬하는 데 사용됩니다. 인접한 값을 비교하고, 순서가 잘못되어 있으면 위치를 교환하는 방식으로 동작합니다.

버블 정렬에는 표준과 최적화된 두 가지 유형이 있습니다. 표준 버블 정렬은 미리 정해진 횟수만큼 비교를 수행하는 반면, 최적화된 버블 정렬은 리스트가 정렬되는 즉시 정렬을 중단합니다.

이제 여러분도 전문가처럼 자바 버블 정렬을 작성할 준비가 되었습니다!