Доброго времени суток.

Имеется динамический массив целых чисел достаточно большой размерности (например, 100 столбцов х 100 строк).
Как грамотнее реализовать сортировку по выбранному столбцу по убыванию или возрастанию?

Это сообщение отредактировал(а) Keeper89 - 4.2.2010, 17:11

Keeper89, Ну на таких величинах прекрасно работает быстрый сорт (быстродействие O(n log n)) ... http://algolist.ru/sort/quick_sort.php

~FoX~, а что если использовать встроенные классы типа TList или TObjectList? В них уже есть реализация быстрой сортировки. 

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

На счет Tlist и TObjectList не припомню что бы там сортировка хоть какая то была, А вот TStringList именно быстрым сортится... Только критерий там один - по первому символу.... Т.е. в твоем случае только по первому столбцу

Придется, но это не накладно... Ну относительно алгоритма сортировки по крайней мере   

Функцию сравнения можно свою написать и сортировать как захочешь..

Можно сделать так:
Загнать первый столбец, например в TStringList.
Написать свою функцию сравнения, которая возвращает -1 если нужно поменять местами объекты и 1 или 0 в противном случае.
Помимо этого, сделать проверку: если возвращается -1, тогда "вручную" поменять местами элементы всех столбцов.
Конечно, нельзя сказать, что всё это будет работать очень быстро. Но зато удовлетворяет твоим требованиям 


Это сообщение отредактировал(а) artsb - 5.2.2010, 09:07

Keeper89, прикрепляю пример. Посмотри и скажи, правильно ли я тебя понял.

Это сообщение отредактировал(а) artsb - 5.2.2010, 22:32

Присоединённый файл ( Кол-во скачиваний: 6 )
 sort.exe 627,00 Kb

artsb, абсолютно правильно.

bems, спасибо, решение с дженериками - супер! 
Единственное добавил еще одну вещь:

А этот вариант случаем не сортирует всё подряд? Вроде как нужно было по конкретному столбцу. Просто я в Делфи не силён...

Добавлено через 2 минуты и 51 секунду
Всё. Кажись понял 

Выкладываю своё решение (правда на С++). Мало ли, кому-нибудь пригодится.
Выкладываю на С++, т.к. плохо знаком с Делфи. Хотя и могу перевести код и он даже будет работать, но скорее всего, будет не эффективен. И к тому же, могут быть скрытые ошибки.


Алгоритм стащил из реализации в classes.pas 
Объясню почему я написал так:

, а не оставил так как это было реализовано в classes.pas:
Дело в том, что там было написано приблизительно так:

Здесь получается, что когда индексы совпадают, т.е. I==J происходит перестановка элементов с этими индексами, но это бессмысленно как вы понимаете  (пустая трата времени)

ЗЫ профи поправьте меня если что   

Keeper89, попросить пояснений ты мог бы прямо в этой теме. Итак:

Класс Generics.Collections.TArray умеет искать двоичным поиском и сортировать методом быстрой сортировки. Это объеденино в класс, потому что невозможно создать обобщенную функцию, не член класса/объекта. Это ограничение языка. Все методы это методы класса, поэтому не нужно создавать экземпляр TArray.

Метод Generics.Collections.TArray.Sort<T> выполняет быструю сортировку массива элементов типа, указанного в Т. 

Values - собственно массив. В моем примере я объявляю типы

Это нужно только для того чтобы объявление параметра Data не воспринималось как открытый массив, это приводит к несоответствию типов. Это ограничение данного конкретного случая, а не класса TArray или дженериков в целом. Я имею в виду, что в T можно прямо указать array of Integer не объявляя промежуточного типа.
Если Index и Count не указаны, то сортируется весь массив.
Comparer, это объект, реализующий интерфейс IComparer. Если не указан, то используется компаратор по умолчанию. Я еще не вник, что же это за сравнение по умолчанию для разных типов, но случаи с целыми числами и строками очевидны. 

Класс Generics.Defaults.TComparer<T> это абстактный компаратор двух величин типа, указанного в T. Его метод Compare абстрактен, поэтому не стоит напрямую создавать экземпляры этого класса.

Метод Generics.Defaults.TComparer<T>.Construct создает объект класса, унаследованного от TComparer<T>, а значит также поддерживающего интерфейс IComparer<T> Реально создается экземпляр TDelegatedComparer<T>, у которого  метод Compare уже реализован. Эта реализация просто вызывает функцию по ссылке, переданной при вызове Construct.
Анонимные методы это отдельная тема, погугли это сам.
Благодаря тому, что Construct возвращает не сам свежесозданный объект, а его интерфейс, и тому что TComparer<T> унаследован от TInterfacedObject, ты можешь сразу передать интерфейс в TArray.Sort<T>, не заботясь о сохранении ссылки с целью освобождения. Объект будет разрушен автоматически при обнулении счетчика ссылок (в моем примере это происходит сразу после вызова Sort<T>).


Это сообщение отредактировал(а) bems - 5.2.2010, 23:38

bems, все прояснилось, спасибо!

З.Ы. Я просто думал не засорять тему нужными только мне пояснениями, поэтому отправил ЛС.

bems, 
Возник вопрос. Возможно ли заменить 

на другой тип, например

Или даже не Real, а свой собственный?

Это сообщение отредактировал(а) Keeper89 - 21.2.2010, 16:08

Keeper89, можно, но тогда замени тип и в
TArray.Sort<TDoubleArr> и в
TComparer<TDoubleArr>.Construct

Сделал так:

И выскакивает ошибка (в 15 строке, где end):


Это сообщение отредактировал(а) Keeper89 - 21.2.2010, 20:12

Не нужно возвращать TCoefficient.
Независимо от типа сравниваемых величин, возвращается целое. <0 если меньше, 0 если равно, >0 если больше