반드시 알아야하는 알고리즘 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)

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

---

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

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

댓글로 말씀해주세요.

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

좋은 하루 되세요. ^^