Bubble Sort

접근

• 맨 왼쪽 원소부터 바로 이웃한 원소와 비교하며, 큰 수가 오른쪽으로 가도록 교환
• 맨 끝까지 가면 가장 큰 원소를 찾은 것이기 때문에, 이 과정을 다시 나머지 n-1개 수에 대해서 반복한다.

• 정확성

  • 제일 큰 원소가 제일 뒤에 위치하고, 그 다음 큰 원소는 그 앞에 위치한다. 이를 반복하니 정확함은 자명

• 시간 복잡도

  • 가장 큰 원소를 구하기 위해 n-1번 비교
  • 그 다음 원소를 구하기 위해 n-2번 비교
  • …
  • $(n-1)+(n-2)+...+1=\theta(n^2)$

• 버블 정렬의 특징

  • 입력과 무관하게 n개의 값을 정렬할 때 항상 똑같은 횟수의 비교를 수행한다.

구현

def bubblesort(L):
    result = list(L)
    for i in range(len(L)-1):
        for j in range(len(L)-i-1):
            if result[j] > result[j+1]:
                result[j], result[j+1] = result[j+1], result[j]

    return result