2강 - 버블 정렬 (Bubble Sort)

1. 버블 정렬

(오름차순을 기준)

1) 정의

앞에서부터 서로 인접한 두 원소를 검사하여 정렬(바로 그 뒤로 보낸다.) 

2) 특징

1> 방향

- 선택 정렬: (0~N-1) -> (1~N-1) -> (2~N-1) -> ... -> (N-1)

- 버블 정렬: (0~N-1) -> (0~N-2) -> (0~N-3) -> ... -> (0~1)

(둘 다 정렬에서 제외되는 data가 하나씩 늘어간다.)

 

2. 구체적인 과정

(오름차순 기준)

1> 0번째 index부터 바로 1번째 index(오른쪽)와 비교해서 교체한다.  (큰 data를 뒤로 보낸다.)

2> 1번째 index도 바로 옆이랑 위의 과정을 진행한다. ... N-2번째까지 진행한다.

3> 1> ~ 2> 를 (0~N-1) -> (0~N-2) -> (0~N-3) -> ... -> (0~1)순서로 진행한다.

 

3. 구현

#include <iostream>
using namespace std;
const int MAX = 1000;

void swap(int &a, int &b)
{
	int temp = a;
	a = b;
	b = temp;
}

int main()
{
	int N;
	cin >> N;
	int arr[MAX];
	for (int i = 0; i < N; i++)
	{
		cin >> arr[i];
	}
    
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N-i; j++)
		{
			if (arr[j] > arr[j+1])
			{
				swap(arr[j], arr[j + 1]);
			}
		}
	}
	for (int i = 0; i < N; i++)
	{
		cout << arr[i] << '\n';
	}
}