버블 정렬 Bubble Sort

Intro::

버블 정렬에 대해 알아보자.

정의

서로 인접한 두 원소의 대소를 비교하여 자리를 교환하는 정렬 알고리즘

• 1 회전
• 0 - 1 비교, 1 - 2 비교 …. n-2 - n-1 비교

• 2회전
• 0 - 1 비교, 1 - 2 비교 …. n-3 - n-2 비교

시간 복잡도

Code

package algorithm;

import java.util.Arrays;

public class BubbleSort {
	public static void main(String[] args) {
		Integer[] list = {2, 6, 1, 5, 4, 3};
		boolean sorted = false;
		for (int i = 0; i < list.length - 1 && !sorted; i++) {
			sorted = true;
			for (int j = 1; j < list.length - i; j++) {
				if (list[j - 1] > list[j]) {
					sorted = false;
					int tmp = list[j - 1];
					list[j - 1] = list[j];
					list[j] = tmp;
				}
			}
			System.out.println(i+1 + "회전: " + Arrays.toString(list));
		}
	}
}


/*

1회전: [2, 1, 5, 4, 3, 6]
2회전: [1, 2, 4, 3, 5, 6]
3회전: [1, 2, 3, 4, 5, 6]
4회전: [1, 2, 3, 4, 5, 6]

*/

References::