[백준 2750] 수 정렬하기

https://www.acmicpc.net/problem/2750

2750번: 수 정렬하기

요구사항

1. 오름 차순으로 정렬

 

풀이

1. 퀵 정렬 구현

1.1 피벗을 정한다

1.2 i, j, pivot 정의

1.3 i는 피벗보다 큰게 나올때 까지 증가

1.4 j는 피벗보다 작은게 나올대 까지 감소

 

i, j가 교차 하였으면 pivot, j 스왑

아니면 i, j 스왑

 

위 과정을 i <=j 교차 될때 까지

 

이 후 재귀 함수로 풀이

#include <iostream>

using namespace std;

int n;
void swap(int& a, int& b)
{
	int temp;
	temp = a;
	a = b;
	b = temp;
}
int map[10001];
void Quick_sort(int l, int r, int arr[])
{
	if (l >= r)
		return;

	int pivot = l;
	int i = l + 1;
	int j = r;
	while (i<=j)
	{
		while (i <= r && arr[pivot] >= arr[i]){
			i++;
		}
		while (j > l && arr[pivot] <= arr[j])		{
			j--;
		}

		if (i > j)
		{
			swap(arr[j], arr[pivot]);
		}
		else {
			swap(arr[i], arr[j]);
		}
	}
	Quick_sort(l, j - 1, arr);
	Quick_sort(j+1,r, arr);
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		cin >> map[i];
	}
	Quick_sort(0, n - 1, map);
	for (int i = 0; i < n; i++)
	{
		cout << map[i] << '\n';
	}
	return 0;
}