버블 정렬의 시간복잡도가 O(n^2)이 아닐 수 있다고?

버블 정렬(Bubble Sort)

설명 : 거품이 수면으로 올라오는 듯 하여 붙여진 버블정렬. 인접한 두 수를 비교하여 오름차순or 내림차순. 안정성은 보장한다.

요약 정리

사실 일반적인 상황에서 버블 정렬의 시간복잡도는 O(n^2) 맞다.
여기서 일반적인 상황이란 array를 기준으로 구현이 되어있을 경우이다.

하지만 만약에 LinkedList라면????
n번째 원소를 접근하는데 n의 시간이 걸리고 이것을 n^2을 반복하면서 시간복잡도가 O(n^3)이 되어버릴 것이다.

즉 함수의 시간복잡도를 측정하는 과정에서 추상화된 하위 함수의 시간복잡도가 영향을 끼칠 수 있다는 것이다.

이런 관점에서 보면 삽입 정렬은 LinkedList가 훨씬 유리할 것이다.
면접에서 버블 정렬의 시간 복잡도를 묻는 다면 이렇게 말해보는건 어떨까?
Array로 구현이 되어 있다면 O(n^2)이지만 만약 Linked List라면 O(n^3)입니다.

버블정렬 코드

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
public class Main {

	public static void main(String[] args) {
		List<Integer> arrayList = new ArrayList<>();
		List<Integer> linkedList = new LinkedList<>();
		
		for(int i=2000; i>=0; i--) {
			arrayList.add(i);
			linkedList.add(i);
		}
		
		System.out.println("array List 버블 정렬 시작");
		bubble_sort(arrayList, arrayList.size());
		System.out.println("Linked List 버블 정렬 시작");
		bubble_sort(linkedList, linkedList.size());
	}

	private static void bubble_sort(List<Integer> list, int size) {
		long beforeTime = System.currentTimeMillis();
		for(int i = 1; i < size; i++) {
			for(int j = 0; j < size - i; j++) {
				if(list.get(j) > list.get(j + 1)) {
					int temp = list.get(j);
					list.set(i, list.get(j + 1));
					list.set(j, temp);
				}
			}
		}
		long afterTime = System.currentTimeMillis();
		long secDiffTime = (afterTime - beforeTime);
		System.out.println("버블 정렬을 실행하는데 걸린 시간: " + secDiffTime);
	}
}

시간 측정

단위 ms
linked list의 실행시간이 arrayList에 비해 기하급수적으로 늘어나는 것을 볼 수 있다

i	100	200	400	800	1600	3200	6400
ArrayList	2	4	13	21	32	61	163
LinkedList	2	10	37	306	2733	20429	165722