📚 Bubble Sort

가장 직관적인 정렬 알고리즘이 아닐까 싶다.
배열의 앞에서부터 차근차근 올라가면서 바꿔주는 게 거품이 뽀글뽀글 올라오는 것 같다고 해서 붙은 이름.

💻 Implementation

class BubbleSort {
	public static void main(String[] args) {
		int[] arr = {9, 4, 2, 1, 3, 5};

		int tmp;
		for (int i=0;i<arr.length;i++) {
			for (int j=0;j<arr.length-i-1;j++) {
				if (arr[j] > arr[j+1]) {
					tmp = arr[j];
					arr[j] = arr[j+1];
					arr[j+1] = tmp;
				}
			}
		}
		for (int i=0;i<arr.length;i++)
			System.out.print(arr[i] + " ");
	}
}

⌛️ Time Complexity

시간복잡도는 O(n^2)이다.
리스트의 요소를 처음부터 끝까지 n번 순회하고, 그 안에서도 최대 n-k (k는 상수) 번 순회하기 때문.
그러니까 kn^2꼴이 될 텐데, asymptotic notation에서는 상수를 무시하므로 O(n^2)이 될 것이다.

🛩 is this stable?

Yes! 교환이 밀착된 요소들끼리 이루어지므로 stable하다.
여기서 stable이란, 리스트의 중복된 요소의 순서가 정렬 이후에도 보장되는지를 뜻한다.