[Sort] 버블정렬 (Bubble Sort)

버블정렬 (Bubble Sort)

버블정렬에 대해서 알아보겠습니다. 버블 정렬은 자기자신 뒤에 오는 요소와 끊임없이 비교하면서, 오름차순일 경우 가장 큰 수가 뒤에서부터 정렬되는 정렬알고리즘입니다. 

또한 마지막 Sorting시에는 첫번째 요소를 제외하고 모두 정렬됐기 때문에 자연스럽게 첫번째정렬됩니다.

그림을 보면서 이해해 봅시다. 우선 5와 3을 비교하고 5가 더 크기 때문에 교환합니다.

다음 버블인 5와 4를 비교하고 5가 더 크기 때문에 교환합니다. 이제 5와 1을 비교하고 5가 더 크기 때문에 교환한 후 정렬 1회전을 종료합니다. 5가 가장 큰 수였기 때문에 차례대로 진행되는 모든 비교에서 이기고 결국 제일 큰 숫자의 자리인 끝의 자리를 차지하게 됩니다.

다음 2회전을 보겠습니다.

3과 4를 비교하고 4가 더 크니까 아무 교환 없이 다음을 진행합니다. 다음 버블인 4와 1을 비교합니다. 4가 1보다 크기 때문에 교환합니다. 이제 5와 비교를 해야 하지만, 5는 정렬이 완료된 상태이기 때문에 비교할 필요가 없습니다. 4는 현재 위치에서 정렬됩니다. 이런 식으로 버블정렬은 오름차순일 경우 큰 숫자부터 뒤에서 정렬을 합니다.

위 원리를 코드로 나타내면 다음과 같습니다. 

package Sort;

import java.util.Arrays;

public class BubbleSort {

	public static void main(String[] args) {
		int[] array = {5, 3, 4, 1};

		System.out.println("Before   : " + Arrays.toString(array) + "\n");
		bubbleSort(array);

	}

	private static void bubbleSort(int[] array) {
		int temp = 0;
		int size = array.length - 1;
		for (int i = 0; i < size; i++) {
			for (int j = 0; j < size-i ; j++) {
				if (array[j] > array[j + 1]) {
					temp = array[j];
					array[j] = array[j + 1];
					array[j + 1] = temp;

				}
			}
			System.out.println((i + 1) + "회전 bubble sort result : " + Arrays.toString(array));
		}

	}

}

	

시간의 복잡도는 n-1,n-2,n-3 .... 1 -> O(n^2)

공간의 복잡도는 하나의 배열에서만 진행되기 때문에 O(n)

참고로 버블 정렬은 위에 보시다시피 원소의 이동이 수면 위로 올라오는 거품과 비슷하다고 해서 지어진 이름입니다. ㅎㅎ