버블 정렬(bubble sort)

버블 정렬이란?

• 서로 인접한 두 원소를 검사하여 정렬하는 알고리즘

 

구현

numList=[1,9,5,6,8]

def bubbleSort(numList):
    leng=top=len(numList)

    for i in range(leng-1):
        top-=1
        for j in range(top):
            if numList[j]>numList[j+1]:
                temp=numList[j]
                numList[j]=numList[j+1]
                numList[j+1]=temp

bubbleSort(numList)

특징

• 장점
  • 구현이 매우 간단하다.
• 단점
  
  • 하나의 요소가 가장 왼쪽에서 가장 오른쪽으로 이동하기 위해서는 배열에서 모든 다른 요소들과 교환되어야 한다.
  • 일반적으로 자료의 교환 작업(SWAP)이 자료의 이동 작업(MOVE)보다 더 복잡하기 때문에 버블 정렬은 단순성에도 불구하고 거의 쓰이지 않는다.

시간복잡도

• 비교 횟수
  • n-1, n-2, … , 2, 1 번 = 등차수열의 합 = 항의 개수(첫째항+마지막항)/2 =  n(n-1)/2
• 교환 횟수
  • 입력 자료가 역순으로 정렬되어 있는 최악의 경우, 한 번 교환하기 위하여 3번의 이동(SWAP 함수의 작업)이 필요하므로 (비교 횟수 * 3) 번 = 3n(n-1)/2
• T(n)=O(n^2)