[Algorithm] 버블 정렬 (python)

버블 정렬

버블 정렬은 인접한 두 데이터끼리 크기를 비교해가며 정렬하는 방식이다.

오름차순으로 정렬하기

input = [4, 6, 2, 9, 1]

def bubble_sort(array):
    # 이 부분을 채워보세요!
    for i in range(len(array)-1):
        for j in range(len(array)-1-i):
            if array[j] > array[j+1]:
                array[j], array[j+1] = array[j+1], array[j]
    return array

bubble_sort(input)
print(input)  # [1, 2, 4, 6, 9] 가 되어야 합니다!

print("정답 = [1, 2, 4, 6, 9] / 현재 풀이 값 = ",bubble_sort([4, 6, 2, 9, 1]))
print("정답 = [-1, 3, 9, 17] / 현재 풀이 값 = ",bubble_sort([3,-1,17,9]))
print("정답 = [-3, 32, 44, 56, 100] / 현재 풀이 값 = ",bubble_sort([100,56,-3,32,44]))

• 2중 for문을 통해 정렬이 이루어진다.
  • 데이터의 크기만큼 반복했다가, 횟수가 1씩 줄어들면서 반복한다.
  • 안쪽 for문에서 len(array)-1-i의 의미는 다음과 같다.
    • 마지막 원소까지 비교를 하지 않기 때문이다.
    • 한 번 for문이 돌면, 가장 큰 값은 맨 뒤로 이동하고, 정렬이 된 상태기 때문에 비교할 필요가 없다.
  • 바깥쪽 for문은 전체 반복 횟수 (정렬할 데이터의 크기-1)
  • 한 번 정렬을 하면, 가장 큰 값이 가장 맨 뒤로 이동되기 때문에 안쪽 for문은 '-i'로 범위를 축

[출력]
[1, 2, 4, 6, 9]
정답 = [1, 2, 4, 6, 9] / 현재 풀이 값 =  [1, 2, 4, 6, 9]
정답 = [-1, 3, 9, 17] / 현재 풀이 값 =  [-1, 3, 9, 17]
정답 = [-3, 32, 44, 56, 100] / 현재 풀이 값 =  [-3, 32, 44, 56, 100]