saber - ordenar un vector de forma descendente en c++

¿Cómo puedo ordenar dos vectores de la misma manera, con criterios que usan solo uno de los vectores?

Question

¿Cómo puedo ordenar dos vectores de la misma manera, con criterios que usan solo uno de los vectores?

Por ejemplo, supongamos que tengo dos vectores del mismo tamaño:

vector<MyObject> vectorA;
vector<int> vectorB;

Luego clasifico vectorA usando alguna función de comparación. Ese vectorA reordenado de clasificación vectorA ¿Cómo puedo hacer que se aplique el mismo reordenamiento al vectorB ?

Una opción es crear una estructura:

struct ExampleStruct {
    MyObject mo;
    int i;
};

y luego vectorA un vector que contenga los contenidos de vectorA y vectorB comprimidos en un solo vector:

// vectorC[i] is vectorA[i] and vectorB[i] combined
vector<ExampleStruct> vectorC;

Esto no parece una solución ideal. ¿Hay otras opciones, especialmente en C ++ 11?

Answer 1

Clasificación in situ con permutación

Usaría una permutación como Timothy, aunque si sus datos son demasiado grandes y no desea asignar más memoria para el vector ordenado, debe hacerlo en el lugar . Aquí hay un ejemplo de una clasificación en contexto O (n) (complejidad lineal) usando permutación :

El truco es obtener la permutación y la permutación inversa para saber dónde colocar los datos sobrescritos por el último paso de clasificación.

template <class K, class T> 
void sortByKey(K * keys, T * data, size_t size){
    std::vector<size_t> p(size,0);
    std::vector<size_t> rp(size);
    std::vector<bool> sorted(size, false);
    size_t i = 0;

    // Sort
    std::iota(p.begin(), p.end(), 0);
    std::sort(p.begin(), p.end(),
                    [&](size_t i, size_t j){ return keys[i] < keys[j]; });

    // ----------- Apply permutation in-place ---------- //

    // Get reverse permutation item>position
    for (i = 0; i < size; ++i){
        rp[p[i]] = i;
    }

    i = 0;
    K savedKey;
    T savedData;
    while ( i < size){
        size_t pos = i;
        // Save This element;
        if ( ! sorted[pos] ){
            savedKey = keys[p[pos]];
            savedData = data[p[pos]];
        }
        while ( ! sorted[pos] ){
            // Hold item to be replaced
            K heldKey  = keys[pos];
            T heldData = data[pos];
            // Save where it should go
            size_t heldPos = rp[pos];

            // Replace 
            keys[pos] = savedKey;
            data[pos] = savedData;

            // Get last item to be the pivot
            savedKey = heldKey;
            savedData = heldData;

            // Mark this item as sorted
            sorted[pos] = true;

            // Go to the held item proper location
            pos = heldPos;
        }
        ++i;
    }
}

Answer 2

Encontrar una permutación de ordenación

Dado un std::vector<T> y una comparación para T , queremos ser capaces de encontrar la permutación que utilizaría si tuviera que ordenar el vector usando esta comparación.

template <typename T, typename Compare>
std::vector<std::size_t> sort_permutation(
    const std::vector<T>& vec,
    Compare& compare)
{
    std::vector<std::size_t> p(vec.size());
    std::iota(p.begin(), p.end(), 0);
    std::sort(p.begin(), p.end(),
        [&](std::size_t i, std::size_t j){ return compare(vec[i], vec[j]); });
    return p;
}

Aplicando una permutación de ordenación

Dado un std::vector<T> y una permutación, queremos ser capaces de construir un nuevo std::vector<T> que se reordena de acuerdo con la permutación.

template <typename T>
std::vector<T> apply_permutation(
    const std::vector<T>& vec,
    const std::vector<std::size_t>& p)
{
    std::vector<T> sorted_vec(vec.size());
    std::transform(p.begin(), p.end(), sorted_vec.begin(),
        [&](std::size_t i){ return vec[i]; });
    return sorted_vec;
}

Por supuesto, puede modificar apply_permutation para apply_permutation el vector que le da en lugar de devolver una nueva copia ordenada. Este enfoque sigue siendo la complejidad del tiempo lineal y utiliza un bit por elemento en su vector. Teóricamente, sigue siendo la complejidad del espacio lineal; pero, en la práctica, cuando sizeof(T) es grande, la reducción en el uso de memoria puede ser dramática. ( Ver detalles )

template <typename T>
void apply_permutation_in_place(
    std::vector<T>& vec,
    const std::vector<std::size_t>& p)
{
    std::vector<bool> done(vec.size());
    for (std::size_t i = 0; i < vec.size(); ++i)
    {
        if (done[i])
        {
            continue;
        }
        done[i] = true;
        std::size_t prev_j = i;
        std::size_t j = p[i];
        while (i != j)
        {
            std::swap(vec[prev_j], vec[j]);
            done[j] = true;
            prev_j = j;
            j = p[j];
        }
    }
}

Ejemplo

vector<MyObject> vectorA;
vector<int> vectorB;

auto p = sort_permutation(vectorA,
    [](T const& a, T const& b){ /*some comparison*/ });

vectorA = apply_permutation(vectorA, p);
vectorB = apply_permutation(vectorB, p);

Recursos

• std::vector
• std::iota
• std::sort
• std::swap
• std::transform

Answer 3

1. Haz un vector de pares de tus vectores individuales.
   inicializar el vector de pares
   Agregar a un vector de par

