Технический форум купить трафик таргетированный
Вернуться   Технический форум > Программирование > Форум программистов > Помощь студентам


Ответ
 
Опции темы Опции просмотра
Старый 09.05.2012, 16:22   #1 (permalink)
Vladimir_S
Специалист
 
Аватар для Vladimir_S
 
Регистрация: 27.08.2008
Адрес: Санкт-Петербург
Сообщений: 24,135
Сказал(а) спасибо: 149
Поблагодарили 300 раз(а) в 102 сообщениях
Репутация: 64735
По умолчанию Об алгоритмах упорядочения одномерных массивов

Часто в учебных задачах, с которыми обращаются на наш форум, требуется провести упорядочение массивов, т.е. расположить элементы исходного массива в порядке возрастания или убывания. Существует множество методов (алгоритмов) решения такой задачи: лет 20-30 назад их усиленно изобретали, стараясь найти самый "оптимальный", быстрый и т.п. Сегодня, с учетом скоростей работы современных компьютеров, подобная деятельность IMHO теряет смысл, и мне представляется разумным обучать студентов владению хотя бы одним методом, лучше всего "пузырька", как самым наглядным и простым, но нет - преподы продолжают мучить детей указулями типа "использовать метод вставки". Ну что же, разберемся с основными.

Метод "пузырька"

Замечаю, что этот простейший и изящнейший метод у многих начинающих программистов вызывает трудности в понимании и даже вопросы типа "а зачем двойной цикл - массив-то одномерный?!" и т.п. Некоторые, впрочем, предпочитают бездумно откуда-нибудь перекатать фрагмент программы, при этом, как правило, путаются в двух переменных цикла, что, разумеется, "не есть хорошо". Между тем, если разобраться, то каждый легко сможет написать это самое упорядочение просто "из головы".
Сделаем разбор примера. Язык - Паскаль (что, впрочем, большого значения не имеет).
Пусть требуется упорядочить по возрастанию следующий массив A:
4 3 5 2 1
Число элементов (5) обозначим n.
Программный код:
Код:
for i:=1 to n-1 do
 for j:=1 to n-i do
  if A[j]>A[j+1] then
   begin
    D:=A[j];
    A[j]:=A[j+1];
    A[j+1]:=D;
   end;
Полагаю, что смысл тела цикла ясен: если предыдущий элемент больше последующего, то они меняются местами. При этом обратите внимание: переменная внешнего цикла i как индекс массива не используется, она - лишь счетчик. А вот чтобы совсем было ясно, проследим последовательность выполнения программы:

Итак, напомню, исходное расположение:

4 3 5 2 1

Первое прохождение внутреннего цикла (i=1, j меняется от одного до 5-1=4):
3 4 5 2 1 (обменялись позициями 1 и 2 элементы)
3 4 5 2 1 (второй и третий стоят правильно)
3 4 2 5 1 (обменялись позициями 3 и 4 элементы)
3 4 2 1 5 (обменялись позициями 4 и 5 элементы)

Легко понять, что где бы ни находился максимальный элемент, после окончания первого внутреннего цикла он окажется последним, то есть там, где ему и место. Больше эта позиция трогаться не будет, ибо следующий внутренний цикл пойдет от 1 до 5-2=3:
3 4 2 1 5 (первый и второй стоят правильно)
3 2 4 1 5 (обменялись позициями 2 и 3 элементы)
3 2 1 4 5 (обменялись позициями 3 и 4 элементы)

Вот и второй по величине элемент (4) встал на место. Следующий цикл по j - от 1 до 5-3=2:
2 3 1 4 5 (обменялись позициями 1 и 2 элементы)
2 1 3 4 5 (обменялись позициями 2 и 3 элементы)

И, наконец, последнее прохождение по j - от 1 до 1:
1 2 3 4 5 (обменялись позициями 1 и 2 элементы)

Всё! Как видите, массив упорядочен, задача решена.
Почему это всё называется "метод пузырька"? А представьте себе наш массив в виде узкого вертикального сосуда с жидкостью, где младшие индексы - это "дно", а старшие - "верх". Тогда перемещение элемента вдоль массива подобно всплыванию пузырька воздуха в сосуде. Просто наглядная аналогия.
Естественно, если надо расположить элементы не в порядке возрастания, а в порядке убывания, то следует всего лишь поменять знак неравенства в условном операторе.

