(C/C++) 정렬 - 버블 정렬(Bubble Sort) - 안정성 O, O(N²)

 

안녕하세요

오늘은 버블 정렬입니다!

 

1. 버블 정렬(Bubble Sort)이란?

인접 요소와 값을 비교 하여 교환해 나가는 방식입니다.

하나하나 비교를 하면서 한바퀴의 루프가 돌았을때는 가장 큰 값이 가장 뒤로 가는 모습을 볼 수 있습니다.

그리고 루프를 돌면서 조금씩 조금씩 정렬이 되기 때문에 모든 루프를 돌지 않아도 정렬이 되어있는 경우도 있습니다.

 

2. 버블 정렬의 특징

성능이 좋지 않은 정렬 알고리즘

안정성 O

O(N²) 의 시간 복잡도

역순의 경우 가장 느리다.

정렬, 난수, 역순 모두 골고루 느린 정렬이라 잘 사용하지 않는다.

 

정렬 안정성 과 알고리즘 시간 복잡도 빅오(Big - Oh)

 

3. 버블 정렬의 구현

 

#include <iostream>
#include <stdio.h>

void BubbleSort_1(int _arrays[], int _arraysLength)
{
	for (int i = 0; i < _arraysLength; i++)
	{
		for (int j = 1; j < _arraysLength - i; j++)
		{
			if (_arrays[j - 1] > _arrays[j])
			{
				int temp = _arrays[j - 1];
				_arrays[j - 1] = _arrays[j];
				_arrays[j] = temp;
			}
		}
	}
}

void BubbleSort_2(int _arrays[], int _arraysLength)
{
	for (int i = 0; i < _arraysLength; i++)
	{
		bool isSorted = true;
		for (int j = 1; j < _arraysLength - i; j++)
		{
			if (_arrays[j - 1] > _arrays[j])
			{
				int temp = _arrays[j - 1];
				_arrays[j - 1] = _arrays[j];
				_arrays[j] = temp;
				isSorted = false;
			}
		}

		if (isSorted)
			return;
	}
}

 

위에 있는 버블정렬과 아래 있는 버블 정렬의 차이점이 보이시나요?

isSorted 라는 bool 값이 추가된건데요.

버블 정렬 특성상 순환하면서 자리를 찾아가기 때문에 중간에 정렬이 되는 경우도 있다고 말씀드렸습니다.

그럴때 bool 값으로 체크를 하면 불필요하게 for 문을 돌지 않아도 됩니다

다만 이 경우는 중간에 정렬이 되는 경우에만 그렇고

bool 값을 대입하고 if 문을 체크하기 때문에 정렬된 경우 이외에는 늘어난다고 볼 수 있습니다.

감사합니다.

 

다른 정렬

버블 정렬(Bubble Sort) - 안정성 O, O(N²)

선택 정렬(Select Sort) - 안정성 X, O(N²)

삽입 정렬(Insert Sort) - 안정성 O, O(N²)

쉘 정렬(Shell Sort) - 안정성 X, O(n^1.5)

병합 정렬(Merge Sort) - 안정성 O, O(N log N)

퀵 정렬(Quick Sort) - 안정성 X, O(N log N)