|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Sergey Politov 2:5015/176.18 14 Jan 2002 05:50:30
To : Alexey Zhivotov
Subject : Re^3: Quick sort
--------------------------------------------------------------------------------
До меня дошли слухи, что *13.01.02* *1:00:26* пролетало сообщение
от Alexey к *Sergey Politov* про *"Re^2: Quick sort"*. И я решил вмешаться.
[...]
AZ> В каком смысле порядок ? мне нужно, чтобы, если я имею уже
AZ> отсортированые строки по первым 6-и символам привет123 привет234
AZ> привет142 то после пересортировки заново не получалочь что-то типа
AZ> привет234 привет123 привет142
в твоем примере должно получиться так:
привет123
привет234
привет142?
Если да, то именно это я и имел ввиду.
SP>> Тогда я бы использовал сортировку слиянием, если я не ошибаюсь она в
SP>> ФАКе есть, если нету - пиши расскажу что это такое.
AZ> А какова она по скоростным качествам по сравнению с сабжем при работе с
AZ> двунаправленными списками из порядка 1-2 тысяч элементов?
Сложность алгоритма O(nlogn), как и у QSort.
AZ> P.S. В факе про сортировку слиянием для файлов только, но что-то мне её
AZ> раелизация не нравится - больно всё громоздкое, да и для списков приделать
AZ> трудно. Можкт есть то-же самое, только для списков или модернезированая
AZ> версия
AZ> сабжа ? Так что пиши, а то непонятно.
Hе нравиться реализация? Hапиши свою, идея простая. Делим массив на кусочки по
два элемента, сортируюм каждую такую пару.
4 2|6 4|6 7|2 8|3 -> 2 4|4 6|6 7|2 8|3
Потом берем уже четверки элементов, каждая четверка состоит из двух
отсортированных пар, сливаем их, что бы сортировка получилась отсортированной.
2 4\4 6|6 7\2 8|3 -> 2 4 4 6|2 6 7 8|3
Теперь переходим к восьмеркам.
2 4 4 6\2 6 7 8|3 -> 2 2 4 4 6 6 7 8|3
Hу а теперь по шестнадцать элементов, только как видишь сдесь нехватка, поэтому
будем сливать два куска один из восьми, а другой из 1 эл-та.
2 2 4 4 6 6 7 8\3 -> 2 2 3 4 4 6 6 7 8
все сортировка закончена, если бы массив на этом не кончился пришлось бы
делить на куски по 32,64, и т.д. каждый раз увеличавая размер в два раза.
Это можно и на списки переделать, только маразму много.
Просто поробуй сначала для массива сделать, отдельную програмку напиши.
Если что не получится - пиши, постараюсь помочь.
np: Helloween "A Million To One"
Искренне Ваш
Sergey Politov
--- WP/95 Rus 1.78 Релиз 1 Reg.
* Origin: Металл сила - всем рэперам могила. (2:5015/176.18)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
