[알고리즘/C++]버블정렬Bubble Sort

---

버블정렬(Bubble Sort)

서로 이웃한 두 원소를 비교하여 큰 값을 비교하여 조건에 맞지 않는다면 자리를 교환하는 정렬이다.

---

#동작 방식

버블 정렬은 반복적으로 배열을 탐색하면서 이웃한 요소를 비교하여 서로 교환한다. 탐색 과정에서 현재 요소가 다음 요소보다 크다면, 두 요소의 위치를 교환다. 이러한 교환 과정을 반복하여 배열의 가장 큰 요소가 맨 뒤로 이동하게 됩니다. 이 과정을 배열의 크기만큼 반복하면 전체 배열이 정렬된다.

 

#코드

코드로 구현하면 이렇다.

void bubbleSort(const int size, int arr[])
{
	for (int i = 0; i < size; i++) //(1) 배열에서 제외할 원소의 갯수
	{
		for (int j = 1; j < 8 - i; j++) //(2) 마지막에서 i만큼 원소를 제외하고 1부터 계산(현재 원소는 j, 이전 원소는 j-1)
		{
			if (arr[j - 1] > arr[j]) //(3) 이전 원소가 지금 현재 가르키는 원소보다 크면 서로 바꾼다.
			{
				swap(arr[j], arr[j - 1]);
			}
		}
	}
}

 

1. 처음 (1)에서 i는 배열에서 제외할 원소의 갯수를 나타낸다.
2. 그다음 (2)에서 i만큼 배열에서 제외하고 1부터 계산한다. 
   • 1부터 하는 이유는 j는 현재 원소를 가르키고 j - 1이 이전 원소를 가르키기 때문이다.
3. (3)에서는 이전 원소(arr[j - 1])이 현재원소(arr[j])보다 크면 서로 교환한다.

 

전체코드

#include <iostream>
using namespace std;

void bubbleSort(const int size, int arr[]); // 버블정렬
void printArr(const int size, const int arr[]); //배열 원소들을 출력
void swap(int& arr1, int& arr2); // 배열 원소를 서로 바꾸어 준다.

int main()
{
	const int size = 8; //배열 크기
	int arr[size]{1, 4, 2, 5, 3, 8, 6, 7}; // 배열
	bubbleSort(size ,arr); // 버블정렬
	printArr(size, arr);   // 출력
}

void bubbleSort(const int size, int arr[])
{
	for (int i = 0; i < size; i++) // 배열에서 제외할 원소의 갯수
	{
		for (int j = 1; j < 8 - i; j++) // 마지막에서 i만큼 원소를 제외하고 1부터 계산(현재 원소는 j, 이전 원소는 j-1)
		{
			if (arr[j - 1] > arr[j]) // 이전 원소가 지금 현재 가르키는 원소보다 크면 서로 바꾼다.
			{
				swap(arr[j], arr[j - 1]);
			}
		}
	}
}

void printArr(const int size, const int arr[]) 
{
	for (int i = 0; i < 8; i++)
		cout << arr[i] << endl;
}

void swap(int& arr1, int& arr2) 
{
	int temp = arr1;
	arr1 = arr2;
	arr2 = temp;
}

 

1부터 8까지 순서대로 출력되게 된다.

---

 

#장점

---

• 구현이 간단하고 이해하기 쉽다.
• 제자리 정렬을 하여서 메모리 부분에서 좋다.

#단점

---

• 시간 복잡도가 O(n^2)으로 비효율적이다.
• 배열의 크기가 클 경우 성능이 저하될 수 있다.

#마무리

---

버블 정렬은 간단하면서도 기초적인 정렬 알고리즘이다. 작은 규모의 배열에 적합하며, 이미 거의 정렬된 배열에 대해서는 성능이 좋을 수 있다. 그러나 배열의 크기가 클 경우에는 다른 정렬 알고리즘을 고려하는 것이 좋다. 버블 정렬은 정렬 알고리즘에 대한 이해를 시작하는 데 도움이 되는 좋은 출발점이다. 다른 정렬 알고리즘을 탐구하며 알고리즘의 장단점을 이해하고 적절한 상황에서 사용하는 것이 중요하다.