|
|
шпаргалки - Форум D-N
|
шпаргалки
| |
| [Lio] | Дата: Воскресенье, 22.04.2007, 23:18 | Сообщение # 1 |
 d-[]ak
Группа: Администраторы
Сообщений: 357
Статус: Offline
| Алгоритм 1. Сортировка вставками. | Quote | Program InsertionSort;
Var A,B : array[1..1000] of integer;
N,i,j : integer;
Begin
{Определение размера массива A (N) и его заполнение}
…
{сортировка данных}
for i:=1 to N do
begin
j:=i;
while (j>1) and (B[j-1]>A[i]) do
begin
B[j]:=B[j-1];
j:=j-1;
end;
B[j]:=A[i];
end;
{Вывод массива B}
…
End. |
Алгоритм 2. Пузырьковая сортировка.
| Quote | Program BubbleSort;
Var A : array[1..1000] of integer;
N,i,j,p : integer;
Begin
{Определение размера массива A (N) и его заполнение}
…
{сортировка данных}
for i:=1 to n do
for j:=1 to n-i do
if A[j]>A[j+1] then
begin {Обмен элементов}
p:=A[j];
A[j]:=A[j+1];
A[j+1]:=P;
end;
{Вывод отсортированного массива A}
…
End. |
$$$ для web-мастеров
|
| |
| |
| Ablai | Дата: Вторник, 24.04.2007, 17:14 | Сообщение # 2 |
 участник
Группа: Клан D-N
Сообщений: 41
Статус: Offline
| и что дает нам такая сортировка?
|
| |
| |
| [Alex] | Дата: Вторник, 24.04.2007, 18:18 | Сообщение # 3 |
 мастер
