Сортировка количества списков по индексам и приоритетам

Question

У меня есть коллекция списков, каждый из которых содержит от 6 до 7 значений. Мол,

list1 = 2,4,7,4,9,5
list2 = 4,3,7.3,9,8,1.2
list3 = 2,2.4,7,9,8,5
list4 = 9,1.6,4,3,4,1
list5 = 2,5,7,9,1,4
list6 = 6,8,7,2,1,5
list7 = 4,2,5,2,1,3

Теперь я хочу отсортировать их с помощью индекса1 как первичного и индекса3 как вторичного, а индекса2 - как третичного и так далее. То есть вывод должен быть таким:

 2,2.4,7,9,8,5
 2,4,7,4,9,5
 2,5,7,9,1,4
 4,2,5,2,1,3
 6,8,7,2,1,5
 9,1.6,4,3,4,1

Я хочу, чтобы порядок списка был сначала отсортирован по index1, и если значения для index1 одинаковы, то сортировка выполняется по index3 и, если это происходит в дальнейшем, по сравнению с index2. Здесь число списков меньше, которое может увеличиться до 20, а индексы также могут увеличиться до 20.

Алгоритм, который я хочу знать, такой же, как и при сортировке песен iTunes, в которой песни с одинаковым альбомом сортируются сначала по исполнителю, а затем по рангу, а затем по имени. Это альбом, если названия альбомов совпадают, тогда сортировка выполняется по исполнителю, если он одинаков, затем по рангу и так далее. Код может быть в C / C ++ / tcl / shell.

Answer 1

sort -n -t ',' -k 1 -k 3 -k 2

Ввести списки в виде отдельных строк.

Answer 2

Чтобы сделать это в Tcl, при условии, что данных не так много (несколько МБ не будут «огромными»), проще всего будет:

# Read the values in from stdin, break into lists of lists
foreach line [split [read stdin] "\n"] {
    lappend records [split $line ","]
}

# Sort twice, first by secondary key then by primary (lsort is _stable_)
set records [lsort -index 1 -real $records]
set records [lsort -index 0 -real $records]

# Write the values back out to stdout
foreach record $records {
    puts [join $record ","]
}

Если вы используете что-то более сложное, чем простые числа, рассмотрите возможность использования пакета csv в Tcllib для синтаксического анализа и форматирования, поскольку он будет иметь дело со многими синтаксическими проблемами, возникающими в реальных данных. Если вы имеете дело с большим количеством данных (где «много» зависит от того, сколько памяти вы используете), подумайте об использовании более ориентированного на поток метода обработки данных (и есть несколько других оптимизаций при обработке памяти) и вы также можете использовать опцию -command для lsort, чтобы предоставить собственный компаратор, чтобы вы могли сортировать только один раз; увы, производительность пользовательского компаратора довольно высока, но для многих записей выиграет уменьшенное число сравнений. Или поместите данные в базу данных, такую ​​как SQLite или Postgres.

Answer 3

Поскольку вы запросили решение Tcl:

set lol {
   {2 4 7 4 9 5}
   {4 3 7.3 9 8 1.2}
   {2 2.4 7 9 8 5}
   {9 1.6 4 3 4 1}
   {2 5 7 9 1 4}
   {6 8 7 2 1 5}
   {4 2 5 2 1 3}
}

set ::EPS 10e-6
proc compareLists {ixo e1 e2} {
   foreach ix $ixo {
      set d [expr {[lindex $e1 $ix] - [lindex $e2 $ix]}]
      if {abs($d) > $::EPS} {
         return [expr {($d>0)-($d<0)}]
      }
   }
   return 0
}

foreach li [lsort -command [list compareLists {0 2 1}] $lol] {
   puts $li
}

Надеюсь, это поможет.

Answer 4

Вы можете использовать сортировку STL , и тогда все, что вам нужно сделать, это написать функцию сравнения, которая делает то, что вы хотите (пример в ссылке должен быть достаточно хорошим).

Answer 5

Вот решение C ++:

#include <iostream>
#include <vector>
#include <algorithm>

template <typename Array, typename CompareOrderIndex>
struct arrayCompare
{
   private:
      size_t
         size ;
      CompareOrderIndex
        index ;
   public:

      arrayCompare( CompareOrderIndex idx ) :  size( idx.size() ), index(idx)  { }

      bool helper( const Array &a1, const Array &a2, unsigned int num ) const
      {
         if( a1[ index[size-num] ] > a2[ index[size-num] ] )
         {
            return false ;
         }

         if( !(a1[ index[size-num] ] < a2[ index[size-num] ]) )
         {
            if( 1 != num )
            {
               return helper( a1, a2, num-1 ) ;   
            }
         }

         return true ;
      }

      bool operator()(  const Array &a1, const Array &a2 ) const
      {
         return helper( a1, a2, size ) ; 

      }
} ;

int main()
{
   std::vector< std::vector<float> > lists = {     { 2, 4,   7,   4, 9, 5},
                                                   { 4, 3,   7.3, 9, 8, 1.2 },
                                                   { 2, 2.4, 7,   9, 8, 5 },
                                                   { 4, 2,   5,   2, 1, 3 },
                                                   { 9, 1.6, 4,   3, 4, 1 },
                                                   { 2, 5,   7,   9, 1, 4 },
                                                   { 6, 8,   7,   2, 1, 5 },
                                                   { 4, 2,   5,   2, 1, 1 },
                                                };
   //
   // Specify the column indexes to compare and the order to compare.
   // In this case it will first compare column 1 then 3 and finally 2.
   // 
   //std::vector<int> indexOrder = { 0, 2, 1, 3, 4 ,5  } ;
   std::vector<int> indexOrder = { 0, 2, 1  } ;

   arrayCompare< std::vector<float>, std::vector<int>> compV( indexOrder ) ;

   std::sort( lists.begin(), lists.end(), arrayCompare< std::vector<float>, std::vector<int>>( indexOrder )  ) ;

    for(auto p: lists) 
    {
       for( unsigned int i = 0; i < p.size(); ++i )
       {
          unsigned int idx = ( i > (indexOrder.size() -1) ? i : indexOrder[i] ) ;

          std::cout << p[idx] << ", " ;
       }
       std::cout << std::endl ;
    }
}