подскажите пожалуйста программную реализацию самого (наиболее) быстрого алгоритма сортировки (по возрастанию) строк двумерного массива по определенному столбцу (например первому)...в сортируемом массиве порядка 50-70 тыс. записей (строк) и 5 столбцов...

http://algolist.manual.ru/sort/index.php
http://ru.wikipedia.org/wiki/%D0%A1%D0%BE%...B%D0%B0#C.2B.2B

http://ru.wikipedia.org/wiki/Quicksort#.D0....B8.D1.82.D0.BC

http://www.cyberguru.ru/cpp-sources/algori...ov-massiva.html


Это сообщение отредактировал(а) vikaz - 22.7.2009, 14:47

хотелось бы получить конкретный алгоритм сортировки двумерного массива, так сказать проверенный на практике и на таких больших объемах данных...

Добавлено @ 10:52
а как программно можно отсортировать целочисленный массив с помощью StringList-а (его свойства Sort или метода Sorted())???

Это сообщение отредактировал(а) gordmiand - 23.7.2009, 10:53

А по ссылкам которые я Вам написал, там что нет такого алгоритма?

trie дерево. Быстрее врядли получится, хотя памяти может сожрать много

xvr : а что за "trie дерево"? хотелось бы примерчик сортировки по определенному столбцу двумерного массива с помощью данного дерева...

Я правильно понял. У тебя есть что-то типа таблицы, тебе нужно отсортировать эту таблицу по одному столбцу, а остальные строки просто поменять местами в соответствии с отсортированным столбцом? 

Т.е. вот например есть данные:



Если сортировать их по первому столбцу, то мы должны получить:



Так? За тем исключением, что у тебя первый столбец это строка. 

Это сообщение отредактировал(а) W4FhLF - 23.7.2009, 15:31

А что, google уже отменили?     http://en.wikipedia.org/wiki/Trie
trie это не совсем сортировка, это скорее способ построить упорядоченный набор строк.
Собственно сам trie представляет собой N дерево, в котором каждая дуга соответствует букве одной или более строк, а узлы представляют собой точки между буквами.


Сортировка делается в 2 прохода:
1) Все строки из заданного столбца помещаются в trie дерево (вместе с номером строки)
2) Полученное trie дерево рекурсивно обходится, по номерам строк из него строится выходная таблица (вместо таблицы можно построить массив индексов и отображать данные в порядке этих индексов)

xvr: как-то Вы все очень сложно говорите - деревья....для такой-то задачи...

W4FhLF: Ваши цитаты полностью верны (вот такой целочисленный массив надо отсортировать как Вы и указали в цитатах...токо столбец-это столбец а не как Вы предположили "столбец это строка")...хотелось бы узнать Ваше оптимальное с т.з. скорости решение такой задачки...

gordmiand, а как ты хранишь данный массив?

Я для рашения такой задачи использовал следующую структуру хранения данных:



Т.е. каждый столбец -- это отдельный вектор. 

Что делает сортировку в данном случае медленной? Это перестановка строк. Чтобы переставить строки местами во всех векторах нужен отдельный цикл. Это очень медленно. Выход простой, надо проиндексировать таблицу перед сортировкой и делать перестановки только в нужном столбце (в том, который сортируем) запоминая номера перестановок в отдельном массиве индексов. А после сортировки, за O(n), в соответствии с массивом индексов, делать перестановки оставшихся столбцов. 

Такая сортировка по времени равносильна сортировке одномерного массива + O(n) на перестановку строк после сортировки. 

А вам надо максимально эффективно и просто? Так не бывает   
Эээ. Trie деревья для строк. Если вам нужно сортировать по числам, то вам это не подойдет.
Для чисел (целых) наиболее быстро будет radix sort (см в google)

Еще есть у меня подозрение, что вам нужна не максимально быстрая сортировка, а другая форма представления таблицы (например через индексы строк). 

Если у вас при сортировке будет перестраиваться сама таблица, то это будет медленно, какой бы алгоритм вы не применили