█████████ ████ ███░░░░░███ ░░███ ███ ░░░ ██████ ███████ ██████ ██████ ░███ ███░░███ ███░░███ ███░░███ ███░░███ ░███ ░███ ░███░███ ░███ ░███████ ░███ ░███ ░░███ ███░███ ░███░███ ░███ ░███░░░ ░███ ░███ ░░█████████ ░░██████ ░░████████░░██████ ░░██████ ░░░░░░░░░ ░░░░░░ ░░░░░░░░ ░░░░░░ ░░░░░░

Envío 5402

Problema 0xde - Ordenar un arreglo grande

  • Autor: slash
  • Fecha: 2021-12-15 05:11:38 UTC (Hace más de 2 años)
Caso # Resultado Tiempo Memoria
#1
Correcto
0.002 s 0 KBi
#2
Correcto
0.002 s 0 KBi
#3
Correcto
0.006 s 0 KBi
#4
Correcto
0.003 s 0 KBi
#5
Correcto
0.004 s 0 KBi
#6
Correcto
0.004 s 0 KBi
#7
Tiempo límite excedido
1.074 s 1 KBi
#8
Tiempo límite excedido
1.033 s 3 KBi
#9
Tiempo límite excedido
1.032 s 1 KBi
#10
Tiempo límite excedido
1.071 s 1 KBi
#11
Tiempo límite excedido
1.015 s 1 KBi
#12
Tiempo límite excedido
1.086 s 1 KBi
#13
Tiempo límite excedido
1.055 s 1 KBi
#14
Tiempo límite excedido
1.033 s 1 KBi
#15
Tiempo límite excedido
1.076 s 2 KBi
#16
Correcto
0.041 s 2 KBi
#17
Correcto
0.038 s 2 KBi
#18
Tiempo límite excedido
1.071 s 1 KBi
#19
Tiempo límite excedido
1.073 s 1 KBi
#20
Tiempo límite excedido
1.1 s 1 KBi
#21
Tiempo límite excedido
1.03 s 1 KBi
#22
Tiempo límite excedido
1.053 s 1 KBi
#23
Tiempo límite excedido
1.069 s 1 KBi
#24
Tiempo límite excedido
1.1 s 1 KBi
#25
Tiempo límite excedido
1.051 s 1 KBi
#26
Tiempo límite excedido
1.1 s 1 KBi
#27
Tiempo límite excedido
1.066 s 1 KBi
Puntos totales: 30 / 100

Código

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

#include "iostream"
#include "random"

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(){
    int n; cin>>n;
    vector<int> numbers;
    for(int i = 0; i < n; i++) {
        int in; cin>>in;
        numbers.push_back(in);
    }
    quicksort(numbers,0,n - 1);
    for (int num: numbers) cout<<num<<' ';
}