버블정렬 bubble Sorting

기본적으로 ChatGPT를 이용하여 틀을 잡고 만든 것

인접한 두 개의 원소를 비교하여 큰 수를 오른쪽으로, 작은 수를 왼쪽으로 이동시키는 정렬 알고리즘

버블정렬 1

def bubble_sort(arr):
    n = len(arr)
    # 반복문을 돌면서 배열의 모든 요소를 비교
    for i in range(n-1):
        # 각 반복에서 오른쪽 끝에서부터 i번째까지 비교하면서 swap
        for j in range(n-i-1):
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j] # 한번에 swap 이 가능하다
    return arr

arr = [64, 34, 25, 12, 22, 11, 90]
bubble_sort(arr)

[11, 12, 22, 25, 34, 64, 90]

• 알고리즘
  • 첫번째 반복문
    • 모든 요소를 비교하기 위해 n-1번 비교한다.
    • n번째는 n-1에서 정해지기 때문에 할 필요가 없다.
  • 두번째 반복문
    • 오른쪽 끝에서부터 i번째부터 비교하면서 swap한다.
    • 0 ~ (n-i-1) 까지만 비교해서 가장 큰수가 두번째 반복문이 끝날 때마다 고정된다.
• 시간 복잡도
  • 최선의 경우 O(n)
  • 평균과 최악의 경우 O(n^2)
  • 이는 정렬할 리스트의 크기가 커질수록 정렬 시간이 길어진다는 것을 의미