На главную
ПРАВИЛА FAQ Помощь Участники Календарь Избранное DigiMania RSS
msm.ru
[!] Как относитесь к модерированию на этом форуме? Выскажите свое мнение здесь
Модераторы: JoeUser, Qraizer
  
> Сортировка, Си
Есть таблица, при клике по заголовку столбца должна происходить сортировка данных по строкам (например как в проводнике).
Прикреплённая картинка
Прикреплённая картинка

Данные в таблице заданы массивом символов data[50][500][256], где максимально возможные значения : 50 столбцов x 500 строк x 256 символлов в ячейке.

Вопрос : Как отсортировать таблицу ?

Вопрос наверное элементарный, но поиск в интернете дает какие-то фрагментальные данные, и кроме того какой алгоритм лучше подойдет?
Вот пример с массивом чисел
ExpandedWrap disabled
    #include <stdio.h>
    #include <stdlib.h>
     
    int values[] = { 40, 10, 100, 90, 20, 25 };
    int compare (const void * a, const void * b)
    {
      return ( *(int*)a - *(int*)b );
    }
     
    int main ()
    {
      int n;
      qsort (values, 6, sizeof(int), compare);
      for (n=0; n<6; n++)
         printf ("%d ",values[n]);
      return 0;
    }

Как сюда вставить массив символов (сроку), тем более массив строк.
И хватит ли стека на мой массив (читал что быстрая сортировка из-за рекурсии может вызвать переполнение стека).
Сообщение отредактировано: E.A. -
E.A., по сути - тут все элементарно, для 500 строк для qsort переполнения стека и не близко не будет.
Вопрос в другом, в "дизайне" массива. Нужно правильно определить порядок, а именно - первое измерение это строки, второе - это столбцы, и последнее символы в столбце. В таком вот случае в функции qsort будут передаваться строки для сравнения в функцию сравнения. Соответственно, для реализации сортировки по столбцу в этой функции сравнения нужно сравнивать данные нужного столбца (поля). Все решается приведением типов в функции сравнения и применении собственно операции сравнения двух строк.
Мои программные ништякиhttp://majestio.info
В вашем случае, E.A., будет как-то так:
ExpandedWrap disabled
    char data[50][500][256];
    int sortCol=2; // колонка
    int compare( const void *a, const void *b)
    {
      return strcmp( (char*)a, (char*)b );
    }
    ...
    qsort( (void*)(data[sortCol]), 500, 256, compare);


Добавлено
Насчёт последней строки не уверен, так надёжнее будет:
ExpandedWrap disabled
    qsort( (void*)(&data[sortCol][0][0]), 500, 256, compare);


Добавлено
Ай, виноват, так только кликнутая колонка и отсортируется. Пардон-с. :blush:

Добавлено
Тогда б я посоветовал взять исходник qsort'а (благо она крохотная) и там операцию перемещения пары элементов заменить на нужное перемещение в вашей базе, E.A., раз уж она имеет такое строение строк в памяти. Будет архибыстро и весьма лаконично.
Но "костылёк" с ГОСТовским qsort'ом, бесспорно, можно и помучать; но надо колдовать... (чую, что надо бы сначала индексы посортировать, а потом уж базой заняться).
Цитата Славян @
Ай, виноват, так только кликнутая колонка и отсортируется.

Как же это произойдёт ?
Любая сортировка делает сравнение и "swap".
(Отличия алгоритмов - это, в основном, отличия
в алгоритмах выбора индексов массива для манипулирования объектами)
Данная функция делает swap для 32-х битных
значений. Но ни как не строк.
---
Эту функцию можно было бы удобно использовать,
если бы кроме пользовательской функции сравнения
она вызывала пользовательскую функцию "swap".
---
Теоретически возможен вариант - составим массив
указателей на строки. Тогда можно отсортировать строки
перестановкой указателей.
Но в данном случае надо также переставлять строки в других
столбцах. Поскольку совокупность содержимого ячеек одной строки таблицы
это один объект сортировки.
---
Тогда получается как-то так:
1. Изначальный массив с данными не будем изменять, результат будет в аналогичном массиве.
Заполняем его читая таблицу.
2. Составляем массив [500] указателей на строки выбранного для сортировки столбца.
3. Сортируем указатели указанной процедурой
4. Потом ищем каждый из указателей отсортированного массива указателей в изначальном
массиве с выбранным столбцом. В результате получим два индекса - старого размещения и нового.
5. Найденный указатель покажет нам, с какого и на какое место должна быть пернесена информация
всего ряда ячеек (всех столбцов).
Копируем все строки по всем столбцам из изначального массива со старым индексом
в массив результата с новым индексом.
6. Массив результата выведем в таблицу.
Сообщение отредактировано: ЫукпШ -
Подпись была выключена в связи с наложенным заземлением.
Цитата
...переполнения стека и не близко не будет...

Цитата
...Будет архибыстро и весьма лаконично...

Так если это такой "детский" массив, то может пузырьком попробовать... такой алгоритм у меня получится. )) Потому как переделать qsort по исходникам мне, не программисту, представляется проблематичным с этими (void*) и т.д.
Спасибо за советы, завтра попробую.
Сообщение отредактировано: E.A. -
Цитата E.A. @
Данные в таблице заданы массивом символов data[50][500][256], где максимально возможные значения : 50 столбцов x 500 строк x 256 символлов в ячейке.

