버블 정렬 (Bubble Sort)

안녕하세요 연두아빠에요.

어린이날이라 가족과 함께 하다 보니 며칠 포스팅을 쉬게 되었네요.

오늘부터 다시 열심히 달려야겠네요.

두번째 기초 정렬 알고리즘은 버블 소트, 거품 정렬 등으로 불리우는 버블 정렬입니다.

버블 정렬은 서로 인접한 두개의 데이터를 비교해 큰 데이터를 뒤로 보내며 정렬하는 방식입니다.

거품이 뽀글 뽀글 올라가듯이 데이터가 계속해서 뒤로 밀려나는 형태를 띄고 있어 버블 정렬이라는데...

뭐 그런가 봅니다... 왜 그런 명칭이 붙었는 가도 중요하니 알고는 있는게 좋겠네요.

역시나 그림을 보며 따라가다보면 쉽게 이해가 되실 것 같아요.

위와 같이 정렬이 되어 있지 않은 다섯 개의 숫자가 있습니다.

버블 소트는 단순히 맨 앞에서부터 두개씩 계속해서 비교를 하며 큰 수를 뒤로 보내면 됩니다.

첫번째 숫자인 5와 두번째 숫자인 3을 비교합니다.

5가 당연히 크니 5와 3의 위치를 서로 교환하여 줍니다.

다음은 5와 1을 비교합니다.

역시 5가 더 크니 둘의 위치를 서로 교환하여 줍니다.

다시 한칸 옆으로 이동해서 5와 2를 비교합니다.

이번에도 5가 크니 5와 2의 위치를 서로 교환하여 줍니다.

다음은 5와 4를 비교해야 합니다.

역시나 5가 더 크니 한번 더 둘의 위치를 서로 교환하여 줍니다.

어떤 식인지 이제 확실히 이해가 되셨죠?

이제 3과 1부터 다시 처음부터 올라가며 큰 수를 뒤로 보내주면 끝입니다.

단, 이때 맨 뒤의 5는 가장 큰 수가 확실하니 제외해도 되겠죠?

따라서 (전체 데이터 개수 - 루프 된 횟수) 만큼의 데이터만 비교하면 됩니다.

한바퀴만 더 돌면 위와 같은 정렬된 결과를 얻을 수 있겠네요. 쉽죠?

지난 번 공부했던 선택정렬과 같이 정렬 알고리즘이 쉽고 단순하면 대부분 비효율적입니다.

배열이 어떻게 되어있던지간에 전체 비교를 진행하게 되므로 시간복잡도는 O(n2)가 됩니다.

빅오 표기법(Big-O Notation)이 기억나지 않으시는 분은 아래 링크로 이동하셔서 복습해 보세요.

    Big O 표기법 (Big O Notation), 시간 복잡도 표기법 (Time Complexity Notation)

버블 정렬을 C# 코드로 구현해보면 다음과 같습니다.

선택 정렬 알고리즘을 C# 코드로 구현을 해보면 다음과 같습니다.

void BubbleSort (List<int> data)

{

    for ( int loopCount = 0; loopCount < data.Count - 1; ++loopCount )

    {

        for ( int i = 1; i < data.Count - loopCount; ++i )

        {

            if (data[i - 1] > data[i])

            {

                data.Swap(i - 1, i);

            }

        }

    }

}

역시나 이중 for 문을 사용하기 때문에 시간복잡도가 O(n2)가 되는 것이죠.

그 외에 더 알고 싶은 점이나 의문이 생기는 부분들 댓글로 남겨드리면 최대한 도움을 드려볼께요.

공감(♥) 및 댓글은 글쓴이에게 커다란 힘이 됩니다.

길지 않은 이 글을 쓰는데 나름 몇 시간이 걸렸어요^^;

저에게 1초만 시간을 내주셔서 공감 버튼 꾸욱 눌러주세요^^

제 블로그를 방문해 주신 모든 분들 사랑합니다^^

이상입니다. 감사합니다!