알고리즘 문제 6. 버블정렬

나의 풀이

#include <iostream>

void sortArray(int* arr, int n)
{
	
	//거품정렬 => 생활코딩거기서 풀어봄
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			if (arr[j - 1] > arr[j])
			{
				int temp = arr[j];
				arr[j] = arr[j - 1];
				arr[j - 1] = temp;
			}
		}
	}
}

int main()
{
	int arr[5] = { 5,2,4,1,3 };

	sortArray(arr, 5);

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

	return 0;
}

문제점 : 두개의 숫자를 비교해서 원소를 정렬하므로 사이즈 만큼 반복문을 돌릴 필요 없이 size - 1만큼 반복문을 돌려주면 된다. 또한 각 페이즈 마다 가장 큰 원소가 정렬되므로 페이즈 숫자 만큼 빼서 반복문을 돌려준다.

#include <iostream>

using namespace std;

void Sort(int* arr, int size)
{
	//버블 소트는 여러 페이즈로 이뤄지며,
	//각 페이즈가 끝날시 맨끝 원소부터 정렬된다.

	//0 - 1- 2 -3 -4
	for (int phase = 0; phase < size - 1; phase++)
	{
		//각 페이즈마다 해줘야 하는 일
		// 마지막으로 비교하는 위치 : 3 - 2 - 1 - 0
		//첫 번째 원소부터 비교해 나간다.
		for (int i = 0; i < size - 1 - phase; i++)
		{
			//정렬조건 : 현재 원소가 다음 원소보다 클때 (오름차순)
			if(arr[i] > arr[i + 1])
			{
				//서로 바꾼다.
				std::swap(arr[i], arr[i + 1]);
			}

		}
	}
}

int main() {


	int arr[5] = { 5, 2, 4, 1, 3 };

	Sort(arr, 5);
	// arr : [ 1, 2, 3, 4, 5 ]

	for (int i = 0; i < 5; i++)
	{
		cout << arr[i] << " ";
	}

	return 0;
}