[ 정렬 알고리즘 ] 버블 정렬(Bubble Sort)이란?

안녕하세요, IT디자이너입니다.

 

이번에는 정렬 알고리즘 중 하나인 버블 정렬(Bubble Sort)에 대해서 포스팅하도록 하겠습니다. 

 

 

-정렬의 필요성

정렬(sorting)은 이름, 학번, 키 등 핵심 항목의 대소 관계에 따라 데이터 집합을 일정한 순서로 줄지어 늘어서도록 바꾸는 작업을 말합니다. 

 

이러한 정렬(sorting) 작업은 우리가 무언가를 검색할 때 더욱 쉽게 할 수 있습니다. 만약, 사전에 실린 수십만 개의 단어가 알파벳이나 가나다순으로 정렬되어 있지 않으면 원하는 단어를 찾기가 어려운 것처럼 말이죠!

 

 

 

- 버블 정렬(Bubble sort)이란

버블 정렬은 첫 번째 인덱스부터 이웃한 두 요소의 대소 관계를 비교하여 교환을 반복합니다. 

 

또한 버블 정렬의 첫 번째 패스(Pass)는 배열의 길이에서 -1 만큼의 비교하며, 두 번째 패스부터는 비교하는 횟수를 -1씩 줄입니다.

 

※ 패스란? : 배열의 길이(n) -1 반복은 첫 번째 패스 , (n)-2 반복은 두 번째 패스입니다.

 

즉, 인덱스가 10이고 0~9까지의 수를 오름차순으로 정렬을 원한다면 첫 번째 패스에서 이미 9가 끝으로 잘 정렬이 되었기 때문에 다음 패스(Pass)는 8번만 반복하면 됩니다.

 

 

 

- 버블 정렬(Bubble sort) 구현하기

 

구현하기에 앞서서, 이번에 제가 작성할 소스코드에서는 정렬되는 과정에 콘솔에 출력되도록 구현하였습니다. 

 

간혹 정렬을 구현하다보면, 결과만 보고 만족하실 수도 있습니다. 하지만, 정렬되는 과정에서 불필요한 연산이라던가 잘못된 연산이 있을 수 있습니다. 

 

그렇기 때문에 제가 작성한 소스코드를 보고 당황하지 마시고 정렬되는 과정을 확인해보시길 바랍니다.

 

 

#include <iostream>
#include <conio.h>
#include <Windows.h>
#include <time.h>

#define MAX_ARR 10

int arr[MAX_ARR] = {0,1,2,3,4,5,6,7,8,9};

void bubblePrint(int val1,int val2) { // 정렬하는 인덱스를 [] 로 확인하는 함수입니다.
	
	for (int i = 0; i < MAX_ARR; i++) {
		if (i == val1 || i == val2) 
			printf_s("[%d]", arr[i]);	
		else
		printf_s(" %d ", arr[i]);
	}
	printf_s("\n");
}


void BubbleSort() {
	int change = 0; // 솔팅 체크 변수

	for (int i = 0; i < MAX_ARR - 1; i++) {
		change = 0; // 패스마다 0으로 초기화
		for (int y = 0; y < MAX_ARR - i - 1; y++) {
			if (arr[y] > arr[y + 1]) {
				int temp = arr[y];
				arr[y] = arr[y + 1];
				arr[y + 1] = temp;
				_getch();
				bubblePrint(y, y + 1);
				change++; // 솔팅이 몇번 되었는지 체크
			}
			else {
				_getch();
				bubblePrint(y, y + 1);
			}
		}

		if (change == 0) // 이번 패스에서 한번도 솔팅이 되지 않았으면 
        // 더 이상 정렬할게 없다는 의미이기 대문에 break
			return;

	}
}


int main()
{
	char str;

	for (int i = 0; i < MAX_ARR; i++) {
		printf_s(" %d ", arr[i]);
	}

	printf_s("\n");

	BubbleSort();
	

	for (int i = 0; i < MAX_ARR; i++) {
		printf_s(" %d ", arr[i]);
	}

}

 

버블 정렬은 다른 정렬들의 비해 비효율적이여서 선호되지 않는 정렬 방법입니다. 

 

하지만, 정렬 알고리즘 중 가장 쉬운 알고리즘으로 간단한 규칙만 알게되면 빠르게 구현할 수 있다는 장점이 있습니다.

 

---

IT디자이너였습니다. 감사합니다.!!