Как быстро отсортировать одномерный массив на основе 3-го столбца (индекс делится на 3) в C ++ - PullRequest
Новая
       50

Как быстро отсортировать одномерный массив на основе 3-го столбца (индекс делится на 3) в C ++

1 голос
/ 18 апреля 2020

У меня есть 1D массив, который a[9]={33888,32567,3,32678,31967,2,32333,32456,0}. Он не может быть преобразован в 2d массив, потому что 2d массив не разрешен. На самом деле в этом 1d-массиве есть три столбца: 

A         B          C
33888     32567      3
32678     31967      2
32333     32456      0

Таким образом, результат сортировки на основе столбца C в 1d-массиве будет: 

32333
32456
0
32678
31967
2
33888
32567
3

Этот массив должен сортировать по столбцу C, то есть все индексы делятся на 3 в массиве 1d. Но этот массив не может быть представлен как 2d массив. Мне нужно быстро отсортировать это с помощью 1D массива. Я реализовал пузырьковую сортировку, но это медленно. Может кто-нибудь помочь, реализовав быструю сортировку этой проблемы в C ++? Если кто-то может сделать это с помощью встроенной функции сортировки с использованием 1d-массива, то это будет работать и для меня. Спасибо.

1 Ответ

1 голос
/ 18 апреля 2020

Вы имеете в виду следующее? 

#include <iostream>
#include <iomanip>
#include <cstdlib>

int cmp( const void *a, const void *b )
{
    const int *p1 = ( const int * )a;
    const int *p2 = ( const int * )b;

    return ( p2[2] < p1[2] ) - ( p1[2] < p2[2] );
}

int main() 
{
    int a[]  = { 33888, 32567, 3, 32678, 31967, 2, 32333, 32456, 0 };
    const size_t N = sizeof( a ) / sizeof( *a );
    const size_t M = 3;

    for ( size_t i = 0; i < N; i++ )
    {
        std::cout << std::setw( 5 ) << a[i] << ' ';
        if ( ( i + 1 ) % M == 0 ) std::cout << '\n';
    }

    std::cout << '\n';

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


    for ( size_t i = 0; i < N; i++ )
    {
        std::cout << std::setw( 5 ) << a[i] << ' ';
        if ( ( i + 1 ) % M == 0 ) std::cout << '\n';
    }

    std::cout << '\n';

    return 0;
}

Выход программы: 

33888 32567     3 
32678 31967     2 
32333 32456     0 

32333 32456     0 
32678 31967     2 
33888 32567     3

То есть число фактических элементов должно быть кратно 3. В общем случае, если число фактические элементы - это N, тогда вызов qsort будет выглядеть как 

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

при условии, что в массиве есть 3 "столбца".

Что касается вашего комментария

Спасибо. Можете ли вы проверить этот массив a [] = {32678,32567,3,32678,32567,2,32678,32456,0,32567,32678,0,32067,32078,1}. Ваш код разрушается, когда я увеличиваю размер массива. Если он работает с любым размером, то будет принят ответ.

, тогда вот вам. 

#include <iostream>
#include <iomanip>
#include <cstdlib>

int cmp( const void *a, const void *b )
{
    const int *p1 = ( const int * )a;
    const int *p2 = ( const int * )b;

    return ( p2[2] < p1[2] ) - ( p1[2] < p2[2] );
}

int main() 
{
    int a[]  = 
    {
        32678, 32567, 3, 
        32678, 32567, 2, 
        32678, 32456, 0, 
        32567, 32678, 0, 
        32067, 32078, 1 
    };

    const size_t N = sizeof( a ) / sizeof( *a );
    const size_t M = 3;

    for ( size_t i = 0; i < N; i++ )
    {
        std::cout << std::setw( 5 ) << a[i] << ' ';
        if ( ( i + 1 ) % M == 0 ) std::cout << '\n';
    }

    std::cout << '\n';

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


    for ( size_t i = 0; i < N; i++ )
    {
        std::cout << std::setw( 5 ) << a[i] << ' ';
        if ( ( i + 1 ) % M == 0 ) std::cout << '\n';
    }

    std::cout << '\n';

    return 0;
}

Программа имеет значение 

32678 32567     3 
32678 32567     2 
32678 32456     0 
32567 32678     0 
32067 32078     1 

32678 32456     0 
32567 32678     0 
32067 32078     1 
32678 32567     2 
32678 32567     3
...