Добро пожаловать в форум, Guest  >>   Войти | Регистрация | Поиск | Правила | В избранное | Подписаться
Все форумы / Программирование Новый топик    Ответить
 Сортировка по нескольким полям  [new]
sergq
Member

Откуда:
Сообщений: 655
Здравствуйте.

Возник такой вопрос. Допустим есть у меня набор данных
Сто строк, 10 колонок.
Отсортировать по первой допустим quicksort не проблема

А вот как потом отсортировать по втрой, третьей, четвёртой ?
С учётом предидущих сортировок?
1 фев 19, 13:46    [21799645]     Ответить | Цитировать Сообщить модератору
 Re: Сортировка по нескольким полям  [new]
Dima T
Member

Откуда:
Сообщений: 13634
При сравнении проверяй все четыре колонки. Если первые равны, то сравнить вторые и т.д.
1 фев 19, 13:54    [21799666]     Ответить | Цитировать Сообщить модератору
 Re: Сортировка по нескольким полям  [new]
sergq
Member

Откуда:
Сообщений: 655
Dima T
При сравнении проверяй все четыре колонки. Если первые равны, то сравнить вторые и т.д.


так вроде как при quicksort на равенство вообще не сравнивают. Или туплю

procedure qSortdesc(var A: array of byte; min, max: Integer;desc:boolean);
var i, j, supp, tmp: Integer;
begin
supp:=A[max-((max-min) div 2)]; // 
i:=min; j:=max;
while i<j do
  begin
    while A[i]>supp do
    i:=i+1; // 
    while A[j]<supp do
    j:=j-1; // 
    if i<=j then
      begin
        tmp:=A[j]; A[j]:=A[i]; A[i]:=tmp; //
        i:=i+1; j:=j-1; // 
      end;
  end;
if min<j then qSortdesc(A, min, j,desc);
if i<max then qSortdesc(A, i, max,desc);
end;
1 фев 19, 23:26    [21800223]     Ответить | Цитировать Сообщить модератору
 Re: Сортировка по нескольким полям  [new]
mayton
Member

Откуда: loopback
Сообщений: 40510
Любой из предикатов типа
A[i]>supp

Можно поставить под инверсию и перевернуть знак на меньше либо равно.
not A[i]<=supp

Тогда и сравнение будет участвовать. Впрочем на смысл алгоритма это не влияет.

И данный пример - узкий. Он показывает сортировку целых чисел в массиве
а у тебя т.н. "строки и колонки".

Кстати советую уйти от этой терминологии и использовать объект и класс (тип).
А для сравнения нужна функция-компаратор. Которая решает какой объект больше
или меньше или равен по рангу.
2 фев 19, 00:54    [21800255]     Ответить | Цитировать Сообщить модератору
 Re: Сортировка по нескольким полям  [new]
kealon(Ruslan)
Member

Откуда: Нижневартовск
Сообщений: 4487
sergq,

не сравнивают, но в функции сравнения это никто не запрещает сделать в случае равенства по первой, второй, ... колонке
2 фев 19, 00:54    [21800256]     Ответить | Цитировать Сообщить модератору
 Re: Сортировка по нескольким полям  [new]
Dima T
Member

Откуда:
Сообщений: 13634
sergq
Dima T
При сравнении проверяй все четыре колонки. Если первые равны, то сравнить вторые и т.д.


так вроде как при quicksort на равенство вообще не сравнивают. Или туплю

Обычно функция сортировки в качестве одного из параметров получает функцию-компаратор, где прописывается алгоритм сравнения. Например в С
2 фев 19, 08:39    [21800307]     Ответить | Цитировать Сообщить модератору
 Re: Сортировка по нескольким полям  [new]
sergq
Member

Откуда:
Сообщений: 655
kealon(Ruslan)
sergq,

не сравнивают, но в функции сравнения это никто не запрещает сделать в случае равенства по первой, второй, ... колонке


