Bubble Sort 작동방식 (간단)

_Bubble Sort

거품 정렬 또는 버블 정렬은 두 인접한 원소를 검사하여 정렬하는 방법이다.

시간 복잡도가 O(n^{2})로 상당히 느리지만, 코드가 단순하기 때문에 자주 사용된다. 

원소의 이동이 거품이 수면으로 올라오는 듯한 모습을 보이기 때문에 지어진 이름이다

 

버블 솔트는 말 그대로 버블이라는 원 하나를 만들어 두개의 원소를 조사하여

더 작은 값을 큰 값이랑 스위치해 왼쪽으로 가게 만들어준다.

Bubble Sort는 stable하다

 

 

 (@@색은 버블이라 생각하면된다)

 

[9, 3, 5, 7, 1] 

[9, 3, 5, 7, 1] --> [3, 9, 5, 7, 1]

[3, 9, 5, 7, 1] --> [3, 5, 9, 7, 1]

[3, 5, 9, 7, 1] --> [3, 5, 7, 9, 1]

[3, 5, 7, 9, 1] --> [3, 5, 7, 1,9 ]

[3, 5, 7,1, 9] --> [3, 5, 1, 7, 9]

... ... .. .. .. .

결과 [1, 3, 5 ,7, 9]

위 같은 방식으로 솔팅된다 2개를 버블해서 그 두 수를 sort하는 것이다.

Time_Complexity

 Avg(평균)  = o(n^2)

Worst(최악) = o(n^2)

Best(최고) = 0(n^2)

 

버블 정렬(bubble sort) 알고리즘의 특징

장점 :
구현이 매우 간단하다.
단점 :
순서에 맞지 않은 요소를 인접한 요소와 교환한다.
하나의 요소가 가장 왼쪽에서 가장 오른쪽으로 이동하기 위해서는 배열에서 모든 다른 요소들과 교환되어야 한다.
특히 특정 요소가 최종 정렬 위치에 이미 있는 경우라도 교환되는 일이 일어난다.
일반적으로 자료의 교환 작업(SWAP)이 자료의 이동 작업(MOVE)보다 더 복잡하기 때문에 버블 정렬은 단순성에도 불구하고 거의 쓰이지 않는다.

void bubbleSort(int arr[], int n)
{
    int i, j;
    for (i = 0; i < n - 1; i++)
  
        // Last i elements are already 
        // in place
        for (j = 0; j < n - i - 1; j++)
            if (arr[j] > arr[j + 1])
                swap(arr[j], arr[j + 1]);
}

 

 

운영중인 카톡방입니다.

https://open.kakao.com/o/gsMhUFie

C/C++/C# 언리얼/유니티 /질문