버블 정렬 구현 및 테스트

  버블 정렬 

선택 정렬과 비슷하게 가장 큰 원소를 가장 끝의 자리로 옮기는 정렬이다. 다만, 이동시키는 방식이 바로 오른쪽 값과 비교하여 교체해주는 것으로 선택 정렬과 차이를 갖는다.

 

버블 정렬 알고리즘

배열 A[1...n]에 대해 A[1] > A[2] 인 경우 A[1]과 A[2]의 자리를 바꾼다. 이 과정을 [1...n]에 대하여 반복한다.

이를 수도 코드로 나타내면 다음과 같다.

 

버블 정렬 알고리즘

BubbleSort(A[], n)
{
	for last ← n downto 2
	{
		for i ← 1 to last - 1
		{
			if (A[i] > A[i+1]) then
			{
				A[i] ↔ A[i+1]
			}
		}
	}
}

 

※ 버블 정렬 알고리즘의 비교 회수는 n(n-1)/2 이며 시간 복잡도는 Ο(n²)이다.

 

버블 정렬 구현

배열 arr과 배열의 길이 n을 입력으로 받는 함수를 구현한다.

 

BubbleSort.hpp

#pragma once
#include "../Common.h"

/// <summary>
/// 주어진 배열을 정렬한다.
/// </summary>
/// <param name="arr">정렬을 진행할 배열</param>
/// <param name="n">배열의 길이</param>
/// <param name="printData">중간 결과 출력 여부</param>
void BubbleSort(int arr[], int n, bool printData = false)
{
	if (printData)
	{
		Common::PrintArray(arr, n);
	}

	for (int i = 1; i < n; i++)
	{
		for (int j = 0; j < n - i; j++)
		{
			if (arr[j] > arr[j + 1])
			{
				Common::Swap(arr, j, j + 1);
			}
		}

		if (printData)
		{
			Common::PrintArray(arr, n);
		}
	}
}

 

arr = [ 2, 4, 6, 8, 10, 9, 7, 5, 3, 1 ], n = 10 을 입력하여 실행한 과정은 다음과 같다.

2 4 6 8 10 9 7 5 3 1
2 4 6 8 9 7 5 3 1 10
2 4 6 8 7 5 3 1 9 10
2 4 6 7 5 3 1 8 9 10
2 4 6 5 3 1 7 8 9 10
2 4 5 3 1 6 7 8 9 10
2 4 3 1 5 6 7 8 9 10
2 3 1 4 5 6 7 8 9 10
2 1 3 4 5 6 7 8 9 10
1 2 3 4 5 6 7 8 9 10

 

난수 1,000,000개에 대한 수행 시간은 다음과 같다.

total time is 471s ( 471389ms )

 

NadanKim/Algorithm: 알고리즘 학습 및 예제 코드 작성을 위한 저장소 (github.com)

NadanKim/Algorithm

 

참고문헌

한빛아카데미.문병로.(2016.07.24).쉽게 배우는 알고리즘