Untitled

mail@pastecode.io avatar
unknown
plain_text
2 years ago
1.0 kB
27
Indexable
Never
#include <iostream>
using namespace std;

void printArray(int * arr, int n){
	for(int i=0; i<n; i++){
		cout << arr[i] << ",";
	}
	cout << endl;
}

int partition(int * arr, int low, int high, int pivot){
	
	int i=low, j=low;
	while(i <= high ){
		
		if(arr[i] > pivot){
			i++;
		} else {
			swap(arr[i], arr[j]);
			i++; j++;
		}
	}
	
	return j-1;
}

int quickSelect(int * arr, int low, int high, int k){
	
	int pivot = arr[high];
	int pi = partition(arr, low, high, pivot);
	
	if(k < pi){
		return quickSelect(arr, low, pi-1, k);
	} else if(k > pi) {
		return quickSelect(arr, pi+1, high, k);
	} else {
		return arr[pi];
	}
	
}

void quickSort(int * arr, int low, int high){
	
	if(low >= high) return;

	int pi = partition(arr, low, high, arr[high]);
	cout << pi << "**";
	quickSort(arr, low, pi-1);
	quickSort(arr, pi+1, high);
}

int main() {
	// your code goes here
	
	int n;
	cin >> n;
	
	int arr[n];
	for(int i=0; i<n; i++){
		cin >> arr[i];
	}
	
	quickSort(arr, 0, n-1);
	
	printArray(arr, n);
	return 0;
}