09.05.2012, 16:22 | #1 (permalink) |
Специалист
Регистрация: 27.08.2008
Адрес: Санкт-Петербург
Сообщений: 27,807
Сказал(а) спасибо: 340
Поблагодарили 583 раз(а) в 208 сообщениях
Репутация: 113184
|
Об алгоритмах упорядочения одномерных массивов
Метод "пузырька" Замечаю, что этот простейший и изящнейший метод у многих начинающих программистов вызывает трудности в понимании и даже вопросы типа "а зачем двойной цикл - массив-то одномерный?!" и т.п. Некоторые, впрочем, предпочитают бездумно откуда-нибудь перекатать фрагмент программы, при этом, как правило, путаются в двух переменных цикла, что, разумеется, "не есть хорошо". Между тем, если разобраться, то каждый легко сможет написать это самое упорядочение просто "из головы". Сделаем разбор примера. Язык - Паскаль (что, впрочем, большого значения не имеет). Пусть требуется упорядочить по возрастанию следующий массив 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; Итак, напомню, исходное расположение: 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; Считается одним из самых быстрых и эффективных. В то же время, весьма ненагляден и сложен для понимания. Несколько напоминает алгоритм Шелла, но, в отличие от последнего, доводит сортировку до конца. Далее я буду в основном заимствовать материал из Википедии, как в плане описания, так и в листинге программы. Шаги алгоритма таковы:
Реализация алгоритма может быть выполнена как с использованием рекурсии, так и без таковой. В последнем случае программа существенно удлиняется. Приведу листинг программы упорядочения целочисленного массива по возрастанию с использованием рекурсивной процедуры: Код:
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; Ниже приведены скриншоты упорядочения одного и того же массива всеми рассмотренными методами. Еще раз обращаю внимание на "незавершенность" метода Шелла. |
09.05.2012, 16:22 | |
Helpmaster
Member
Регистрация: 08.03.2016
Сообщений: 0
|
Моя задача - дать вам знать о том, что на форуме есть похожие посты Обработка двумерных массивов Среднее арифметическое двух массивов Обработка массивов Обработка одномерных и двумерных массивов |
Ads | |
Member
Регистрация: 31.10.2006
Сообщений: 40200
Записей в дневнике: 0
Сказал(а) спасибо: 0
Поблагодарили 0 раз(а) в 0 сообщениях
Репутация: 55070
|
|
|