Группа: Участники
Сообщений: 227
Статус: Offline
| на самом деле мне тоже не понятно что это такое.[Lio] мой тебе совет прежде чем создавать тему "шпоры по паскалю" ты объясни че это вообще такое 
|
| |
| |
| [Lio] | Дата: Вторник, 24.04.2007, 18:30 | Сообщение # 4 |
|
d-[]ak
Группа: Администраторы
Сообщений: 357
Статус: Offline
| Еще в раннем детстве в нас просыпается стремление к разрушению и хаосу - один их базовых инстинктов человека. Но по мере взросления в нем крепнет противоположное начало - тяга к упорядочиванию и систематизации. Появление компьютеров дало возможность работать с куда большими объемами информации. Проблема упорядочивания стала более остро, на нее были кинуты силы лучших умов. В прикладной математике она получила название «задача сортировки». Надо отдать должное исследователям, постарались они хорошо. Об этом свидетельствует то огромное количество методов, которыми нам предлагают сортировать данные. Зачем же так много? И правда - может, достаточно одного эффективного способа, и не надо морочить себе голову таким обилием? Ответ на этот вопрос состоит в том, что очень трудно иногда бывает сопоставить эффективность двух разных методов. Проще говоря: одни более удобны в одних случаях, другие - в других. Проблемам сортировок Дональд Кнут посвятил целый том своего «Искусства программирования». Попробуем и мы разобраться в этом подробней. Итак, постановка задачи такова: есть набор неупорядоченных данных (массив), задача - выдать те же данные, упорядоченные по некоторому полю (ключу) по возрастанию (убыванию). Обычно данные представляются в виде ключа и некоторой связанной с ним информации. Например, год рождения и фамилия. Рассмотрим несколько алгоритмов, решающих данную задачу.
$$$ для web-мастеров
|
| |
| |
| [Lio] | Дата: Вторник, 24.04.2007, 18:34 | Сообщение # 5 |
|
d-[]ak
Группа: Администраторы
Сообщений: 357
Статус: Offline
| Алгоритм 1. Сортировка вставками.
Это изящный и простой для понимания метод. Вот в чем его суть: создается новый массив, в который мы последовательно вставляем элементы из исходного массива так, чтобы новый массив был упорядоченным. Вставка происходит следующим образом: в конце нового массива выделяется свободная ячейка, далее анализируется элемент, стоящий перед пустой ячейкой (если, конечно, пустая ячейка не стоит на первом месте), и если этот элемент больше вставляемого, то подвигаем элемент в свободную ячейку (при этом на том месте, где он стоял, образуется пустая ячейка) и сравниваем следующий элемент. Так мы прейдем к ситуации, когда элемент перед пустой ячейкой меньше вставляемого, или пустая ячейка стоит в начале массива. Помещаем вставляемый элемент в пустую ячейку. Таким образом, по очереди вставляем все элементы исходного массива. Очевидно, что если до вставки элемента массив был упорядочен, то после вставки перед вставленным элементом расположены все элементы, меньшие его, а после - большие. Так как порядок элементов в новом массиве не меняется, то сформированный массив будет упорядоченным после каждой вставки. А значит, после последней вставки мы получим упорядоченный исходный массив. Вот как такой алгоритм можно реализовать на языке программирования Pascal:
*дальше смотрим код, который вверху*
В принципе, данную сортировку можно реализовать и без дополнительного массива B, если сортировать массив A сразу при считывании, т. е. осуществлять вставку нового элемента в массив A.
Алгоритм 2. Пузырьковая сортировка.
Реализация данного метода не требует дополнительной памяти. Метод очень прост и состоит в следующем: берется пара рядом стоящих элементов, и если элемент с меньшим индексом оказывается больше элемента с большим индексом, то мы меняем их местами. Эти действия продолжаем, пока есть такие пары. Легко понять, что когда таких пар не останется, то данные будут отсортированными. Для упрощения поиска таких пар данные просматриваются по порядку от начала до конца. Из этого следует, что за такой просмотр находится максимум, который помещается в конец массива, а потому следующий раз достаточно просматривать уже меньшее количество элементов. Максимальный элемент как бы всплывает вверх, отсюда и название алгоритма. Так как каждый раз на свое место становится по крайней мере один элемент, то не потребуется более N проходов, где N - количество элементов. Вот как это можно реализовать:
*смотрим код вверху*
$$$ для web-мастеров
|
| |
| |
| [Alex] | Дата: Вторник, 24.04.2007, 21:54 | Сообщение # 6 |
|
мастер
Группа: Участники
Сообщений: 227
Статус: Offline
| [Lio], можно было и менее подробно рассказать 
|
| |
| |
| [Lio] | Дата: Вторник, 24.04.2007, 22:01 | Сообщение # 7 |
|
d-[]ak
Группа: Администраторы
Сообщений: 357
Статус: Offline
| [Alex], просили вдвоем - вот и получили вдвойне
$$$ для web-мастеров
|
| |
| |
| [Alex] | Дата: Вторник, 24.04.2007, 22:16 | Сообщение # 8 |
|
мастер
Группа: Участники
Сообщений: 227
Статус: Offline
| хх,звучит убедительно
|
| |
| |
| [Lio] | Дата: Среда, 25.04.2007, 13:51 | Сообщение # 9 |
|
d-[]ak
Группа: Администраторы
Сообщений: 357
Статус: Offline
| Алгоритм 3. Сортировка Шейкером.
Когда данные сортируются не в оперативной памяти, а на жестком диске, особенно если ключ связан с большим объемом дополнительной информации, то количество перемещений элементов существенно влияет на время работы. Этот алгоритм уменьшает количество таких перемещений, действуя следующим образом: за один проход из всех элементов выбирается минимальный и максимальный. Потом минимальный элемент помещается в начало массива, а максимальный, соответственно, в конец. Далее алгоритм выполняется для остальных данных. Таким образом, за каждый проход два элемента помещаются на свои места, а значит, понадобится N/2 проходов, где N - количество элементов. Реализация данного алгоритма выглядит так:
| Quote | Program ShakerSort;
Var A : array[1..1000] of integer;
N,i,j,p : integer;
Min, Max : integer;
Begin
{Определение размера массива A - N) и его заполнение}
…
{сортировка данных}
for i:=1 to n div 2 do
begin
if A[i]>A[i+1] then
begin
Min:=i+1;
Max:=i;
end
else
begin
Min:=i;
Max:=i+1;
end;
for j:=i+2 to n-i+1 do
if A[j]>A[Max] then
Max:=j
else
if A[j] Min:=j;
{Обмен элементов}
P:=A[i];
A[i]:=A[min];
A[min]:=P;
if max=i then
max:=min;
P:=A[N-i+1];
A[N-i+1]:=A[max];
A[max]:=P;
end;
{Вывод отсортированного массива A}
…
End. |
Рассмотрев эти методы, сделаем определенные выводы. Их объединяет не только то, что они сортируют данные, но также и время их работы. В каждом из алгоритмов присутствуют вложенные циклы, время выполнения которых зависит от размера входных данных. Значит, общее время выполнения программ есть O(n2) (константа, умноженная на n2). Следует отметить, что первые два алгоритма используют также O(n2) перестановок, в то время как третий использует их O(n). Отсюда следует, что метод Шейкера является более выгодным для сортировки данных на внешних носителях информации. Если вы думаете, что бравые «алгоритмщики» остановились на достигнутом, то вы ошибаетесь. Видите ли, временная оценка O(n2) показалась им слишком громоздкой, и они, жадины такие, решили еще потратить свое время, чтобы впоследствии сэкономить наше. Итак, давайте теперь рассмотрим более быстрые алгоритмы.
$$$ для web-мастеров
|
| |
| |
| DaRve1L | Дата: Суббота, 26.05.2007, 00:24 | Сообщение # 10 |
 участник
