quicksort.cpp

#include <vector>
#include <iostream>

using namespace std;

void swap(int& a, int& b) {
	int tmp = a;
	a = b;
	b = tmp;
}

int partition(vector<int>& arr, int left, int right) {
	int pivot = arr[right];
	int i = left - 1;

	for (int j = left; j <= right - 1; j++) {
		if (pivot > arr[j]) {
			i++;
			swap(arr[i], arr[j]);
		}
	}
	swap(arr[i + 1], arr[right]);
	return (i + 1);
}

void quicksort(vector<int>& arr, int left, int right) {
	if (left < right) {
		int p = partition(arr, left, right);

		quicksort(arr, left, p - 1);
		quicksort(arr, p + 1, right);
	}
	return;
}

int main(void) {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);

	int n;
	cin >> n;
	vector<int> arr(n);
	for (int i = 0; i < n; i++) {
		cin >> arr[i];
	}
	
	quicksort(arr, 0, n - 1);
	for (int i = 0; i < n; i++) {
		cout << arr[i] << '\n';
	}
	return 0;
}

quicksort2.cpp

#include <vector>
#include <iostream>

using namespace std;

void swap(int& a, int& b) {
	int tmp = a;
	a = b;
	b = tmp;
}

int partition(vector<int>& arr, int l, int r) {
	int pivot = arr[l];
	int i = r + 1;

	for (int j = r; j > l; j--) {
		if (pivot < arr[j]) {
			i--;
			swap(arr[i], arr[j]);
		}
	}
	swap(arr[i - 1], arr[l]);
	return (i - 1);
}

void quicksort(vector<int>& arr, int l, int r) {
	if (l < r) {
		int p = partition(arr, l, r);

		quicksort(arr, l, p - 1);
		quicksort(arr, p + 1, r);
	}
}

int main(void) {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
  
	int n;
	cin >> n;
	vector<int> a(n);
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}

	quicksort(a, 0, n - 1);
	for (int i = 0; i < n; i++) {
		cout << a[i] << '\n';
	}
	return 0;
}