[알고리즘] 버블 정렬 (C++)

 

 

버블 정렬

 

크기가 n인 배열(arr)이 있다고 가정했을때,

(arr[0] 와 arr[1]), (arr[1] 와 arr[2]), (arr[2] 와 arr[3]) ..... (arr[n-1] 와 arr[n]) 을 비교해서 정렬하는 방식이다

 

• 시간복잡도는 O(n∧2)
• 구현은 단순하지만 교환작업의 비효율성으로 거의 사용하지 않는다

 

 

 

 

#include<iostream>
using namespace std;


void BubbleSort(int arr[], int length)
{
	int temp;
	
	
	for (int i = 0; i < length; i++)
	{
		for (int j = 0; j < length - 1 - i; j++)
		{
			if(arr[j] > arr[j+1])
			{
				//자리 교체
				temp = arr[j];
				arr[j] = arr[j + 1];
				arr[j + 1] = temp;
			}
		}
	}

}

int main()
{
	int list[8] = { 5,3,1,6,7,2,8,4 };
	int length = sizeof(list) / sizeof(int);	//배열 크기 구하기

	BubbleSort(list, length);

	//출력
	for (int i = 0; i < sizeof(list) / sizeof(int); i++)
	{
		cout << list[i] << " ";
	}

	return 0;

}

 

정렬 후