Это что то из этой оперы?
https://stackoverflow.com/questions/47030279/quick-sort-with-multiple-keys
2 фев 19, 20:51    [21800545]     Ответить | Цитировать Сообщить модератору
 Re: Сортировка по нескольким полям  [new]
sergq
Member

Откуда:
Сообщений: 655
mayton
Любой из предикатов типа
A[i]>supp

Можно поставить под инверсию и перевернуть знак на меньше либо равно.
not A[i]<=supp

Тогда и сравнение будет участвовать. Впрочем на смысл алгоритма это не влияет.

И данный пример - узкий. Он показывает сортировку целых чисел в массиве
а у тебя т.н. "строки и колонки".

Кстати советую уйти от этой терминологии и использовать объект и класс (тип).
А для сравнения нужна функция-компаратор. Которая решает какой объект больше
или меньше или равен по рангу.


У меня скорее не строки и колонки и пе объект и класс.
У меня скоре raw файл бинарный. Разбитый на блоки (строки) , а внутри блок разбит на «колонки»
2 фев 19, 20:53    [21800546]     Ответить | Цитировать Сообщить модератору
 Re: Сортировка по нескольким полям  [new]
mayton
Member

Откуда: loopback
Сообщений: 40510
sergq
mayton
Любой из предикатов типа
A[i]>supp

Можно поставить под инверсию и перевернуть знак на меньше либо равно.
not A[i]<=supp

Тогда и сравнение будет участвовать. Впрочем на смысл алгоритма это не влияет.

И данный пример - узкий. Он показывает сортировку целых чисел в массиве
а у тебя т.н. "строки и колонки".

Кстати советую уйти от этой терминологии и использовать объект и класс (тип).
А для сравнения нужна функция-компаратор. Которая решает какой объект больше
или меньше или равен по рангу.


У меня скорее не строки и колонки и пе объект и класс.
У меня скоре raw файл бинарный. Разбитый на блоки (строки) , а внутри блок разбит на «колонки»

Ты можешь называть это сепулькой или кандибобером.

Но в форуме программирования, очень продуктивно использовать устоявшуюся терминологию. Поверь мне.
2 фев 19, 21:24    [21800552]     Ответить | Цитировать Сообщить модератору
 Re: Сортировка по нескольким полям  [new]
Dima T
Member

Откуда:
Сообщений: 13634
sergq
У меня скорее не строки и колонки и пе объект и класс.
У меня скоре raw файл бинарный. Разбитый на блоки (строки) , а внутри блок разбит на «колонки»

Без разницы что там у тебя. Сначала тебе надо сформулировать правило сравнения двух блоков. Записать в виде функции.
И только после этого сортировать.
3 фев 19, 12:25    [21800722]     Ответить | Цитировать Сообщить модератору
 Re: Сортировка по нескольким полям  [new]
mayton
Member

Откуда: loopback
Сообщений: 40510
Автору надо почитать про современное ООП-программирование в Delphi. Вопросы отпадут ИМХО.
3 фев 19, 13:04    [21800736]     Ответить | Цитировать Сообщить модератору
 Re: Сортировка по нескольким полям  [new]
exp98
Member

Откуда:
Сообщений: 1624
sergq, а что, лексикографическое сравнени сразу 4-х блоков не проходит? как я понял, они равной длины
3 фев 19, 20:31    [21800898]     Ответить | Цитировать Сообщить модератору
 Re: Сортировка по нескольким полям  [new]
kealon(Ruslan)
Member

Откуда: Нижневартовск
Сообщений: 4487
sergq
kealon(Ruslan)
sergq,

не сравнивают, но в функции сравнения это никто не запрещает сделать в случае равенства по первой, второй, ... колонке


Это что то из этой оперы?
https://stackoverflow.com/questions/47030279/quick-sort-with-multiple-keys
оно и есть
самый последний ответ из этой темы
4 фев 19, 08:03    [21800998]     Ответить | Цитировать Сообщить модератору
Все форумы / Программирование Ответить