Метод вставки

Он значительно уступает "пузырьку" в простоте и наглядности и, кроме того, требует применения одного искусственного приема - добавления лишнего вспомогательного элемента (можно и без этого, но тогда программа становится громоздкой). Суть: пусть первый из n элементов уже "упорядочен", т.е. на первом месте стоит наименьший элемент. Тогда далее начиная со второго путем, как и в "пузырьке", цепочечной попарной перестановки, "гоним" справа налево элементы - сначала второй, потом третий и так до n-го. Но как выполнить условие, чтобы на первом месте стоял наименьший элемент? А вот для этого "спереди" к массиву и прицепляется лишний "нулевой" по счету элемент, заведомо меньший всех остальных. Код:
Код:
A[0]:=0; {Это если массив неотрицательный}
For i:=2 to N do
 begin
  j:=i;
  while A[j]<A[j-1] do
   begin
    c:=A[j];
    A[j]:=A[j-1];
    A[j-1]:=c;
    Dec(j);
   end;
 end;
Метод сортировки выбором

Тут всё совсем просто - ищем наименьший элемент, меняем местами с первым, потом ищем наименьший из оставшихся, меняем его местами со вторым и т.д. до предпоследнего, который, если надо, меняем местами с последним. Код:
Код:
For i:=1 to N-1 do
 begin
  d:=i;
  For j:=i+1 to N do
   If A[j]<A[d] then d:=j;
  c:=A[i];
  A[i]:=A[d];
  A[d]:=c;
 end;
Метод Шелла

Вот тут - внимание! МЕТОД ШЕЛЛА НЕ РЕШАЕТ ЗАДАЧУ ОКОНЧАТЕЛЬНО, он лишь осуществляет предварительную "грубую" сортировку, а окончательно это дело доводится методом вставок или пузырька. Суть: вначале обмениваются местами по возрастанию элементы, отстоящие на n/2 позиций (т.е. если n=6, то 1 с 4, 2 с 5 и 3 с 6), затем "расстояние" делится на 2 (с округлением, естественно) и процедура повторяется, и так продолжается до тех пор, пока "шаг" не станет равным 1. Код:
Код:
d:=N;
Repeat
 d:=d div 2;
 for i:=1 to N-d do
  if A[i]>A[i+d] then
   begin
    c:=A[i];
    A[i]:=A[i+d];
    A[i+d]:=c;
   end;
Until d=1;
Метод быстрой сортировки (алгоритм Хоара)

Считается одним из самых быстрых и эффективных. В то же время, весьма ненагляден и сложен для понимания. Несколько напоминает алгоритм Шелла, но, в отличие от последнего, доводит сортировку до конца. Далее я буду в основном заимствовать материал из Википедии, как в плане описания, так и в листинге программы.
Шаги алгоритма таковы:
  1. Выбираем в массиве некоторый элемент, который будем называть опорным элементом. С точки зрения корректности алгоритма выбор опорного элемента безразличен.
  2. Операция разделения массива: реорганизуем массив таким образом, чтобы все элементы со значением меньшим или равным опорному элементу, оказались слева от него, а все элементы, превышающие по значению опорный — справа от него. Обычный алгоритм операции:
    1. Два индекса — l и r, приравниваются к минимальному и максимальному индексу разделяемого массива, соответственно.
    2. Вычисляется индекс опорного элемента m.
    3. Индекс l последовательно увеличивается до тех пор, пока l-й элемент не окажется больше либо равен опорному.
    4. Индекс r последовательно уменьшается до тех пор, пока r-й элемент не окажется меньше либо равен опорному.
    5. Если r = l — найдена середина массива — операция разделения закончена, оба индекса указывают на опорный элемент.
    6. Если l < r — найденную пару элементов нужно обменять местами и продолжить операцию разделения с тех значений l и r, которые были достигнуты. Следует учесть, что если какая-либо граница (l или r) дошла до опорного элемента, то при обмене значение m изменяется на r-й или l-й элемент соответственно, изменяется именно индекс опорного элемента и алгоритм продолжает свое выполнение.
  3. Рекурсивно упорядочиваем подмассивы, лежащие слева и справа от опорного элемента.
  4. Базой рекурсии являются наборы, состоящие из одного или двух элементов. Первый возвращается в исходном виде, во втором, при необходимости, сортировка сводится к перестановке двух элементов. Все такие отрезки уже упорядочены в процессе разделения.
