Bubble Sort (거품 정렬)

이번 글에서는 정렬 알고리즘들 중에 가장 기초적인 거품 정렬에 대해 살펴보겠다. 만약 알고리즘 스터디, 혹은 컴퓨터 공학 과정에서 자료구조 중에 정렬 알고리즘들을 배웠다면, 아마 거품 정렬을 제일 먼저 접해봤을 것이다.

 

 

간략하게 설명하자면, 배열 A에서 위치 x가 주어졌다. 그럼 A[x] > A[x + 1]을 비교하게 된다. 만약 진짜 A[x] > A[x + 1]이 맞으면, A[x]값과 A[x + 1] 값이 서로 교체 (swap)한다. 그리고 비교 지점이 한 칸씩 앞으로 이동한다. 만약 마지막 위치가 n이고 배열 A[n - 1]과 A[n] 비교가 마치면, 다시 첫번째 배열 위치 A[0]로 돌아가서 다시 A[1]을 비교하게 된다. 모든 배열들이 정렬했을 때 까지 이런식으로 반복된다.

만약 위에 있는 글이 이해하기 힘들었다면 아래 비주얼을 참고하자.

메서드: 네이브 (Naive)

의사코드는 다음과 같다.

 

  Bubble-Sort(A)
    for i = 1 to A.length
        // Traverse through array
        for j = A.length to i + 1
            if A[j] > A[j + 1]
                  Exchange A[j] with A[j - 1]

 

이 알고리즘도 역시 for loop 두 개가 겹쳐있어서 총 시간 복잡도는 O(n^2)이다. 공간 복잡도 마저 O(1)이라 이 알고리즘 역시 메모리가 압박할 때 응용하기 좋은 알고리즘이다. 

 

 

 

 

아래 레포지토리에서 거품 정렬을 응용한 프로그램을 완성하셨다. 응요하기 위해 참고하는 것도 좋을 것 같다. 

 

yoonBot/Algorithm-Collection