버블 정렬(Bubble Sort)

버블 정렬(Bubble Sort)

배열의 이웃한 두 요소의 대소관계를 비교하여 교환을 반복함으로써 이루어지는 정렬

 

시간복잡도 : O(N²)

배열의 크기가 N개 일 때, 이중 반복문을 사용하기 때문에 N의 제곱만큼의 시간 복잡도가 생긴다.

 

 

 

[예제]

배열 arr의 요소가 5 2 3 8 1 4 6 일 때, 배열을 버블 정렬을 통해 오름차순으로 정렬하기

 

배열의 첫번째 요소부터 인접한 요소와 비교하기 시작한다.

세번째 요소(5)와 네번째 요소(8)는 비교 결과, 5보다 8이 더 크므로 교환하지 않는다.

첫 번째 반복문이 종료되면 배열의 가장 마지막에 8이 위치하게 되고, 마지막 요소는 정렬된 상태가 된다.

두번째는 첫 번째 요소부터 4번째 요소까지 인접한 요소들간의 비교가 이루어진다.

반복문이 종료되면 5번째 위치에 6이 들어가며, 6과 8은 정렬이 완료된 상태이다.

첫 번째 요소부터 3번째 요소까지 인접한 요소끼리의 비교 및 교환이 일어난다.

4번째 요소까지 비교가 완료되면, 4번째 요소에 5가 위치하게 된다.

 

첫 번째 위치부터 2번째 위치까지 인접한 요소와의 비교가 이루어진다.

반복문이 끝나면 3번째 위치에 4가 들어가게 되며 4, 5, 6, 8 은 정렬된 상태가 된다.

1과 2, 2와 3을 비교하면 된다.

1과 2의 비교에서 2가 1보다 더 크므로 비교만 하고 교환은 하지 않는다.

마찬가지로, 3이 2보다 더 크므로 비교만 하고 교환은 하지 않는다.

마지막으로 1과 2의 비교를 한다. 2는 1보다 크므로 비교는 하되 교환은 하지 않는다.

최종 오름차순으로 정렬된 결과는 아래와 같다.

 

 

소스 코드 : 

	public static void bubbleSort(int[] arr, int n) {

		for (int i = 0; i < n - 1; i++) {
			for (int j = 0; j < n - i - 1; j++) {
				if (arr[j] > arr[j + 1]) {
					swap(arr, j, j+1);
				}
			}
		}
	}

결과 :