[Algorithm] 35. Special Sort(구글 인터뷰)

인트로

정렬을 알고리즘을 적용하는 문제이다.

 

어떤 정렬을 사용할진 문제를 읽어보고 고민하길 바란다. 

 

Special Sort(구글 인터뷰)

문제

N개의 정수가 입력되면 당신은 입력된 값을 정렬해야 한다.
음의 정수는 앞쪽에 양의 정수는 뒤쪽에 있어야 한다. 또한 양의 정수와 음의 정수의 순서에는 변함이 없어야 한다.

※ 입력 설명
첫 번째 줄에 정수 N(5<=N<=100)이 주어지고, 그다음 줄부터 음수를 포함한 정수가 주어진다.
숫자 0은 입력되지 않는다.

※ 출력 설명
정렬된 결과를 출력한다.

입력

8
1 2 3 -3 -2 5 6 -6

출력

-3 -2 -6 1 2 3 5 6

코드 설명

문제의 조건을 살펴보면 다음과 같다.

 

1) 음의 정수는 앞쪽에 양의 정수는 뒤쪽에 있어야 한다.

▶음의 정수를 앞쪽으로 밀어 넣으면 양의 정수는 자연스럽게 뒤쪽으로 배치된다.

 

2) 양의 정수와 음의 정수의 순서에는 변함이 없어야 한다.

▶두 값의 대소를 비교하고 자리를 교체하는 문제는 아니란 것을 알 수 있다.

 

따라서,

▶음수와 양수의 배치는 유지한 채 음수를 한 칸 한 칸  앞으로 밀어 넣어는 작업에 유리한 버블 정렬을 사용했다.

[Algorithm] 버블 정렬(Bubble Sort) 코드와 시간 복잡도

[Algorithm] 버블 정렬(Bubble Sort) 코드와 시간 복잡도

#include <iostream>
#include <vector>

using namespace std;

int main()
{
	int n;

	cin >> n;

	vector<int> v(n);

	for (int i = 0; i < n; i++) 
		cin >> v[i];

	/*Bubble Sort Begin*/
	for (int i = 0; i < n - 1; i++)
	{
		for (int j = 0; j < n -i - 1; j++)
		{
			if (v[j] > 0 && v[j+1] < 0)
			{
				int temp = v[j];
				v[j] = v[j + 1];
				v[j + 1] = temp;
			}
		}
	}
	/*Bubble Sort End*/

	for (int i = 0; i < n; i++)
		cout << v[i] << " ";
}