Новости
Видео
Microsoft
Windows 10
Железо
Программы
Форум

Имя пользователя:
Пароль:  
Помощь | Регистрация | Забыли пароль?  | Правила  

Компьютерный форум OSzone.net » Программирование, базы данных и автоматизация действий » Программирование и базы данных » Быстрая сортировка

1 2 Следующая >
Ответить
Настройки темы
Быстрая сортировка

Студент


Сообщения: 445
Благодарности: 8

Профиль | Отправить PM | Цитировать

Идея метода заключается в следующем: выбираем в массиве произвольный элемент и ставим его "на своё место". Все элементы меньшие выбранного должны оказаться слева, а больше справа. И потом просто вызываем рекурсивную процедурку, которая аналогичным образом отсортирует левую и правую части массива.

Пример кода:
Код: Выделить весь код
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;
As is (я не несу ответственности за последствия получения вами данного кода)

Праверьте ещё раз, правильно ли работает... Если что - стучите

[Гневные ругательства в адрес BigMac-а]
Кстати говоря... Паскалевское обращение к элементу массива вида A[W], где вместо "W" стоит "I" твой форум распознал как открытие тэга... Сделай примочку, которая в тэге CODE игнорирует все другие тэги...
[/Гневные ругательства в адрес BigMac-а]

(Отредактировал(а) noname00.pas - 10:06 8-01-2002)

-------
*Origin: Lots of people talking, few of them - no... (2:5020/****.**)

Это сообщение посчитали полезным следующие участники:

Отправлено: 12:56, 08-01-2002

 

Аватара для BigMac

Призрачный админ


Сообщения: 5254
Благодарности: 90

Профиль | Отправить PM | Цитировать

noname00.pas
Понял..... он распознал его как косой шрифт.......гляну.....

-------
Истина где-то рядом...

Отправлено: 13:54, 08-01-2002 | #2



Для отключения данного рекламного блока вам необходимо зарегистрироваться или войти с учетной записью социальной сети.

Если же вы забыли свой пароль на форуме, то воспользуйтесь данной ссылкой для восстановления пароля.


Пользователь


Сообщения: 6
Благодарности: 0

Профиль | Отправить PM | Цитировать

noname00.pas
Вау! Круто! А на сколько быстрее она работает. А то зачем ее писать если я и пузырьком могу отсортить

Отправлено: 14:37, 08-01-2002 | #3


Студент


Сообщения: 445
Благодарности: 8

Профиль | Отправить PM | Цитировать

BluesBrother
В худшем случае (при специально подобранных данных) она работает за O(N*N) операций. Но вероятность выпадения именно таких данных на достаточно больших массивах ничтожна мала, поэтому в общем случае кол-во операций можно оценивать как O(N*log(N)). В среднем этот алгоритм работает быстрее, чем HeapSort, Шелл и прочие алгоритмы сложности O(N*log(N))

(Отредактировал(а) noname00.pas - 11:46 8-01-2002)

-------
*Origin: Lots of people talking, few of them - no... (2:5020/****.**)

Отправлено: 14:45, 08-01-2002 | #4


Мичуринский ученик


Сообщения: 740
Благодарности: 1

Профиль | Отправить PM | Цитировать

noname00.pas

-------
Apis.NET@oszone.net

Отправлено: 07:25, 09-01-2002 | #5


редкий гость


Сообщения: 1696
Благодарности: 44

Профиль | Сайт | Отправить PM | Цитировать

Цитата:
Кстати говоря... Паскалевское обращение к элементу массива вида A[W], где вместо "W" стоит "I" твой форум распознал как открытие тэга... Сделай примочку, которая в тэге CODE игнорирует все другие тэги...
Лень. Если нужно поставить именно [[, то пиши квадратную скобку дважды [[[[. []как ни странно, но это написано не жирным шрифтом[]

-------
http://ivank.ru

Отправлено: 09:43, 08-02-2002 | #6


Студент


Сообщения: 445
Благодарности: 8

Профиль | Отправить PM | Цитировать

ivank
А если програмка уже написана, а я её через буффер обмена сюда вставляю? :Р

-------
*Origin: Lots of people talking, few of them - no... (2:5020/****.**)

Отправлено: 13:04, 09-02-2002 | #7


редкий гость


Сообщения: 1696
Благодарности: 44

Профиль | Сайт | Отправить PM | Цитировать

noname00.pas
существует такая штука как "Поиск и замена". Открываешь блокнот, и проводишь в нём эту архисложную операцию со своей прогой

-------
http://ivank.ru

Отправлено: 17:55, 09-02-2002 | #8


Студент


Сообщения: 445
Благодарности: 8

Профиль | Отправить PM | Цитировать

ivank
Проще один раз исправить скрипт, чем каждый раз открывать блокнот.

-------
*Origin: Lots of people talking, few of them - no... (2:5020/****.**)

Отправлено: 23:23, 10-02-2002 | #9


изверг


Сообщения: 39
Благодарности: 0

Профиль | Сайт | Отправить PM | Цитировать

std::sort :>
Кнута почитайте-с, - не знаснёте - много нового узнаете

-------
RTFM, RTFM и потом опять RTFM
http://vudz.tk

Отправлено: 22:03, 03-03-2002 | #10

1 2 Следующая >


Компьютерный форум OSzone.net » Программирование, базы данных и автоматизация действий » Программирование и базы данных » Быстрая сортировка

Участник сейчас на форуме Участник сейчас на форуме Участник вне форума Участник вне форума Автор темы Автор темы Шапка темы Сообщение прикреплено

Похожие темы
Название темы Автор Информация о форуме Ответов Последнее сообщение
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


« Предыдущая тема | Следующая тема »


 
Переход