알고리즘 버블정렬(Bubble sort) 그림으로 쉽게 이해하기

알고리즘 버블정렬(Bubble sort) 그림으로 쉽게 이해하기

 

안녕하세요.

 

로스윗의 코딩캠프입니다.

오늘 포스팅에서는 버블소트(Bubble Sort)에 대해서 자세히 알려드리겠습니다.

버블소트(Bubble Sort)에 대해서 알아보기 전에 먼저 정렬의 특징에 대해서 알아봐야합니다.

 

 

- 정렬의 특징

우선 정렬은 안정 정렬과 불안정 정렬로 구분할 수 있습니다.

그림처럼 정렬되어 있지 않은 리스트에 중복된 값 1이 2개가 들어있다고 가정을 해볼게요.

 

 

정렬되지 않은 리스트

실제로는 동일한 1이지만 이 둘을 구분하기 위해서 스몰a와 스몰b를 붙여서 나타냈습니다.

이 리스트를 정렬 했을 때는 아래의 그림처럼 두가지 경우가 가능합니다.

 

 

안정 정렬과 불안정 정렬

 

- 안정 정렬 vs 불안정 정렬

위의 경우는 동일한 1에 대해서 처음 그대로 a,b 순서대로 정렬이 되었고

아래의 경우는 정렬은 되었지만 숫자 1의 a,b 순서는 바뀌었습니다.

이렇게 중복된 값의 순서 보장 여부에 따라서

순서가 보장이 되는 경우는 안정 정렬, 순서가 보장이 되지 않는 경우는 불안정 정렬이라고 부릅니다.

이런 안정(stable)여부는 정렬에 있어서 굉장히 중요한 특징 중에 하나입니다.

물론 중복된 숫자 자체에 a,b 라벨이 붙어 있는것이 아니기 때문에

단순 숫자의 경우에 stable이랑 unstable의 차이가 그렇게 유의미한가? 싶을 수도 있습니다.

그래서 숫자 대신에 다른 예시로 설명을 한 번 해볼게요.

 

 

이름 순 정렬 예시

이렇게 이름 순으로 정렬된 파일이 있다고 할 때

이 파일들을 날짜순으로 재정렬을 한다고 가정을 해봅시다.

안정 정렬인 경우에는 날짜순으로 정렬되면서 동시에 이름순으로 정렬이 되는 것을 볼 수 있고,

불안정정렬을 실시할 경우에는 마찬가지로 날짜순으로 정렬을 할 수는 있지만 

 

파일의 이름이 정렬되어 있는 것은 보장을 할 수가 없게 되는것입니다.

 

 

안정 정렬과 불안정 정렬

 

- In-place vs Out-of-place

두번째는 구현 방식에 따라서 In-place와 Out-of-place로 구분할 수 있습니다

in-place정렬은 원본 데이터 내에서 정렬이 이루어지는 경우를 말하고

out-of-place는 원본 데이터가 아닌 새로운 배열로 정렬된 output결과를 만드는 경우를 말합니다.

그래서 정렬을 볼때에는 정렬의 시간 복잡도와 안정 정렬 여부,

 

그리고 구현 방식 이렇게 3가지 관점에서 차이를 비교해볼 수 있습니다.

먼저 첫번째 정렬 방법인 Bubble sort에 대해서 먼저 알아보겠습니다.

 

 

- 버블정렬(Bubble Sort) 동작 원리

버블 정렬(Bubble sort)은 어떤 방식으로 정렬이 이루어질까요?

그림처럼 정렬되어 있지 않은 리스트를 버블 정렬(Bubble sort)로 오름차순 정렬을 한 번 해보도록 하겠습니다.

 

 

버블정렬 그림 예시

우선 가장 앞에 위치한 2개의 값을 비교를 하게 됩니다. 

 

5와 4이겠지요.

 

버블정렬 그림 예시

그래서 이 두 값이 정렬되어 있지 않다면, 

 

다시 말해서 왼쪽의 값이 오른쪽의 값보다 크다면 두 값의 위치를 바꿔줍니다.

 

 

버블정렬 그림 예시

그리고 한 칸 이동해서 동일한 연산을 수행합니다.

5와 1의 값을 비교합니다.

 

 

버블정렬 그림 예시

 

 

5와 1의 값을 비교하는, 순서가 정렬이 되어 있지 않죠. 

 

