Best Case : $\Omega(n)$

Average Case : $\Theta(n^2)$

Worst Case : $O(n^2)$

우리말로 버블 정렬이라고 하는 Bubble Sort 알고리즘은 앞에서부터 2개씩 서로를 비교해가는 것이다.

[출처] : ESSLAB "Algorithm" Lecture Note - Elementary Sorting

1. 1번째 원소와 2번째 원소를 비교한다.
2. 이때 앞의 원소가 더 크면 서로를 swap한다.
3. 1~2의 과정을 원소의 개수만큼 반복한다.
4. 1~3의 과정을 원소의 개수만큼 반복한다.

N개의 원소를 갖는 배열에서 1~2의 과정을 N번 반복하게 되면 맨 마지막 원소만 정렬되게 된다. 이를 다시 원소의 개수만큼 정렬시키면 모든 원소가 정렬되게 된다.

Pseudo Code

BUBBLE-SORT(A)
  for i=0 to n-1
    for j=0 to n-1-i
	  if leftElement > rightElement
			do swap(leftElement, rightElement)
end

C Code