stable - C++ clasificación y seguimiento de índices

stable sort c++

Question

Usando C ++, y con suerte la biblioteca estándar, quiero ordenar una secuencia de muestras en orden ascendente, pero también quiero recordar los índices originales de las muestras nuevas.

Por ejemplo, tengo un conjunto, o vector, o matriz de muestras A : [5, 2, 1, 4, 3] . Quiero ordenarlos para que sean B : [1,2,3,4,5] , pero también quiero recordar los índices originales de los valores, para poder obtener otro conjunto que sería: C : [2, 1, 4, 3, 0 ] - que corresponde al índice de cada elemento en ''B'', en la ''A'' original.

Por ejemplo, en Matlab puedes hacer:

 [a,b]=sort([5, 8, 7])
 a = 5 7 8
 b = 1 3 2

¿Alguien puede ver una buena manera de hacer esto?

Answer 1

¿Son los artículos en el vector únicos? Si es así, copie el vector, clasifique una de las copias con STL Sort y luego podrá encontrar qué índice tenía cada elemento en el vector original.

Si se supone que el vector maneja elementos duplicados, creo que es mejor implementar su propia rutina de clasificación.

Answer 2

Bueno, mi solución usa la técnica de residuos. Podemos ubicar los valores bajo clasificación en los 2 bytes superiores y los índices de los elementos, en los 2 bytes inferiores:

int myints[] = {32,71,12,45,26,80,53,33};

for (int i = 0; i < 8; i++)
   myints[i] = myints[i]*(1 << 16) + i;

Luego ordena los array myints como de costumbre:

std::vector<int> myvector(myints, myints+8);
sort(myvector.begin(), myvector.begin()+8, std::less<int>());

Después de eso, puedes acceder a los índices de los elementos a través de residuum. El siguiente código imprime los índices de los valores ordenados en orden ascendente:

for (std::vector<int>::iterator it = myvector.begin(); it != myvector.end(); ++it)
   std::cout << '' '' << (*it)%(1 << 16);

Por supuesto, esta técnica funciona solo para los valores relativamente pequeños en la matriz original myints (es decir, los que pueden caber en los 2 bytes superiores de int ). Pero tiene el beneficio adicional de distinguir valores idénticos de myints : sus índices se imprimirán en el orden correcto.

Answer 3

Es más fácil de lo que parece ser.

Supongamos que el vector dado es

A=[2,4,3]

Crear un nuevo vector

V=[0,1,2] // indicating positions

Ordene V y mientras ordena en lugar de comparar elementos de V, compare los elementos correspondientes de A

 //Assume A is a given vector with N elements
 vector<int> V(N);
 int j=0;
 std::iota(V.begin(),V.end(),j++); //Initializing
 for(int i=0;i<N;i++)
      V[i]=i;
 sort( V.begin(),V.end(), [&](int x,int y){return A[x]<A[y];} );

Answer 4

Escribí una versión genérica de index sort.

template <class RAIter, class Compare>
void argsort(RAIter iterBegin, RAIter iterEnd, Compare comp, 
    std::vector<size_t>& indexes) {

    std::vector< std::pair<size_t,RAIter> > pv ;
    pv.reserve(iterEnd - iterBegin) ;

    RAIter iter ;
    size_t k ;
    for (iter = iterBegin, k = 0 ; iter != iterEnd ; iter++, k++) {
        pv.push_back( std::pair<int,RAIter>(k,iter) ) ;
    }

    std::sort(pv.begin(), pv.end(), 
        [&comp](const std::pair<size_t,RAIter>& a, const std::pair<size_t,RAIter>& b) -> bool 
        { return comp(*a.second, *b.second) ; }) ;

    indexes.resize(pv.size()) ;
    std::transform(pv.begin(), pv.end(), indexes.begin(), 
        [](const std::pair<size_t,RAIter>& a) -> size_t { return a.first ; }) ;
}

El uso es el mismo que el de std :: sort a excepción de un contenedor de índice para recibir índices ordenados. pruebas:

