bubble sort

정렬되는 모양이 거품이 올라가는 모양과 비슷하여 거품 정렬이라고 한다.

배열에 5,  4, 3, 2, 1이 있을때 버블 정렬 순서는 다음과 같다.

Step-1: 4 3 2 1 5
Step-2: 3 2 1 4 5
Step-3: 2 1 3 4 5
Step-4: 1 2 3 4 5


버블정렬의 복잡도


(N-1) + (N-2) + ... + 2 + 1 = (N-1) * N/2 = N(N-1) / 2

C 코드


#define SWAP(x, y, t) ((t)=(x), (x)=(y), (y)=(t))

void BubbleSort(int arr[], int count)
{
    int temp = 0;

    for (int n = count - 1; n > 0; n--)
    {
        for (int m = 0; m < n; m++)
        {
            if (arr[m] > arr[m + 1])
                SWAP(arr[m], arr[m + 1], temp);
        }
    }
}

Python 코드


def bubbleSort(alist):
    for passnum in range(len(alist)-1,0,-1):
        for i in range(passnum):
            if alist[i]>alist[i+1]:
                alist[i], alist[i+1] = alist[i+1], alist[i]

alist = [5, 4, 3, 2, 1]
bubbleSort(alist)
print(alist)

파이썬 - range 문법:
range(시작, 끝, 증가값)
range(시작, 끝)
range(끝)

끝은 포함하지 않는다. range(10)은 0부터 9까지 정수이다.

파이썬 - 두변수의 값을 바꾸는 방법:
a, b = b, a
alist[i], alist[i+1] = alist[i+1], alist[i]

파이썬 - 문자열, 리스트(배열) 개수 구하기
len(array)

소스 : BubbleSort.cpp    BubbleSort1.cpp    bubbleSort.py

C 코드 참조)
http://www.algorithmist.com/index.php/Bubble_sort.c
http: //proneer.tistory.com/entry/Sort-버블-정렬Bubble-Sort
Data Structures in C - 생능출판사
열혈강의 자료구조 - 프리

Python 코드 참조)
http://interactivepython.org/courselib/static/pythonds/SortSearch/TheBubbleSort.html