Поскольку в каждой итерации (на каждом следующем уровне рекурсии) длина обрабатываемого отрезка массива уменьшается, по меньшей мере, на единицу, терминальная ветвь рекурсии будет достигнута обязательно и обработка гарантированно завершится.


Реализация алгоритма может быть выполнена как с использованием рекурсии, так и без таковой. В последнем случае программа существенно удлиняется.

Приведу листинг программы упорядочения целочисленного массива по возрастанию с использованием рекурсивной процедуры:
Код:
Uses CRT;
Const
 N=20;
Type
 Vector=Array[1..N] of Byte;
Const
 M:Vector=(18,17,36,37,15,26,11,9,18,49,13,10,28,36,10,2,25,41,40,21);
Var
 A:Vector;
 k:Byte;

Procedure Sort(var Ar:Vector; low,high:byte);
var
 i,j,m,D:byte;
begin
 i:=low;
 j:=high;
 m:=Ar[(i+j) div 2];
 repeat
  while Ar[i]<m do Inc(i);
  while Ar[j]>m do Dec(j);
  if i<=j then
   begin
    D:=Ar[i];
    Ar[i]:=Ar[j];
    Ar[j]:=D;
    Inc(i);
    Dec(j);
   end;
 until i>j;
 For k:=1 to N do
  Write(Ar[k]:4);
 if low<j then Sort(Ar, low, j);
 if i<high then Sort(Ar, i, high);
end;

Begin
 ClrScr;
 A:=M;
 Writeln('HOARE SORT');
 Writeln;
 Writeln('Initial array:');
 For k:=1 to N do
  Write(A[k]:4);
 Writeln;
 Sort(A, 1, N);
 ReadKey
End.
Метод "ХХХХ"

Наткнулся тут давеча еще на один метод. Простой и глупый. Поскольку я не знаю, как он именуется, и именуется ли как-нибудь вообще, назовем его "метод ХХХХ".
Суть: вводим булеву переменную-флажок b и начинаем многократное прохождение массива от начала до конца, меняя местами соседние "неупорядоченные" элементы, и так делаем до тех пор, пока таких "неупорядоченных" пар не останется, т.е. заданное перед очередным прохождением значение флажка останется неизменным (если же встретится хоть одна "неупорядоченная" пара, то флажок переворачивается). Код:
Код:
Repeat
 b:=true;
 for i:=1 to N-1 do
  if A[i]>A[i+1] then
   begin
    D:=A[i];
    A[i]:=A[i+1];
    A[i+1]:=D;
    b:=false;
   end;
Until b;
__________
Ниже приведены скриншоты упорядочения одного и того же массива всеми рассмотренными методами. Еще раз обращаю внимание на "незавершенность" метода Шелла.
Миниатюры
shell01.jpg   shell02.jpg   shell03.jpg   shell04.jpg   hoare.jpg  

xxxx.jpg  
__________________
With Mozilla Firefox - straight to communism!
Vladimir_S вне форума   Ответить с цитированием

Старый 09.05.2012, 16:22
Helpmaster
Member
 
Аватар для Helpmaster
 
Регистрация: 08.03.2016
Сообщений: 0

Моя задача - дать вам знать о том, что на форуме есть похожие посты

Обработка двумерных массивов
Среднее арифметическое двух массивов
Обработка массивов
Обработка одномерных и двумерных массивов

Ads

Яндекс

Member
 
Регистрация: 31.10.2006
Сообщений: 40200
Записей в дневнике: 0
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Репутация: 55070
Ответ

Опции темы
Опции просмотра

Ваши права в разделе
Вы не можете создавать новые темы
Вы не можете отвечать в темах
Вы не можете прикреплять вложения
Вы не можете редактировать свои сообщения

BB коды Вкл.
Смайлы Вкл.
[IMG] код Выкл.
HTML код Выкл.
Trackbacks are Вкл.
Pingbacks are Вкл.
Refbacks are Выкл.




Часовой пояс GMT +4, время: 09:12.


Powered by vBulletin® Version 6.2.5.
Copyright ©2000 - 2014, Jelsoft Enterprises Ltd.