버블정렬

버블솔트

• 인접한 두 개의 원소를 비교하며 자리를 계속 교환하는 방식
• 정렬 과정
  • 첫 번째 원소부터 인접한 원소끼리 계속 자리를 교환하면서 맨 마지막자리까지 이동한다.
  • 한 단계가 끝나면 가장 큰 원소가 마지막 자리로 정렬된다
  • 교환되면 자리를 이동하는 모습이 물 위에 올라오는 거품 모양과 같다고 하여 버블 정렬이라고 한다.
• 시간복잡도 : O(n^2)

def bubble_sort(num):
    #원소의 마지막 부터
    #why? 최대값부터 마지막에 박고 오름차순으로 정렬할 것이기 때문
    for i in range(len(num)-1,0,-1) :
        #0번 index부터 i번째 index까지
        for j in range(0,i) :
            #num[j]가 num[j+1]보다 크면
            if num[j] > num[j+1] :
                #위치 변경
                num[j],num[j+1] = num[j+1],num[j]
    return num
num = [54,26,93,17,77,31,44,55,20]

print(bubble_sort(num))

1. 원소의 마지막부터 -1씩 후진하면서 시작해 최대값부터 마지막에 위치시킴
2. 0번째부터 i번째까지 왼쪽이 오른쪽보다 크면 자리 변경
3. 그럼 마지막 값은 가장 큰 값으로 갱신
4. 그럼 이제 -2번째를 진행
5. 계속 순환하면 정렬끝