На главную
ПРАВИЛА FAQ Помощь Участники Календарь Избранное RSS
15 мая "Исходники.РУ" отмечают 20-летие присутствия в сети!
Поздравляем всех причастных и неравнодушных с юбилеем сайта!
И огромное спасибо всем, кто был с нами все эти годы!
msm.ru
[!] Как относитесь к модерированию на этом форуме? Выскажите свое мнение здесь
Модераторы: 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 будут передаваться строки для сравнения в функцию сравнения. Соответственно, для реализации сортировки по столбцу в этой функции сравнения нужно сравнивать данные нужного столбца (поля). Все решается приведением типов в функции сравнения и применении собственно операции сравнения двух строк.
      Мои программные ништякиhttps://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)
                    Прочитал про сортировку пузырьком. Решил тоже усовершенствовать.

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


                    Рейтинг@Mail.ru
                    [ Script Execution time: 0,1742 ]   [ 22 queries used ]   [ Generated: 4.06.20, 01:14 GMT ]