А здесь разве не вот такой массив должен быть - data[500][50][256]? Т.е. 500 строк, каждая из которых состоит из 50 х 256 символов.
Ну и сортировать сам этот массив смысла нет - нужно сделать ещё один - массив указателей или индексов строк и сортировать его, и отображать в таблице тоже его.
Цитата
здесь разве не вот такой массив должен быть - data[500][50][256]?

data[50][500][256]
при выборе измерений руководствовался следующим : 0 - измерение по оси x, 1 - измерение по оси y
cellubound[0] - число столбцов
cellubound[1] - число строк
такой вид вместо традиционных названий column и row дает уменьшение кода там где эти функции практически одинаковы
например найти на сколько сдвинута таблица по оси х и по оси y ... и т.д. можно находить уже в цикле.
поэтому на первом месте то что меняется по оси х а это столбцы...
возможно у других и не так, но мне уже переделывать о-о-очень много, поэтому пусть будет так.

вот что получилось:
ExpandedWrap disabled
    void LinkDllTableSorting(HWND hwndpic, UINT message, WPARAM wparam, LPARAM lparam, int cellubound[2], int cellwidth[50], int cellheight[1], int step[2], int frame[2], int param)
    {
        int i, j, k, n;
        char tmpdata[50][1][256];
        n = -1;
        for (i=0; i<cellubound[0]; i++)
        {
            if (e::linkgridsortedstate[i] != 0) // здесь статус столбца 0 нет сортировки, 1 сортировка min->max, -1 сортировка max->min
            {
                n = i;
                break;
            }
        }
        if (n != -1)
        {
            if (e::linkgridsortedstate[n] == 1)
            {
                for (i=0; i<cellubound[1]-1; i++)
                {
                    for (j=0; j<cellubound[1]-i-1; j++)
                    {
                        if (strcmp(e::linkgriddata[n][j], e::linkgriddata[n][j+1]) > 0)
                        {
                            for (k=0; k<cellubound[0]; k++)
                            {
                                strcpy(tmpdata[k][0], e::linkgriddata[k][j]);
                                strcpy(e::linkgriddata[k][j], e::linkgriddata[k][j+1]);
                                strcpy(e::linkgriddata[k][j+1], tmpdata[k][0]);
                            }
                        }
                    }
                }
            }
            if (e::linkgridsortedstate[n] == -1)
            {
                for (i=0; i<cellubound[1]-1; i++)
                {
                    for (j=0; j<cellubound[1]-i-1; j++)
                    {
                        if (strcmp(e::linkgriddata[n][j], e::linkgriddata[n][j+1]) < 0)
                        {
                            for (k=0; k<cellubound[0]; k++)
                            {
                                strcpy(tmpdata[k][0], e::linkgriddata[k][j]);
                                strcpy(e::linkgriddata[k][j], e::linkgriddata[k][j+1]);
                                strcpy(e::linkgriddata[k][j+1], tmpdata[k][0]);
                            }
                        }
                    }
                }
            }
        }
    }

работает достаточно быстро и при максимальном размере, а при 200 сроках мгновенно, правда появился ожидаемый недостаток после 1 идет 10 ...
Прикреплённая картинка
Прикреплённая картинка

но это легко исправить - нужно определить в колонке 1) только числа или 2) числа и буквы.
и выполнить сортировку по этим данным.

ЫукпШ ваш алгоритм, конечно отличный, возможно когда-нибудь так и сделаю, если будет необходимость ускорить сортировку.
Всем спасибо.

Если у кого-то есть предложения по улучшению с удовольствием выслушаю.
Сообщение отредактировано: E.A. -
1)
Прочитал про сортировку пузырьком. Решил тоже усовершенствовать.
Сделать предварительную сортировку:
Идея в следующем : поменять первый и последний, второй и предпоследний... и т.д. до середины. т.е. избавиться от "черепах" как в википедии называют
Для отсортированного в обратном порядке массива это самое то что нужно ))

2)
Добавлена проверка на числа, если число то сортировка как нужно 1, 2, 3 ... а не 1, 10, 100

3)
Ввел дополнительный массив digitdata[i] чтобы постоянно не выполнять в цикле atof()

Получилось много кода, но результатом доволен - сортировка на максимальном размере работает мгновенно.
Наверное самый плохой вариант данных это 1, 499, 3, 497 ... , 498, 2 т.е когда предварительная сортировка не даст заметного выйгрыша, но такой вариант для моих задач маловероятен.

Вопрос решен.
Сообщение отредактировано: E.A. -
Цитата E.A. @
правда появился ожидаемый недостаток после 1 идет 10 ...

надо всего лишь изменить алгоритм сравнения строк.

Добавлено
Цитата E.A. @
1)
Прочитал про сортировку пузырьком. Решил тоже усовершенствовать.

В Сети легко можно найти описание и исходники
широко используемых алгоритмов сортировки:
- пузырьковая сортировка
- сортировка выбором
- сортировка вставками
- шейкерная сортировка (разновидность пузырьковой сортировки)
- сортировка Шелла
- быстрая сортировка
Наверняка подберёшь что-нибудь подходящее.
Сообщение отредактировано: ЫукпШ -
Подпись была выключена в связи с наложенным заземлением.
1 пользователей читают эту тему (1 гостей и 0 скрытых пользователей)
0 пользователей:


Рейтинг@Mail.ru
[ Script Execution time: 0,1351 ]   [ 24 queries used ]   [ Generated: 19.09.19, 19:06 GMT ]