버블 정렬.

정렬 방법론.

1. N번째 위치와 N+1번째 위치의 값을 비교해서, N+1번째 위치의 값이 더 클 경우 N번째와 N+1번째의 값을 교환함. 

특징.

1. 계속 비교하므로 리스트 크기가 크면 불리하다.

2. 정렬이 거의 된 데이터일 경우 더 유리하다.(교환이 적게 일어나므로)

3. 데이터가 역순인경우, 즉 최악의경우에 시간이 엄청 느리다.

N개의 원소에 대해서 N-1번의 비교를 해야 되기 때문에

비교횟수는 N(N-1)2, 시간 복잡도는 O(n^2) 이 된다.

10000개의 데이터를 돌려봤는데 예상한대로 나왔다.

시간복잡도가 같이 n^2인데도 시간 차이가 나는건 위에서 언급했듯이 최악의 경우에 교환이 더 많이 일어나서 오래걸리는것으로 보인다.

# -*- encoding: cp949 -*-
import time
import random

N = 10000
def swap(a,i,j):
    a[i],a[j] = a[j],a[i]

def CheckSort(a,n):
    Sorted = True
    for i in range(n):
        if a[i] > a[i+1]:
            Sorted = False
        if not Sorted:
            break
    if Sorted: print '정렬 완료.'
    else: print '정렬 오류 발생.'

def BubbleSort(a,N): #버블 정렬
    for i in range(N,0,-1):
        for j in range(1,i):
            if a[j] > a[j+1]:
                swap(a,j,j+1)

def main():
    a = [random.randint(1,65536) for i in range(N+1)] #랜덤한 10000개의 데이터
    start_time = time.time()
    BubbleSort(a,N)
    print '(랜덤)버블 정렬의 실행 시간 (N = {} ) : {}'.format(N,time.time()-start_time)
    CheckSort(a,N)

    a = [i for i in range(N+1)] #정렬된 10000개의 데이터
    start_time = time.time()
    BubbleSort(a,N)
    print '(최고)버블 정렬의 실행 시간 (N = {} ) : {}'.format(N,time.time()-start_time)
    CheckSort(a,N)

    a = [i for i in range(N,-1,-1)] #최악의 경우의 10000개의 데이터
    start_time = time.time()
    BubbleSort(a,N)
    print '(최악)버블 정렬의 실행 시간 (N = {} ) : {}'.format(N,time.time()-start_time)
    CheckSort(a,N)

if __name__=='__main__':
    main()