2. Haga un comparador de clasificación personalizado:
   Ordenar un vector de objetos personalizados
   http://rosettacode.org/wiki/Sort_using_a_custom_comparator#C.2B.2B

3. Clasifica tu vector de pares.

4. Separe su vector de pares en vectores individuales.

5. Pon todos estos en una función.

Código:

std::vector<MyObject> vectorA;
std::vector<int> vectorB;

struct less_than_int
{
    inline bool operator() (const std::pair<MyObject,int>& a, const std::pair<MyObject,int>& b)
    {
        return (a.second < b.second);
    }
};

sortVecPair(vectorA, vectorB, less_than_int());

// make sure vectorA and vectorB are of the same size, before calling function
template <typename T, typename R, typename Compare>
sortVecPair(std::vector<T>& vecA, std::vector<R>& vecB, Compare cmp)
{

    std::vector<pair<T,R>> vecC;
    vecC.reserve(vecA.size());
    for(int i=0; i<vecA.size(); i++)
     {
        vecC.push_back(std::make_pair(vecA[i],vecB[i]);   
     }

    std::sort(vecC.begin(), vecC.end(), cmp);

    vecA.clear();
    vecB.clear();
    vecA.reserve(vecC.size());
    vecB.reserve(vecC.size());
    for(int i=0; i<vecC.size(); i++)
     {
        vecA.push_back(vecC[i].first);
        vecB.push_back(vecC[i].second);
     }
}

Answer 4

Me gustaría contribuir con una extensión que se me ocurrió. El objetivo es poder ordenar múltiples vectores al mismo tiempo usando una sintaxis simple.

sortVectorsAscending(criteriaVec, vec1, vec2, ...)

El algoritmo es el mismo que el propuesto por Timothy, pero utilizando plantillas variadas , por lo que podemos ordenar múltiples vectores de tipos arbitrarios al mismo tiempo.

Aquí está el fragmento de código:

template <typename T, typename Compare>
void getSortPermutation(
    std::vector<unsigned>& out,
    const std::vector<T>& v,
    Compare compare = std::less<T>())
{
    out.resize(v.size());
    std::iota(out.begin(), out.end(), 0);

    std::sort(out.begin(), out.end(),
        [&](unsigned i, unsigned j){ return compare(v[i], v[j]); });
}

template <typename T>
void applyPermutation(
    const std::vector<unsigned>& order,
    std::vector<T>& t)
{
    assert(order.size() == t.size());
    std::vector<T> st(t.size());
    for(unsigned i=0; i<t.size(); i++)
    {
        st[i] = t[order[i]];
    }
    t = st;
}

template <typename T, typename... S>
void applyPermutation(
    const std::vector<unsigned>& order,
    std::vector<T>& t,
    std::vector<S>&... s)
{
    applyPermutation(order, t);
    applyPermutation(order, s...);
}

template<typename T, typename Compare, typename... SS>
void sortVectors(
    const std::vector<T>& t,
    Compare comp,
    std::vector<SS>&... ss)
{
    std::vector<unsigned> order;
    getSortPermutation(order, t, comp);
    applyPermutation(order, ss...);
}

// make less verbose for the usual ascending order
template<typename T, typename... SS>
void sortVectorsAscending(
    const std::vector<T>& t,
    std::vector<SS>&... ss)
{
    sortVectors(t, std::less<T>(), ss...);
}

Ideone en Ideone .

Explico esto un poco mejor en esta publicación de blog .

Answer 5

No estoy seguro de si esto funciona, pero usaría algo como esto. Por ejemplo, para ordenar dos vectores, utilizaría el método de ordenación de burbujas descendente y los pares de vectores.

Para el tipo de burbuja descendente, crearía una función que requiere un par de vectores.

void bubbleSort(vector< pair<MyObject,int> >& a)
{
    bool swapp = true;
    while (swapp) {
        int key;
        MyObject temp_obj;
        swapp = false;
        for (size_t i = 0; i < a.size() - 1; i++) {
            if (a[i].first < a[i + 1].first) {
                temp_obj = a[i].first;
                key = a[i].second;

                a[i].first = a[i + 1].first;
                a[i + 1].first = temp_obj;

                a[i].second = a[i + 1].second;
                a[i + 1].second = key;

                swapp = true;
            }
        }
    }
}

Después de eso, pondría tus 2 valores vectoriales en un par de vectores. Si puede agregar valores al mismo tiempo, use este y luego llame a la función de clasificación de burbujas.

vector< pair<MyObject,int> > my_vector;

my_vector.push_back( pair<MyObject,int> (object_value,int_value));

bubbleSort(my_vector);

Si desea usar valores después de agregar a sus 2 vectores, puede usar este y luego llamar a la función de clasificación de burbujas.

vector< pair<MyObject,int> > temp_vector;

for (size_t i = 0; i < vectorA.size(); i++) {
            temp_vector.push_back(pair<MyObject,int> (vectorA[i],vectorB[i]));
        }

bubbleSort(temp_vector);

Espero que esto ayude. Saludos, Caner

Answer 6

Supongo que vectorA y vectorB tienen la misma longitud. Puedes crear otro vector, vamos a llamarlo pos, donde:

pos[i] = the position of vectorA[i] after sorting phase

y luego, puede ordenar vectorB usando pos, es decir, crear vectorBsorted donde:

vectorBsorted[pos[i]] = vectorB[i]

y luego vectorBsorted se ordena por la misma permutación de índices que vectorA is.