Сортировка таблицы C ++

Question

У меня есть таблица чисел, которая выглядит следующим образом:

2 8 4 0
3 1 0 9
1 2 3 4
5 4 14 2

Я положил все числа в массив { 2,8,4,0,3,1... }. Есть ли способ отсортировать его по первому столбцу, используя только одномерный массив, чтобы он заканчивался так:

1 2 3 4
2 8 4 0
3 1 0 9
5 4 14 2

Я знаю, что есть способ сделать это с двумерным массивом, но, если яузнать количество столбцов, возможно ли это только с 1D массивом?

Answer 1

Я бы создал массив индексов для ваших данных, а затем отсортировал бы эти индексы;это сохранит приличное количество копий.

Ваша сортировка затем проверит значение числа по заданному индексу.

т.е. для вашего примера - индексы будут 1,2,3, 4 и затем отсортированные будут читать 3,1,2,4

edit: это было 1 на основе;код 0 на основе. Не имеет значения.

По сути, преобразование вашего 1d массива в 2. Так как большая часть ваших данных все еще непрерывна (особенно для большого количества столбцов), чтение все равно должно быть быстрым.

Пример кода:

std::vector<int> getSortedIndexes(std::vector<int> data, int size) {
    int count = data.size() / size;
    std::vector<int> indexes(count);

    // fill in indexes from 0 to "count" since that's the size of our vector
    std::iota(indexes.begin(), indexes.end(), 0);

    // don't write your own sorting implementation .... really; don't.
    std::sort(indexes.begin(), indexes.end(), [data, size](int indexA, int indexB) {
               return data[indexA*size] < data[indexB*size];
             });
    return indexes;
}

Answer 2

Для массивов не определенных пользователем типов легко выполнить задачу, используя стандартную функцию C qsort.

Вот демонстрационная программа.

#include <iostream>
#include <cstdlib>

int cmp( const void *a, const void *b )
{
    const int *left  = static_cast<const int *>( a );
    const int *right = static_cast<const int *>( b );

    return ( *right < *left ) - ( *left < *right );
}

int main()
{
    const size_t N = 4;
    int a[N * N] =
    {
        2, 8, 4, 0, 3, 1, 0, 9, 1, 2, 3, 4, 5, 4, 14, 2 
    };


    for ( size_t i = 0; i < N; i++ )
    {
        for ( size_t j = 0; j < N; j++ )
        {
            std::cout << a[N * i + j] << ' ';
        }
        std::cout << '\n';
    }        

    std::cout << '\n';

    std::qsort( a, N, sizeof( int[N] ), cmp );

    for ( size_t i = 0; i < N; i++ )
    {
        for ( size_t j = 0; j < N; j++ )
        {
            std::cout << a[N * i + j] << ' ';
        }
        std::cout << '\n';
    }        

    std::cout << '\n';
}    

Программавывод

2 8 4 0 
3 1 0 9 
1 2 3 4 
5 4 14 2 

1 2 3 4 
2 8 4 0 
3 1 0 9 
5 4 14 2 

Так что все, что вам нужно, это написать функцию

int cmp( const void *a, const void *b )
{
    const int *left = static_cast<const int *>( a );
    const int *right = static_cast<const int *>( b );

    return ( *right < *left ) - ( *left < *right );
}

и добавить всего одну строку в вашу программу

std::qsort( a, N, sizeof( int[N] ), cmp );

Answer 3

Вы можете использовать пузырьковую сортировку:

void sort_by_name(int* ValueArray, int NrOfValues, int RowWidth)
{
    int CycleCount = NrOfValues / RowWidth;
    int temp;
    (int j = 0; j < CycleCount ; j++) 
    {
       for (int i = 1; i < (CycleCount - j); i++) 
       {
           if(ValueArray[((i-1)*RowWidth)] > ValueArray[(i*RowWidth)]) 
           {
              for(int k = 0; k<RowWidth; k++)
              {
                  temp = ValueArray[(i*RowWidth)+k]
                  ValueArray[(i*RowWidth)+k] = ValueArray[((i-1)*RowWidth)+k];
                  ValueArray[((i-1)*RowWidth)+k] = temp;
              }
           }
       }
    }
}

имейте в виду, что простое создание массива 2D будет НАМНОГО ЛУЧШЕЕ решением

edit: имя переменной