버블 정렬(Bubble Sort)

 버블 정렬은 리스트를 반복적으로 순회하며 인접한 두 요소를 비교하고, 잘못된 순서라면 교환합니다. 모든 요소를 여러 번 비교해야 하기 때문에 일반적으론 비효율적입니다. 여기서 두 요소를 비교, 교환은 앞써 쓴 글인 삽입 정렬 (Insertion Sort)과 비슷하지만 비교 방식과 에서 다른 형태를 가지고 있습니다. 그림으로 설명하겠습니다.

버블 정렬 구조 예시

• 삽입 정렬: 순차적으로 리스트를 확인하며 두 요소를 비교, 정렬하는 방식
• 버블 정렬: 리스트를 반복 순회하며 두 요소를 비교, 정렬하는 방식

즉, 버블 정렬은 리스트를 계속 순회하기 때문에 삽입 정렬보다 비효율적인 정렬 방식입니다.

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define MAX_LEN 10

// Init: Initialization
void InitRandomNumber(int* const _pArr, int _len);	//랜덤 값 설정 함수
void Swap(int* const _pLhs, int* const _pRhs);	//좌 우 값 교환 함수
void BubbleSort(int* const _pArr, int _len);	//버블 정렬 함수
void PrintAll(const int* const _pArr, int _len);	//출력 함수

void main()
{
	// 거품정렬(Bubble Sort)
	srand(time(NULL));		//srand: 랜덤한 값 선정 time(NULL): 현재 시간

	int arr[MAX_LEN] = { 0 };	//arr[10] = 0으로 모두 초기화
	InitRandomNumber(arr, MAX_LEN);	//InitRandomNumber함수 호출
	PrintAll(arr, MAX_LEN);		//출력

	printf("\n");			
	BubbleSort(arr, MAX_LEN);	//버블 정렬 함수 호출
	printf("\n");

	PrintAll(arr, MAX_LEN);		//출력 함수 호출
}


void InitRandomNumber(int* const _pArr, int _len)
{
	if (_pArr == NULL || _len < 1) return;	//예외 처리

	for (int i = 0; i < _len; ++i) 
    {
		*(_pArr + i) = rand() % 100;	// 0 ~ 100 랜덤값 선정 
	}
}

void Swap(int* const _pLhs, int* const _pRhs)	
{
	if (_pLhs == NULL || _pRhs == NULL) return;	//NULL 예외처리

	int tmp = (*_pLhs);	//tmp 임시 변수에 *_pLhs가 가진 주소값 대입
	*_pLhs = *_pRhs;	//*_pLhs = *_pRhs 로 같게 설정
	*_pRhs = tmp;		//*_pRhs에 *_pLhs의 주소값을 가진 tmp 대입
}

void BubbleSort(int* const _pArr, int _len)
{
	if (_pArr == NULL || _len < 1) return;	//예외처리

	for (int k = 0; k < _len - 1; ++k)
	{
		for (int i = 0; i < _len - 1 - k; ++i) 
        {
			if (*(_pArr + i) > *(_pArr + i + 1)) 
            {
				Swap(_pArr + i, _pArr + i + 1);

				//for (int j = 0; j < _len; ++j) 
                //{
				//	if (j == i || j == i + 1)
				//		printf("[%d] - ", *(_pArr + j));
				//	else
				//		printf(" %d  - ", *(_pArr + j));
				//}
				//printf("(%d)\n", _len);
			}
		}

		PrintAll(_pArr, _len);
	}
}

void PrintAll(const int* const _pArr, int _len)
{
	if (_pArr == NULL || _len < 1) return;	//예외처리

	for (int i = 0; i < _len; ++i) 
    {
		printf("[%d] - ", *(_pArr + i));
	}
	printf("(%d)\n", _len);
}

<출력값>

[95] - [99] - [53] - [14] - [77] - [94] - [36] - [15] - [82] - [1] - (10)

InitRandomNumber(arr, MAX_LEN);
PrintAll(arr, MAX_LEN);
[95] - [53] - [14] - [77] - [94] - [36] - [15] - [82] - [1] - [99] - (10)
[53] - [14] - [77] - [94] - [36] - [15] - [82] - [1] - [95] - [99] - (10)
[14] - [53] - [77] - [36] - [15] - [82] - [1] - [94] - [95] - [99] - (10)
[14] - [53] - [36] - [15] - [77] - [1] - [82] - [94] - [95] - [99] - (10)
[14] - [36] - [15] - [53] - [1] - [77] - [82] - [94] - [95] - [99] - (10)
[14] - [15] - [36] - [1] - [53] - [77] - [82] - [94] - [95] - [99] - (10)
[14] - [15] - [1] - [36] - [53] - [77] - [82] - [94] - [95] - [99] - (10)
[14] - [1] - [15] - [36] - [53] - [77] - [82] - [94] - [95] - [99] - (10)
[1] - [14] - [15] - [36] - [53] - [77] - [82] - [94] - [95] - [99] - (10)

BubbleSort(arr, MAX_LEN);
printf("\n");
[1] - [14] - [15] - [36] - [53] - [77] - [82] - [94] - [95] - [99] - (10)

PrintAll(arr, MAX_LEN);

각 출력값에 영향을 준 출력문들을 밑에 배치했습니다.

 

끝