[C++/백준 2751번] 수 정렬하기 2

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

2751번: 수 정렬하기 2

 

#include <iostream>
#include <algorithm>
using namespace std;
void quick_sort(int* data, int start, int end) {
    if (start >= end) {
   
        return;
    }

    int pivot = start;
    int i = pivot + 1; 
    int j = end; 
    int temp;

    while (i <= j) {

        while (i <= end && data[i] <= data[pivot]) {
            i++;
        }
        while (j > start && data[j] >= data[pivot]) {
            j--;
        }

        if (i > j) {

            temp = data[j];
            data[j] = data[pivot];
            data[pivot] = temp;
        }
        else {
            temp = data[i];
            data[i] = data[j];
            data[j] = temp;
        }
    }

    // 분할 계산
    quick_sort(data, start, j - 1);
    quick_sort(data, j + 1, end);
}
int main()
{
	int N;

	cin >> N;

    int *arr = new int[N];

	for (int i = 0; i < N; i++)
	{
		cin >> arr[i];
	}

	
	//quick_sort(arr, 0, N - 1);
    sort(arr, arr + N);

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


    delete[] arr;
	return 0;
}

 

2751번 문제를 풀며 알게 된 것들

• cin, cout 보다 printf, scanf가 빠르다.
• stl 내장함수인 sort함수가 직접 구현한 정렬 알고리즘보다 효율적이다.