int a[] = { 3, 1, 0, 4 } ;
std::vector<size_t> indexes ;
argsort(a, a + sizeof(a) / sizeof(a[0]), std::less<int>(), indexes) ;
for (size_t i : indexes) printf("%d/n", int(i)) ;

debería obtener 2 1 0 3. para los compiladores sin compatibilidad con c ++ 0x, reemplace la expresión lamba como una plantilla de clase:

template <class RAIter, class Compare> 
class PairComp {
public:
  Compare comp ;
  PairComp(Compare comp_) : comp(comp_) {}
  bool operator() (const std::pair<size_t,RAIter>& a, 
    const std::pair<size_t,RAIter>& b) const { return comp(*a.second, *b.second) ; }        
} ;

y reescribir std :: sort como

std::sort(pv.begin(), pv.end(), PairComp(comp)()) ;

Answer 5

Hay otra forma de resolver esto, usando un mapa:

vector<double> v = {...}; // input data
map<double, unsigned> m; // mapping from value to its index
for (auto it = v.begin(); it != v.end(); ++it)
    m[*it] = it - v.begin();

Sin embargo, esto erradicará elementos no únicos. Si eso no es aceptable, use un multimapa:

vector<double> v = {...}; // input data
multimap<double, unsigned> m; // mapping from value to its index
for (auto it = v.begin(); it != v.end(); ++it)
    m.insert(make_pair(*it, it - v.begin()));

Para generar los índices, itere sobre el mapa o multimapa:

for (auto it = m.begin(); it != m.end(); ++it)
    cout << it->second << endl;

Answer 6

Haz un std::pair en la función y luego ordena el par:

Versión genérica :

template< class RandomAccessIterator,class Compare >
auto sort2(RandomAccessIterator begin,RandomAccessIterator end,Compare cmp) ->
   std::vector<std::pair<std::uint32_t,RandomAccessIterator>>
{
    using valueType=typename std::iterator_traits<RandomAccessIterator>::value_type;
    using Pair=std::pair<std::uint32_t,RandomAccessIterator>;

    std::vector<Pair> index_pair;
    index_pair.reserve(std::distance(begin,end));

    for(uint32_t idx=0;begin!=end;++begin,++idx){
        index_pair.push_back(Pair(idx,begin));
    }

    std::sort( index_pair.begin(),index_pair.end(),[&](const Pair& lhs,const Pair& rhs){
          return cmp(*lhs.second,*rhs.second);
    });

    return index_pair;
}

ideone

Answer 7

Hermosa solución de @Lukasz Wiklendt! Aunque en mi caso necesitaba algo más genérico, lo modifiqué un poco:

template <class RAIter, class Compare>
vector<size_t> argSort(RAIter first, RAIter last, Compare comp) {

  vector<size_t> idx(last-first);
  iota(idx.begin(), idx.end(), 0);

  auto idxComp = [&first,comp](size_t i1, size_t i2) {
      return comp(first[i1], first[i2]);
  };

  sort(idx.begin(), idx.end(), idxComp);

  return idx;
}

Ejemplo: Encuentre índices que clasifiquen un vector de cadenas por longitud, excepto por el primer elemento que es un maniquí.

vector<string> test = {"dummy", "a", "abc", "ab"};

auto comp = [](const string &a, const string& b) {
    return a.length() > b.length();
};

const auto& beginIt = test.begin() + 1;
vector<size_t> ind = argSort(beginIt, test.end(), comp);

for(auto i : ind)
    cout << beginIt[i] << endl;

huellas dactilares:

abc
ab
a

Answer 8

Me encontré con esta pregunta, y descubrí que ordenar los iteradores directamente sería una forma de ordenar los valores y hacer un seguimiento de los índices; No es necesario definir un contenedor adicional de pair de (valor, índice) que es útil cuando los valores son objetos grandes; Los iteradores proporcionan el acceso tanto al valor como al índice:

/*
 * a function object that allows to compare
 * the iterators by the value they point to
 */
template < class RAIter, class Compare >
class IterSortComp
{
    public:
        IterSortComp ( Compare comp ): m_comp ( comp ) { }
        inline bool operator( ) ( const RAIter & i, const RAIter & j ) const
        {
            return m_comp ( * i, * j );
        }
    private:
        const Compare m_comp;
};

