Ru-Board.club
← Вернуться в раздел «Прикладное программирование»

» Сортировка методом пузырька в Маткаде

Автор: Smog
Дата сообщения: 18.12.2003 18:58
Сабж
Автор: Lechii
Дата сообщения: 20.12.2003 13:31
Smog

это не оно ?
Автор: mastervigo
Дата сообщения: 20.12.2003 13:41
пример для Паскаля (язык в MathCad'e мне не известен), но ты просил также алгоритм:
объявление переменных
A массив
s временная переменная

текст проги
for j:=0 to High(A) do
for i:=1 to High(A) do
if A[i-1] > A[i]
then
begin
s:=A[i-1];
A[i-1]:=A[i];
A[i]:=s
end;
отсортирует по возрастанию.
Автор: Smog
Дата сообщения: 20.12.2003 20:19
Lechii

Цитата:
это не оно ?

посмотрим, я щас на компе, где маткада нет, но наверное, судя по названию ))
mastervigo

Цитата:
for j:=0 to High(A) do
for i:=1 to High(A) do
if A[i-1] > A[i]
then
begin
s:=A[i-1];
A[i-1]:=A[i];
A[i]:=s
end;
отсортирует по возрастанию.

спасибо, насколько на паскале легче программить, а
Автор: evilman
Дата сообщения: 21.12.2003 10:48
Smog
извини, но зачем такое извращение понадобилось?
в маткаде свои Sorting Functions есть..
Автор: krast
Дата сообщения: 21.12.2003 16:12

Цитата:
текст проги
for j:=0 to High(A) do
for i:=1 to High(A) do
if A[i-1] > A[i]
then
begin
s:=A[i-1];
A[i-1]:=A[i];
A[i]:=s
end;
отсортирует по возрастанию.


Он отсортирует, но есть некоторые уточнения к алгоритму.
При первом проходе внешнего цикла (по j) на последнем месте в массиве окажется максимальный элемент. При втором витке на предпоследнем месте окажется наибольший элемент из оставшейся части массива, и так далее. То есть, чем больше значение счетчика j, тем больше будет холостых сравнений if. Поэтому условие для внутреннего цикла следует переписать в таком виде:
for i := 1 to High(A) - j do

Не говоря о том, что и во внешнем цикле нужно _бежать_ не до High(A), а до High(A) - 1

Вот не люблю я такие обмены значений двух переменных местами. Мне больше нравится вариант без привлечения третьей:

A[i] := A[i] + A[j];
A[j] := A[i] - A[j]; // в A[j] теперь лежит значение из A[i]
A[i] := A[i] - A[j]; // в A[i] - значение из A[j]

Ну, это старые университетские замашки проклевываются. Понятно что это дело вкуса.

И еще. Алгоритм можно улучшить введя флаг - был ли поменяны значения хоть одной пары переменных при очередном проходе. Ясен пень, что если нет, то можно сворачивать удочки.
Дальше: Можно также запоминать индекс элемента, при котором произошел последний обмен. Все места в массиве, выше (больше) этого элемента уже _расселись_ по своим местам и смысла ходить за этот индекс для нормального алгоритма нету.
Можно еще и по очереди сменять направления проходов для того чтобы алгоритм не скатывался в самый худший свой вариант при некоторых массивах (думаю, понятно каких) когда ему придется отработать ВСЕ итерации.

А вообще-то лучше взять любую книгу по алгоритмам и почитать, полезное времяпрепровождение гарантирую.

Кстати, если тебе нужен алгоритм сортировки больших массивов, то используй сортировку с лучшим временем выполнения. В _пузырчастой_ сортировке оно составляет O(n^2), где n - количество элементов в массиве. Например, возьми сортировку при помощи куч (также именуемую пирамидальной сортировкой), у которой следующий порядок роста: O(n * log(n)). Уж поверь мне что это лучше. Можно также использовать и сортировки за линейное время ( O(n) ), но это уже надо смотреть на специфику проблемной области.


Цитата:
спасибо, насколько на паскале легче программить, а

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

Добавлено
Эх, а ведь давал слово не постится в программистском форуме на руборде.
Smog, только из уважения к тебе отреплаился
Автор: mastervigo
Дата сообщения: 22.12.2003 05:56
krast
силён...

Страницы: 1

Предыдущая тема: программирование микроконтроллеров


Форум Ru-Board.club — поднят 15-09-2016 числа. Цель - сохранить наследие старого Ru-Board, истории становления российского интернета. Сделано для людей.