1966. 숫자를 정렬하자

1966. 숫자를 정렬하자

문제출처: https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5PrmyKAWEDFAUq&categoryId=AV5PrmyKAWEDFAUq&categoryType=CODE

풀이 방법

버블 소트를 직접 구현하여 풀었다. 하지만 사실 std::sort를 사용하는것이 제일 빠르다 버블소트는 O(n^2)인데 std::sort는 O(nlongn)이다. 하지만 Container를 사용하는 것 보다는 배열이 더 빠른경우가 많다.

<코드>

첫 번째

#include<iostream>
using namespace std;

void Swap(int *left, int *right)			
{
	int temp;
	temp = *right;
	*right = *left;
	*left = temp;
}


void BubbleSort(int *targetArray, int length)					
{
	bool change = false;										
	for (int pass = 0; pass <= length + 1; pass++)				
	{
		for (int i = 0; i < length - pass - 1; i++)				
		{
			if (targetArray[i] > targetArray[i + 1])
			{
				Swap(&targetArray[i], &targetArray[i + 1]);
				change = true;
			}
		}
		if (change == false)
			return;
	}
}
int main(int argc, char** argv)
{
	int test_case;
	int T;
	cin >> T;

	for (test_case = 1; test_case <= T; ++test_case)
	{
		int length;
		std::cin >> length;
		int* dataArray = new int[length] {0, };

		for (int i = 0; i < length; i++) std::cin >> dataArray[i];
		
		BubbleSort(dataArray, length);


		std::cout << "#" << test_case<<" ";
		for (int i = 0; i < length; i++)
			std::cout << dataArray[i] << " ";
		std::cout << "\n";

	}

	return 0;//정상종료시 반드시 0을 리턴해야합니다.
}

두 번째

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int main(int argc, char** argv)
{
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);
	std::cout.tie(nullptr);

	int test_case;
	int T;
	cin >> T;

	for (test_case = 1; test_case <= T; ++test_case)
	{
		int n;
		std::cin >> n;
		std::vector<int> vec(n);

		for (int i = 0; i < n; i++)
			std::cin >> vec[i];

		std::sort(vec.begin(), vec.end());
		
		std::cout << "#" << test_case << " ";
		for (int i = 0; i < n; i++)
			std::cout << vec[i] << " ";
		std::cout << "\n";

	}

	return 0;//정상종료시 반드시 0을 리턴해야합니다.
}