1. Sort - Bubble Sort : 버블 정렬

// Bubble Sort
// O(n^2)
#include <iostream>
#include <vector>

//9 3 5 7 1
//3 9 5 7 1
//3 5 9 7 1
//3 5 7 9 1
//3 5 7 1 9

//3 5 7 1 9
 
//3 5 7 1 9

//3 5 1 7 9

//3 1 5 7 9

//1 3 5 7 9

int main() {
	std::vector<int> v{ 9,3,5,7,1 };
	for (int i = 0; i < v.size() - 1; i++)
	{
		for (int j = 0; j < v.size() - 1 - i; j++)
		{
			if (v[j] > v[j + 1])
			{
				int temp = v[j];
				v[j] = v[j + 1];
				v[j + 1] = temp;
			}

		}
	}
	for (const int& iter : v)
	{
		std::cout << iter << " ";
	}
	std::cout << std::endl;
	return 0;
}

BubbleSort는 양옆의 두 자리를 비교해서 한쪽이 더 크거나 작으면 (오름차순, 내림차순) 서로 swap하는 형태의 알고리즘이다.

 

뒷자리부터 확정을 내는 것이 특징이며 비효율적인 정렬 알고리즘이다 O(n^2)