[백준 #2693] N번째 큰 수 (C++)

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

2693번: N번째 큰 수

 

입력받은 수를 정렬하여 3번째 큰 값을 출력하면 된다.

많은 정렬 알고리즘 중에 평균적으로 좋은 성능을 가진 퀵 정렬을 사용하여

입력받은 배열을 정렬하고 3번째로 큰 수를 출력하였다.

(오름차순으로 정렬되므로 7번째 인덱스)

 

ex)

1 2 3 4 5 6 7 8 9 1000

idx: 0 1 2 3 4 5 6 7 8 9

 

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

void quickSort(int arr[], int start, int end) {
	if (start >= end) return;
	int pivot = start;
	int i = start + 1;
	int j = end;

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

		if (i > j) {
			swap(arr[pivot], arr[j]);
		}
		else {
			swap(arr[i], arr[j]);
		}
	}
	quickSort(arr, start, j - 1);
	quickSort(arr, j + 1, end);
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);

	int t;
	cin >> t;

	for (int i = 0; i < t; i++) {
		int arr[11];
		for (int j = 0; j < 10; j++) {
			cin >> arr[j];
		}
		quickSort(arr, 0, 9);
		cout << arr[7] << "\n";
	}
	return 0;
}