|
|
|
|
Быстрая сортировка
|
|
Студент Сообщения: 445 |
Идея метода заключается в следующем: выбираем в массиве произвольный элемент и ставим его "на своё место". Все элементы меньшие выбранного должны оказаться слева, а больше справа. И потом просто вызываем рекурсивную процедурку, которая аналогичным образом отсортирует левую и правую части массива.
Пример кода: Код:
 procedure swap(var a, b : integer);
var
*c : integer;
begin
*c := a;
*a := b;
*b := c;
end; *{Это просто процедурка, которая меняет местами значения A и B}
procedure sort(l, r : integer);
var
*Y, j, x : integer;
begin
*Y := l;
*j := r; {с помощью указателей Y и J мы будем "двигаться по массиву"}
*x := a[(l + r) div 2]; {выбрали произвольный элемент. Например из серединки}
*repeat
* *while (a[Y] < x) do inc(Y); {Двигаем левый указатель до близжайшего элемента, большего X}
* *while (a[j] > x) do dec(j); {Двигаем правый указатель до близжайшего элемента, меньшего X}
* *if Y <= j then begin
* * *swap(a[Y], a[j]);
* * *inc(Y);
* * *dec(j);
* *end; {поменяли элементы местами, сдвинули указатели}
*until Y > j;
*if Y < r then sort(Y, r);
*if j > l then sort(l, j);
end;
Праверьте ещё раз, правильно ли работает... Если что - стучите  [Гневные ругательства в адрес BigMac-а] Кстати говоря... Паскалевское обращение к элементу массива вида A[W], где вместо "W" стоит "I" твой форум распознал как открытие тэга... Сделай примочку, которая в тэге CODE игнорирует все другие тэги... [/Гневные ругательства в адрес BigMac-а] (Отредактировал(а) noname00.pas - 10:06 8-01-2002) |
|
|
------- Отправлено: 12:56, 08-01-2002 |
|
редкий гость Сообщения: 1696
|
Профиль | Сайт | Отправить PM | Цитировать std::sort это и есть быстрая сортировка (аналог сишного qsort, только на столь нелюбимых кем-то шаблонах
), а он рассказывал про то, как это работает.Цитата:
|
|
|
------- Отправлено: 09:39, 04-03-2002 | #11 |
|
изверг Сообщения: 39
|
Профиль | Сайт | Отправить PM | Цитировать а на фига разбираться? у тея есть алгоритм. описание того, как это должно работать и всё. Да и асм там не сложной, у iP2 И старше гораздо сложнее
|
|
------- Отправлено: 14:39, 04-03-2002 | #12 |
|
редкий гость Сообщения: 1696
|
Профиль | Сайт | Отправить PM | Цитировать Обычно мне хватает моего КЛР (Кормен&Лейзерсон&Ривест).
|
|
------- Отправлено: 17:32, 04-03-2002 | #13 |
|
Участник сейчас на форуме |
 |
Участник вне форума |
 |
Автор темы |
 |
Сообщение прикреплено |
| |||||
| Название темы | Автор | Информация о форуме | Ответов | Последнее сообщение | |
| HDD - быстрая проверка USB-HDD? | Antoniooo | Накопители (SSD, HDD, USB Flash) | 2 | 21-10-2008 12:17 | |
| Быстрая смена сетевых настроек | PERMYAK | Сетевые технологии | 4 | 20-05-2007 16:15 | |
| W2K3+ быстрая смена пользователей | Gudvin | Microsoft Windows NT/2000/2003 | 1 | 05-02-2007 08:58 | |
| Недостаточно быстрая работа компьютера | Vadeneev | Хочу все знать | 5 | 28-09-2004 09:32 | |
| Быстрая перезагрузка | Guest | Microsoft Windows 95/98/Me (архив) | 5 | 24-12-2002 21:54 | |
|
|
Время: 04:58. | © OSzone.net 2001-
|
|
Powered by: vBulletin Copyright ©2000 - 2025, Jelsoft Enterprises Ltd. |
