버블 정렬 (Bubble Sort)

소개

• 배열의 인접한 두 요소 값들을 비교하여 정렬한다.

 

 

과정

 

 

코드

• \(j\) 인덱스 값이 \(j + 1\) 인덱스 값보다 크다면 두 숫자의 위치를 바꿔준다.
• 첫 번째 for문이 한 번 종료될 때마다 가장 마지막 인덱스에 숫자가 하나씩 정렬된다.

public static void main(String[] args) {
	int[] nums = { 6, 7, 2, 8, 1, 4 };
	int len = nums.length;

	for (int i = 0; i < len - 1; ++i) {
		for (int j = 0; j < len - i - 1; ++j) {

			if (nums[j] > nums[j + 1])
				Swap(nums, j, j + 1);
		}
	}
}

 

 

결과

 

 

계산 복잡도

Time Complexity : for문 두 개가 지배하며, \((N-1) + (N -2 ) + ... + 1 = \frac{(N-1)*(N)}{2}\)

• Best : \(O(N^2)\)
• Average : \(O(N^2)\)
• Worst : \(O(N^2)\)

Space Complexity : \(O(1)\)