KoreanFoodie's Study

버블 정렬(Bubble Sort) - 파이썬 코드 구현 본문

Data Structures, Algorithm

버블 정렬(Bubble Sort) - 파이썬 코드 구현

hashnut 2019.09.19 15:59

Bubble sort python code implementation.
버블 정렬을 파이썬 코드로 구현해 보자.


버블 정렬 (Bubble Sort)

위키피디아의 정의를 참고해 보자.

: 거품 정렬(Bubble sort)은 두 인접한 원소를 검사하여 정렬하는 방법이다. 시간 복잡도가 O(n^2)으로 상당히 느리지만, 코드가 단순하기 때문에 자주 사용된다. 원소의 이동이 거품이 수면으로 올라오는 듯한 모습을 보이기 때문에 지어진 이름이다.

예시를 통해 버블 정렬이 어떻게 동작하는지 알아보자.

버블 정렬은 매우 단순한데, 그냥 처음부터 2개씩 짝을 지어 값을 비교한 후, 작은 녀석은 앞으로, 큰 녀석은 뒤로 보내면 된다.

(55, 07)은 (07, 55)로, (55, 78)은 그대로, (78, 12)는 (12, 78)로, (78, 42)는 (42, 78)이 된다.

버블 정렬은 이 과정을 단순히 배열의 길이만큼 반복하면 된다.

이제 버블 정렬을 파이썬 코드로 구현해 보자.

# Bubble sort implementation
import sys #for sys.maxsize

array1 = [4,3,9,1,5,6,7,22,3243,436,56,4,73,45,24,23,5]
array2 = [100]

def swap(array, a, b):
    array[a], array[b] = array[b], array[a]

def bubble_sort(input):

    for i in range(len(input)-1):

        for j in range(len(input)-1):
            if input[j] > input[j+1]:
                swap(input, j, j+1)

    return input


def print_array(input):
    for i in range(len(input)):
        print(input[i], end=' ')
    print()

print_array(array1)

array3 = bubble_sort(array1)
bubble_sort(array3)

print_array(array3)
0 Comments
댓글쓰기 폼