그래서 5와 1의 위치를 바꿔줍니다.

 

 

버블정렬 그림 예시

그리고 또 한칸 이동해서 비교 연산을 하는데 

 

이번에는 5와 9의 값이 이미 정렬되어 있는 상태이기 때문에 값을 바꾸지 않고 또 한칸 이동합니다.

버블정렬 그림 예시

이런식으로 리스트의 처음부터 끝까지 비교 연산 사이클을 한번 반복하게 되면 

 

이 리스트의 가장 끝에는 리스트 안에 존재하는 가장 큰 값이 위치하게 됩니다.

 

 

버블정렬 그림 예시

하지만 이 값을 제외한 앞의 값들은 여전히 정렬되지 않은 상태입니다.

그러면은 다시 처음부터 비교하고 다시 위치를 바꿔주는 연산을 실시합니다.

그러면 맨 앞에 있는 4와 1을 비교하게 되겠지요.

 

버블정렬 그림 예시

 

 

정렬이 되어 있지 않으니 역시 순서를 바꿔주게 됩니다.

 

 

버블정렬 그림 예시

이것을 또 리스트의 끝까지 반복하게 되면 

 

마찬가지로 마지막 인덱스의 바로 앞에는 이번 수행에서 가장 큰 값이었던 7이 위치하게 됩니다.

 

 

버블정렬 그림 예시

그러면은 정렬된 뒤의 두 칸을 제외하고 다시 처음부터 비교와 위치를 바꿔주는 스왑연산을 수행하게 됩니다.

그렇게 해서 한 사이클을 수행할 때마다 현재의 리스트에 위치한 가장 큰 값이 뒤에 하나씩 하나씩 쌓이게 될거에요.

그래서 마지막으로 정렬해야 할 데이터의 크기가 하나가 된다면 

 

배열 내의 모든 데이터가 정렬된 상태가 될 것입니다.

 

- 정리 및 요약

다시 정리를 해보자면, 

 

버블 정렬(Bubble sort)은 인접한 두 element의 값을 비교하고

 

두 값이 정렬되어 있지 않다면 위치를 교환하는 매커니즘입니다.

이렇게 해서 리스트의 처음부터 끝까지 이 동작을 반복을 하게 되면은 

 

가장 끝에는 정렬이 완료된 element가 남게 되겠죠.

그래서 이렇게 정렬이 완료된 element를 제외하고 위의 과정을 반복하게 됩니다.

이때 비교횟수는 데이터의 크기가 2개면 1번 비교가 이뤄지겠고, 

 

데이터가 3개면 두 번의 비교가 이뤄지겠죠.

그래서 데이터가 n개 일때는 n-1번의 비교를 제일 처음 비교 연산에서 하게 됩니다.

그 이후에는 이미 정렬된 하나의 데이터를 제와한 n-2번의 비교 연산이 발생할거구요

그 다음에는 정렬된 데이터가 하나 더 늘었으니까 n-3번의 비교 연산을 할 겁니다.

그리고 이 값이 1이 될때까지 비교를 하면서 위치를 스왑을 하겠죠.

이거를 식으로 정리하면 n(n-1)/2 이 도출이 됩니다. 

 

이때 상수항은 무시해서 n제곱이라는 값이 남게 되겠죠.

마찬가지로 교환횟수도  n(n-1)/2이 될 것입니다.

그래서 버블정렬(Bubble sort)의 시간 복잡도는 O(N제곱)으로 표현이 됩니다.

이 버블 정렬(Bubble sort)는 알고리즘이 굉장히 직관적이고 단순해서 이해하기 쉽지만

 

느리기 때문에 실제로 사용하기에는 어렵다는 단점이 있습니다.

그리고 이때 정렬되는 모양이 마치 거품이 있는 것 같다고 해서 Bubble sort라는 이름이 붙었습니다.

 

오늘 포스팅은 여기까지 입니다.

 

로스윗의 코딩캠프는 미래의 개발자 여러분을 응원합니다.

 

모두 화이팅!!

 

알고리즘 - 버블정렬(Bubble sort)이란? (ft. 그림으로 쉽게 설명)

자료구조 - 버블정렬(Bubble sort)이란? (ft. 그림으로 쉽게 설명)

 

자료구조 - 해시(Hash)란? (ft. 가장 쉬운 비유 설명)

자료구조 해시(Hash)란? (ft. 가장 쉬운 비유 설명)