Envío 5403

Código

//
// Created by danie on 12/11/2021.
//

#include "iostream"
#include "random"

#define fast_io ios_base::sync_with_stdio(false); cin.tie(NULL);

using namespace std;



void swap(int &a, int &b){
//    a = b + a;
//    b = a - b;
//    a = a - b;
    int temp = b;
    b = a;
    a = temp;
}

int partition(vector<int> &cards, int from, int to){
    int x = cards[to];
    int i = from;
    for (int j = from; j < to; j++){
        if (cards[j] <= x){
            swap(cards[i], cards[j]);
            i++;
        }
    }
    swap(cards[i], cards[to]);
    return i;
}

void quicksort(vector<int> &cards, int from, int to){
    if (to > from){
        int part = partition(cards, from, to);
        quicksort(cards,from, part  -1);
        quicksort(cards, part + 1, to);
    }
}

int randomized_partition(vector<int> &cards, int from, int to){
    int k = rand();
    int i = (rand() % (to - from)) + from;
    swap(cards[to], cards[i]);
    return partition(cards,from,to);
}

int randomized_select(vector<int> &cards, int from, int to, int ith){ // este es el bueno
    if(to == from) return cards[from];
    int ordered_item = randomized_partition(cards, from, to);
    int distance = ordered_item - from;
    if (ith == ordered_item) return cards[ordered_item];
    if (ith < ordered_item) return randomized_select(cards, from, ordered_item - 1, ith);
    return randomized_select(cards, ordered_item + 1, to, ith);
}

//int randomized_select(vector<int> &cards, int from, int to, int ith){
//    if(to == from) return cards[from];
//    int ordered_item = randomized_partition(cards, from, to);
//    int elements_on_left_array = (ordered_item - from) ;
//    if (ith == elements_on_left_array) return cards[ordered_item];
//    if (ith < ordered_item) return randomized_select(cards, from, ordered_item - 1, ith);
//    return randomized_select(cards, ordered_item + 1, to, ith - elements_on_left_array);
//}

void randomized_quicksort(vector<int> &cards,int from,int to){
    if (to > from){
        int part = randomized_partition(cards, from, to);
        randomized_quicksort(cards,from, part - 1);
        randomized_quicksort(cards, part + 1, to);
    }
}

//void tests(){
//    vector<int> cards = {8,7,5,7,3,5,1,0}; // 0 1 3 5 5 7 7 8 sorted
//    vector<int> cpcopy_cards = cards;
//    vector<int> copy_cards = cards;
////    quicksort(cpcopy_cards, 0, cpcopy_cards.size() - 1);
////    for(int card:cpcopy_cards)cout<<card<<' ';
////    cout<<'\n';
////    randomized_quicksort(cards,0,cards.size() - 1);
////    for(int card:cards)cout<<card<<' ';
////    cout<<'\n';
////    for(int card:copy_cards)cout<<card<<' ';
//    cout<<'\n'<<randomized_select(copy_cards,0,cards.size() - 1, 7)<<'\n';
//    for(int card:copy_cards)cout<<card<<' ';
//
//
//}

int main(){
    fast_io
    int n; cin>>n;
    vector<int> numbers;
    for(int i = 0; i < n; i++) {
        int in; cin>>in;
        numbers.push_back(in);
    }
    randomized_quicksort(numbers,0,n - 1);
    for (int num: numbers) cout<<num<<' ';
}