버블정렬

• 이웃하는 숫자를 비교하여 작은 수를 앞으로 이동시키는 과정을 반복하여 정렬
• 작은 수는 배열의 앞부분으로 이동하는데, 배열을 좌우가 아니라 상하로 그려보면 정렬하는 과정에서 작은 수가 마치 거품처럼 위로 올라가는 것을 연상케함

1. 버블 정렬의 수행과정 예제

• 패스(pass): 입력된 배열의 전체 요소를 1번 처리하는 것
• 1패스
  
• 2패스
  
• 3패스
  

2. 알고리즘

for pass = 1 to n-1
  for i=1 to n-pass
    if A[i-1] > A[i]
      sweep(A[i-1], A[i])

3. 시간복잡도

• for문: (n-1)+(n-2)+(n-3)+(n-4)+...+1 = n(n-1)/2
• for문 내: O(1)
• 최종결과: O(n^2)