[정렬-JAVA] 버블 정렬 (Bubble Sort)

버블 정렬(Bubble Sort)는 정렬의 과정이 수면 위로 떠오르는 거품과 비슷한 모양이라고 해서 붙여졌다고 한다. 이름이야 어쨌든 시간 복잡도가 O(N^2)로 특정 횟수 이상으로는 도저히 못 쓸 코드로 보인다. 하지만 코드의 구현이 매우 간단하고 직관적이어서 많이들 쓴다고 한다. 

최악 시간 복잡도	O(N^2)
최선 시간 복잡도	O(N)
평균 시간 복잡도	O(N^2)
공간 복잡도	O(1)

정렬의 핵심 아이디어는, 주어진 수를 오름차순으로 정리하고 싶을 때 값을 하나씩 확정하는 것이다. 5개의 수가 주어질 때 한 수와 인접한 숫자의 크기를 비교하여, 큰 값을 뒤로(오른쪽)으로 보내고 작은 값을 왼쪽(앞)으로 보내는 과정을 반복하면 5번째에는 가장 큰 수가 확정적으로 위치할 것이다. 아래의 예시를 보자.

Origin :
5 4 3 2 1
정렬 : 
4 5 3 2 1 --- 1
4 3 5 2 1 --- 2
4 3 2 5 1 --- 3
4 3 2 1 5 --- 4

3 4 2 1 5 --- 5
3 2 4 1 5 --- 6
3 2 1 4 5 --- 7

2 3 1 4 5 --- 8
2 1 3 4 5 --- 9

1 2 3 4 5 ---- 10

위의 정렬 과정을 말로 단계적으로 표현하면 다음과 같다.

1. 루프의 범위를 정한다.
2. 인접한 숫자들의 크기를 비교한다.
3. 만약 조건에 부합하다면, swap한다.
4. 루프가 끝날 때 까지 2, 3 과정을 반복한다.
5. 루프가 끝나면 새로운 정렬 영역을 지정한다.
6. 정렬이 완료될 때 까지 반복한다.

위 과정의 자바 코드는 아래와 같다.

import java.util.Arrays;
import java.util.Scanner;

public class BubbleSort {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int[] arr = new int[N];
		for(int i = 0; i<N; i++) arr[i] = sc.nextInt(); // 정렬하고자 하는 배열 입력 받기
		
		for(int i = 0; i<N-1; i++) {
			for(int j = 0; j<N-1-i; j++) { // 정렬 영역 설정
				if(arr[j] > arr[j+1]) { //인접한 두 수를 비교, swap하기
					int tmp = arr[j];
					arr[j] = arr[j+1];
					arr[j+1] = tmp;
				}
			}
		}
		System.out.print(Arrays.toString(arr));
		
		sc.close();
	}
}

 

아래 링크는 버블 정렬 과정을 애니메이션으로 보여주는 사이트다. 참고해도 좋을 것 같다.

https://www.toptal.com/developers/sorting-algorithms/bubble-sort