template <class INIter, class RAIter, class Compare>
void itersort ( INIter first, INIter last, std::vector < RAIter > & idx, Compare comp )
{ 
    idx.resize ( std::distance ( first, last ) );
    for ( typename std::vector < RAIter >::iterator j = idx.begin( ); first != last; ++ j, ++ first )
        * j = first;

    std::sort ( idx.begin( ), idx.end( ), IterSortComp< RAIter, Compare > ( comp ) );
}

en cuanto al ejemplo de uso:

std::vector < int > A ( n );

// populate A with some random values
std::generate ( A.begin( ), A.end( ), rand );

std::vector < std::vector < int >::const_iterator > idx;
itersort ( A.begin( ), A.end( ), idx, std::less < int > ( ) );

ahora, por ejemplo, el quinto elemento más pequeño en el vector ordenado tendría el valor **idx[ 5 ] y su índice en el vector original sería la distance( A.begin( ), *idx[ 5 ] ) o simplemente *idx[ 5 ] - A.begin( ) .

Answer 9

Para este tipo de pregunta, almacene los datos de la matriz orignal en una nueva información y luego busque binariamente el primer elemento de la matriz ordenada en la matriz duplicada y ese índice se debe almacenar en un vector o matriz.

input array=>a
duplicate array=>b
vector=>c(Stores the indices(position) of the orignal array
Syntax:
for(i=0;i<n;i++)
c.push_back(binarysearch(b,n,a[i]));`

Aquí binarysearch es una función que toma la matriz, el tamaño de la matriz, el elemento de búsqueda y devolvería la posición del elemento buscado.

Answer 10

Puede ordenar std :: pair en lugar de solo ints - first int es datos originales, second int es índice original. A continuación, proporcione un comparador que solo ordena en la primera int. Ejemplo:

Your problem instance: v = [5 7 8]
New problem instance: v_prime = [<5,0>, <8,1>, <7,2>]

Ordene la nueva instancia de problema usando un comparador como:

typedef std::pair<int,int> mypair;
bool comparator ( const mypair& l, const mypair& r)
   { return l.first < r.first; }
// forgetting the syntax here but intent is clear enough

El resultado de std :: sort en v_prime, usando ese comparador, debería ser:

v_prime = [<5,0>, <7,2>, <8,1>]

Puede pelar los índices caminando por el vector, agarrando .segundo de cada estándar :: par.

Answer 11

Si es posible, puede construir la matriz de posición usando la función encontrar y luego ordenar la matriz.

O tal vez puede usar un mapa donde la clave sería el elemento, y los valores una lista de su posición en las siguientes matrices (A, B y C)

Depende de los usos posteriores de esas matrices.

Answer 12

Usando C ++ 11 lambdas

template <typename T>
vector<size_t> sort_indexes(const vector<T> &v) {

  // initialize original index locations
  vector<size_t> idx(v.size());
  iota(idx.begin(), idx.end(), 0);

  // sort indexes based on comparing values in v
  sort(idx.begin(), idx.end(),
       [&v](size_t i1, size_t i2) {return v[i1] < v[i2];});

  return idx;
}

Ahora puede usar el vector de índice devuelto en iteraciones como

for (auto i: sort_indexes(v)) {
  cout << v[i] << endl;
}

Obviamente, también puede optar por suministrar su propio vector de índice original, función de clasificación, comparador o reordenar automáticamente v en la función sort_indexes utilizando un vector adicional.

Answer 13

vector<pair<int,int> >a;

for (i = 0 ;i < n ; i++) {
    // filling the original array
    cin >> k;
    a.push_back (make_pair (k,i)); // k = value, i = original index
}

sort (a.begin(),a.end());

for (i = 0 ; i < n ; i++){
    cout << a[i].first << " " << a[i].second << "/n";
}

Ahora a contiene tanto nuestros valores como sus respectivos índices en el ordenado.

a[i].first = value en i ''th.

a[i].second = idx en la matriz inicial.