Группа: Участники
Сообщений: 30
Статус: Offline
| ОгО лио и тебе не впадло было это все писать или скопировал ану колись! 
Не неси бре а-то полу4ишь с КОЛЬТА В ХЕД
|
| |
| |
| [Lio] | Дата: Суббота, 26.05.2007, 09:54 | Сообщение # 11 |
|
d-[]ak
Группа: Администраторы
Сообщений: 357
Статус: Offline
| DaRve1L, скопировал , но эти методы....э... обще признаны
пиши по теме лутше
$$$ для web-мастеров
|
| |
| |
| DaRve1L | Дата: Воскресенье, 27.05.2007, 23:49 | Сообщение # 12 |
|
участник
Группа: Участники
Сообщений: 30
Статус: Offline
| А за4ем те шпоры!!!!?
Не неси бре а-то полу4ишь с КОЛЬТА В ХЕД
|
| |
| |
| [Lio] | Дата: Понедельник, 28.05.2007, 13:56 | Сообщение # 13 |
|
d-[]ak
Группа: Администраторы
Сообщений: 357
Статус: Offline
| DaRve1L, не нопял
$$$ для web-мастеров
|
| |
| |
| antid | Дата: Понедельник, 11.06.2007, 00:25 | Сообщение # 14 |
 специалист
Группа: Клан D-N
Сообщений: 82
Статус: Offline
| LIO я тут одного не пойму: зачем ты эти шпоры выкладываешь?? в паскале системно qsort валяется:))
предлагаю вот что: у кого проблемы, вопросы насчет паскаля, пусть задает, а мы их решим. :))
а тупо выкладывать алгоритмы бесполезно: никто их не будет знать, все будут тупо зубрить
|
| |
| |
| [Lio] | Дата: Понедельник, 11.06.2007, 12:30 | Сообщение # 15 |
|
d-[]ak
Группа: Администраторы
Сообщений: 357
Статус: Offline
| antid, вообще логично
но надо же было выложить что-нибудь в этот раздел? 
$$$ для web-мастеров
|
| |
| |
| |
