[알고리즘] 03. Java 정렬 알고리즘 - 버블 정렬

 

 

 

 

 

안녕하세요🖐️

 

이번시간에는 정렬 알고리즘 중 하나인 버블 정렬에 대해 간단히 알아보는 시간을 갖겠습니다~

 

 

 

 

---

버블 정렬 (Bubble Sort)

버블 정렬은 정렬 알고리즘 중 가장 이해하기 쉽고 구현하기 간단한 알고리즘입니다. 하나의 배열이 주어졌을 때, 배열의 각 원소를 순차적으로 비교하고, 인접한 원소끼리의 순서가 잘못되어 있으면 서로 위치를 바꿔주는 과정을 반복합니다. 이 과정을 배열의 길이만큼 반복하면서, 각 반복마다 최소 하나의 원소가 최종 위치로 이동합니다.

 

버블 정렬의 작동방식을 순서대로 나열하면 아래와 같은 과정을 진행합니다. (오름차순)

1. 배열의 첫 번째 원소부터 시작하여 인접한 원소와 비교합니다.
2. 현재 원소가 다음 원소보다 크면, 두 원소의 위치를 바꿉니다.
3. 다음 인접한 원소로 이동하여 같은 과정을 반복합니다.
4. 배열의 끝에 도달할 때까지 이 과정을 반복하며, 각 단계마다 가장 큰 원소가 배열의 끝으로 이동하게 됩니다.
5. 배열의 모든 원소가 정렬될 때까지 전체 과정을 반복합니다.

 

다음 예시로 버블 정렬이 어떻게 진행되는지 확인해 보겠습니다.

Int[] array = {4, 7, 2, 5, 1, 3, 6};

이런 배열이 있다고 가정해 보겠습니다. 이 배열을 오름차순으로 버블 정렬을 진행하게 되면 아래와 같이 정렬이 진행됩니다.

버블 정렬 예시

1. 배열의 첫 번째 원소인 4와 두 번째 원소인 7을 비교합니다. 4는 7보다 작기 때문에 위치를 바꾸지 않습니다.
2. 두 번째 원소인 7과 세 번째 원소인 2를 비교합니다. 7이 2보다 크기 때문에 두 원소의 위치를 바꿉니다.
3. 7은 세 번째 위치로 이동했고, 이것을 다음 원소인 5와 비교합니다. 7이 5보다 크므로, 위치를 바꿉니다.
4. 7은 네 번째 위치로 이동했고, 이것을 다음 원소인 1과 비교합니다. 7이 1보다 크므로, 위치를 바꿉니다.
5. 7은 다섯 번째 위치로 이동했고, 이것을 다음 원소인 3과 비교합니다. 7이 3보다 크므로, 위치를 바꿉니다.
6. 7은 여섯 번째 위치로 이동했고,  이것을 다음 원소인 6과 비교합니다. 7이 6보다 크므로, 위치를 바꿉니다.

7이 배열의 끝으로 이동했으므로, 다음 반복에서는 7을 제외하고 이전 단계들을 다시 반복합니다. 이 과정은 배열의 모든 원소가 올바른 순서로 정렬될 때까지 계속됩니다.

 

최종 정렬이 된 배열은 [1, 2, 3, 4, 5, 6, 7] 입니다.

 

 

 

 

---

버블 정렬 실습

아래의 실습 예제와 함께 버블 정렬을 구현해 보겠습니다.

 

- 실습 예제 -

public class BubbleSort {

	void bubbleSort(int[] arr) {
		
		int n = arr.length;
        
		// 배열의 마지막 길이 -1 까지 반복한다.
		for (int i = 0; i < n-1; i++) {
			// 인접한 원소들을 비교하고, 필요한 경우 위치를 바꾸기 위해 배열을 순회한다. 
			// 각 순회마다 이미 정렬된 마지막 원소는 제외하고 비교한다.
			for (int j = 0; j < n-i-1; j++) {
				// 이전 원소가다음 원소보다 클 경우 바꿔준다.
				if (arr[j] > arr[j+1]) {
					int temp = arr[j];
					arr[j] = arr[j+1];
					arr[j+1] = temp;
				}
			}
		}
	}
	
	public static void main(String[] args) {
		// BubbleSort 클래스 인스턴스 생성
		BubbleSort bs = new BubbleSort();
    	
		int[] arr = {4, 7, 2, 5, 1, 3, 6};
        
		// BubbleSort 클래스의 bubbleSort 메소드 접근
		bs.bubbleSort(arr);
        
		for (int i=0; i < arr.length; i++)
			System.out.print(arr[i] + " ");
    }
}

- 출력 결과 -

1 2 3 4 5 6 7

 

 

 

 

---

시간복잡도

버블 정렬의 시간 복잡도는 아래와 같습니다.

 

 

- 최악의 경우 시간 복잡도: O(n^2)

배열이 역순으로 정렬되어 있어서, 모든 원소들이 각각 비교되고 위치가 교환되어야 하는 경우입니다.

 

- 최선의 경우 시간 복잡도: O(n)

배열이 이미 정렬되어 있는 경우입니다.

 

- 평균 시간 복잡도: O(n^2)

원소들이 무작위로 배치되어 있는 평균적인 상황입니다.

 

 

버블 정렬은 그 구현의 단순성으로 인해 초보 프로그래머에게 알고리즘의 기본 개념을 가르치는 데 자주 사용됩니다. 하지만 비효율적인 시간 복잡도로 인해 대규모 데이터셋에는 적합하지 않으며, 실제 응용에서는 더 효율적인 정렬 알고리즘들이 선호됩니다.

 

 

* 시간 복잡도에 대한 내용은 아래 글에서 확인할 수 있습니다.

[알고리즘] 복잡도란? (시간복잡도, 공간복잡도)

[알고리즘] 복잡도란? (시간복잡도, 공간복잡도)

 

 

 

 

 

 

 

 

이상으로 정렬 알고리즘 중 하나인 버블 정렬에 대해 알아보는 시간을 마치겠습니다!

 

읽어주셔서 감사합니다 😊

 

---

소스 코드 바로가기