반드시 알아야하는 알고리즘 top 8 - 4. 버블 정렬

반드시 알아야 하는 알고리즘 top 8

• 재귀 알고리즘 

• 이진 탐색 

• 순차 탐색

• 버블 정렬

• 삽입 정렬

• 탐욕 알고리즘

• 최단거리 알고리즘

• 몬테 카를로 알고리즘

버블 정렬 

• 버블 정렬은 두 인접한 값들을 검사하여 정렬하는 방법입니다. 시간이 매우 오래 걸리는 알고리즘 중 하나지만 코드가 단순하기 때문에 자주 사용되는 방법입니다. 값들이 정렬되는 과정이 거품이 수면으로 올라오는 듯한 모습을 보이기 때문에 지어진 이름 입니다. 다음 동영상을 통해 세부 과정을 살펴보겠습니다.

버블 정렬 코드 01 : Python 

a = [3,2,4,1]

for i in range(len(a)):

    for j in range(len(a)-1-i):

        if a[j] > a[j+1]:

            a[j], a[j+1] = a[j+1], a[j]

• 버블 정렬을 간단히 구현한 코드 입니다. for loop 문 두개로 간단하게 구현할 수 있다는 점이 장점입니다만 모든 수들을 계산해야 하기 때문에 오래 걸리는 부분이 단점 입니다.

i = 0  j = 0  a =  [2, 3, 4, 1]

i = 0  j = 1  a =  [2, 3, 4, 1]

i = 0  j = 2  a =  [2, 3, 1, 4]

i = 1  j = 0  a =  [2, 3, 1, 4]

i = 1  j = 1  a =  [2, 1, 3, 4]

i = 2  j = 0  a =  [1, 2, 3, 4]

[1, 2, 3, 4]

• 위의 코드는 다음처럼 진행 됩니다. i = 0 일 때 가장 마지막 숫자가 정렬되고, i = 1 일 때 뒤에서 2번째 숫자가 정렬되는 형식으로 for loop 문이 한 번씩 진행될 때마다 하나씩 정렬되는 알고리즘 입니다.

버블 정렬 코드 02 : Python 

• 두 번째로 구현한 코드는 재귀알고리즘을 사용한 버블 정렬 코드 입니다.

def bubble_sort(n = 0, i = 0):

    global a

    if i == len(a)-1:

        return

    else:

        if n < len(a) -1:

            if a[n] > a[n+1]:

                a[n],a[n+1] = a[n+1],a[n]

            bubble_sort(n+1,i)

        else:

            bubble_sort(0,i+1)

• 위의 코드를 단순히 재귀함수로 변환한 것이기 때문에 조건들이나 해당조건 시 실행하는 것들이 자세히 살펴보면 다를 바 없습니다.

---

부족한 블로그에 방문해 주셔서 감사합니다.

잘못된 부분이나 질문이 있으시면 

댓글로 말씀해주세요.

금방 확인하고 피드백 드리겠습니다.

좋은 하루 되세요. ^^