Отправляет email-рассылки с помощью сервиса Sendsay

Решение Вами Предложенных Задач На Языке PASCAL. Алгоритмы.

Подписаться Бесплатная новостная рассылка Подписчиков 27 RSS
  Апрель 2004   →
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30


За последние 60 дней ни разу не выходила


Сайт рассылки: http://openlab.org.ua/pascal_subscribe.php
Открыта: 21-04-2004

Автор
Денис Владимирович

Статистика

27 подписчиков
0 за неделю
←   Все выпуски   →

Решение Вами Предложенных Задач На Языке PASCAL. Алгоритмы.


Информационный Канал Subscribe.Ru

Решение Предложенных Вами Задач На Языке PASCAL.
Описание Работы Алгоритмов.

Здравствуйте Дорогие Подписчики!
Вот и настал момент выхода первого номера этой рассылки!
Изначально, как и полагается, я расскажу Вам о правилах данной рассылки.
Итак, рассылка выходит с переодичностью раз в неделю или чуть реже (т.к. на начальном этапе, чувствую материала будет нехватать).
Материал будет составляться по Вашим просьбам и заявкам. Каждая рассылка будет разбита на 3 части.
Первая часть -- это описание алгоритма(либо другого Вашего вопроса) и принципа его работы.
Вторая часть -- будет "первый форум", где прямо в рассылке мы будем обсуждать аспекты решения тех или иных задач. Причем уровень сложности здесь роли не играет. Решать будем как задачи для самых, что ни на есть начинающих пользователей до крупных и сложнейших олимпиадных задач. Так что не стесняйтесь присылайте Ваши задачи сюда: pascal123@mail.ru с темой сообщения "Задача" (либо "Zadacha").
Здесь же будут публиковаться ссылки на решенные задачи (предложенные опять-таки Вами!).
Каждый желающий сможет как опубликовать любую свою задачу, так и решить ту, которую он посчитает для себя нужной или же просто интересной!
Третья часть-- второй форум, где будут обсуждаться исключительно вопросы программирования на языке PASCAL/DELPHI.

Основные e-mail адреса рассылки
Все условия Ваших задач присылать сюда: pascal123@mail.ru (тема "Zadacha", либо "Задача")
Решенные задачи, либо идеи по решению оных сюда: pascal123@mail.ru (тема "Reshenie", либо "Решение")
Вопросы/ответы по Pascal/Delphi сюда: pascal123@mail.ru (тема "Vorpos", либо "Вопрос")
Вопрос лично администратору рассылки присылайте по адресу: pascal123@mail.ru (тема "Avtoru", либо "Автору")

Алгоритм сортировки по методу Шелла
Алгоритм сортировки методом Шелла заключается в сравнении ключей на некотором расстоянии d. Причем на первом шаге расстояние равно длине сортируемого массива пополам. Сразу приведу пример кода(готовая процедура для сортировки массива):

procedure ShellSort(var arr : array of integer);
var
  d, i, t, N : integer;
  k          : boolean;
begin
  N := Length(arr)-1;
  d:= N div 2;
  while d>0 do begin
    k:=true;
    while k do begin
    k:=false;
    for i:=0 to N-d do begin
      if arr[i]>arr[i+d] then begin
        t := arr[i];
        arr[i] := arr[i+d];
        arr[i+d] := t;
        k:=true;
      end;
    end;
    end;
  d:=d div 2;
  end;
end;

Как мы можем видеть из кода, изначально мы получаем расстояние d (длина_массива деленная на 2, причем если получается дробное число, мы отсекаем целую часть числа). Далее мы запускаем цикл, который работает пока расстояние d>0, отсюда мы можем сделать выводы, что последнее расстояние при котором работает цикл d=1.
Далее следует работа внутреннего цикла, который проверяет были ли сортировки на данном этапе или нет. Причем, если цикл определяет, что сортировки на данном этапе ("данный этап" -- это когда d=n, где n это некоторое число) были, то цикл не прекращает свою работу и делает следующее.
Создается внутренний цикл for, который работает от 0-вого элемента до N-d, где N - размер сортируемого массива. Далее следует оператор условия if, который проверяет левую(arr[i]) и правую(arr[i+d]) границы массива, если цикл "видит" ситуацию, где левая граница больше правой, а так быть не может, т.к. в отсортированном массиве предыдущее число меньше, либо равно числу идущему после него.
Если видим, что левое число все-таки больше правого, значит числа стоят не на своем месте, меняем их местами. И в переменную k присваиваем значение true, т.к. сортировки были.
Возможно будут ещё подобные сортировки, мы пока что этого ещё не знаем... короче говоря, на данном этапе, в цикле while k... сведется все к тому, что сортировок на данном этапе делать больше будет не нужно и переменная k останется равной значению false и цикл прекратит свою работу. Но прекратить работу это не значит прекратить работу всей процедуры, далее продолжает свою работу цикл while d>0... который делит переменную расстояния d ещё пополам и начинается заново вся работа, только уже с d:=d div 2.
И так далее, пока d не станет равной еденице и сортировать будет нечего! Это и будет последним шагом в сортировке методом Шелла.

Вот так и происходит сортировка по методу Шелла!
Более быстрые результаты, по сравнению с сортировкой методом пузырька, достигаются за счет того, что выявленные числа не на своем месте обнаруживаются быстрее и сразу же расстанавливаются по своим местам.

Качественный порядок сортировки по методу Шелла: O(N^2).
Среднее число сравнений, определенное эмперическим путем: log2(N)^2*N

Ну вот и все чудеса на сегодня!
Если есть какие-либо комментарии, пожелания, вопросы по данному методу обязательно пишите на: pascal123@mail.ru

И на последок случайный анекдот!
- Мама, мама! Вовка меня всю обрызгал...
- А ты его тоже обрызгай.
- Ну, мама, как? Я же девочка!

http://OpenLab.org.ua © 2004

http://subscribe.ru/
E-mail: ask@subscribe.ru 		Отписаться
Убрать рекламу

В избранное