[배열] 버블 정렬 (Bubble sort)

버블 정렬이란?

버블 정렬 또는 거품 정렬은 정렬 알고리즘 중 하나이다. 시간 복잡도가 O(n^{2})로 상당히 느리지만, 코드가 단순하기 때문에 자주 사용된다. 원소의 이동이 거품이 수면으로 올라오는 듯한 모습을 보이기 때문에 지어진 이름이다.

---

버블 정렬의 장점

1. 코드가 단순하다.

2. 추가적인 메모리를 필요로 하지 않는다.

3. 작은 데이터셋에서는 효과적이다.

---

버블 정렬의 단점

1. 큰 데이터셋에서는 매우 비효율적이다.

2. 다른 정렬 알고리즘에 비해 느리다.

---

버블 정렬의 알고리즘

버블 정렬은 기본적으로 배열의 두 수(a, b)를 선택한 뒤, 만약 그 두 수가 정렬되었다면 놔두고 아니라면 두 수를 바꾸는 방식으로 진행된다. 오름차순으로 정렬할 때는 
a>b여야 정렬된 것으로 판단한다. 이를 배열의 처음부터 끝까지 반복한다. (내림차순이라면 a<b)

위 알고리즘을 배열에 아무 변화가 없을 때까지 반복한다.

---

코드

public static void main(String[] args) {

		int[] arr = new int[5]; // 5개의 정수를 저장하는 배열 arr 할당

		arr[0] = 3; // 0번 index에 3 저장
		arr[1] = 2; // 1번 index에 2 저장
		arr[2] = 5; // 2번 index에 5 저장
		arr[3] = 1; // 3번 index에 1 저장
		arr[4] = 4; // 4번 index에 4 저장

		// 정렬을 몇번할지 결정하는 반복문
		// 배열의 요소개수만큼 수행하겠다! == 5번 정렬하겠다!
		while (true) { // 배열을 완료할 때까지 무한 루프
			boolean flag = true; // flag가 false 일 때만 결과값 출력

			// 배열을 1회 정렬할때 사용되는 반복문
			for (int i = 0; i < arr.length - 1; i++) {

				// 임시 저장변수, 임시 변수
				// 변수값들을 서로 교환하려면 반드시 tmp가 필요함!
				// tmp,temp 변수명이 발견된다면?
				// 아~ 교환하려나보다~~ 예상가능함

				if (arr[i] > arr[i + 1]) {
					int temp = arr[i];
					arr[i] = arr[i + 1];
					arr[i + 1] = temp;
					flag = false;
				}
			}
			// 1번 정렬을 마친상태 == 1회전 정렬이 끝났다.

			if (flag) { // 배열에 변화가 이루어지지 않았다면
				break; // 출력 코드에 닿지 않게 함
			}
			
			// 배열에 변화가 이루어졌다면 출력

			for (int p = 0; p < arr.length; p++) {
				System.out.print(arr[p] + " ");
			}

			System.out.println();
		}

	}

---

결과

2 3 1 4 5

2 1 3 4 5

1 2 3 4 5

---