Изучение и программирование алгоритмов сортировки. Сортировка данных. Основные понятия. Метод обмена соседних элементов (метод "пузырька"), страница 2

2.  Метод "четных и нечетных транспозиций"

Этот метод является разновидностью метода обмена. Сортировка выполняется следующим образом. Массив просматривается многократно,  причем на первом просмотре сравниваются A[i] с A[i+1] для всех нечетных i. На втором просмотре сравниваются A[i] с A[i+1] для всех четных i.  Каждый раз, когда A[i]>A[i+1], выполняется обмен этих элементов. Просмотры продолжаются до тех пор, пока массив не будет упорядочен. Очевидно, в таком случае не будет выполнен ни один обмен элементов. Описание алгоритма:              Заполнение массива              Повторять

             │ перестановка=0

             │ i=1

             │ Пока i<N выполнять

             │ │ Если A[i]>A[i+1] то

             │ │  │ Переставить(A[i],A[i+1])

             │ │  │ перестановка=1

             │ │ i=i+2

             │ i=2

             │ Пока i<N выполнять

             │ │ Если A[i]>A[i+1] то

             │ │  │ Переставить(A[i],A[i+1]);

             │ │  │ перестановка=1;

             │ │ i=i+2;

             до получения перестановка=0;

3.  Метод выбора (метод поиска минимума)

Последовательными сравнениями ищется  наименьший  элемент  массива, причем в процессе поиска запоминается индекс текущего наименьшего числа.

После того как просмотрен последний элемент, можно поменять  местами 1-й элемент с наименьшим, т.к. его индекс известен. Затем эти  действия повторяются, начиная со 2-го элемента (1-й уже стоит на  правильном месте), затем с 3-го элемента, и т.д.

В случае массива из 5 чисел получим, например:

исходный массив:                    50 40 30 10 20

индекс наименьшего элемента: [4]     └────────────  область просмотра массив после перестановки:          10 40 30 50 20

индекс наименьшего элемента: [5]        └─────────  область просмотра массив после перестановки:          10 20 30 50 40

индекс наименьшего элемента: [3]           └──────  область просмотра

(в данном случае перестановка не нужна, т.к. индекс совпадает с началом области просмотра)

                                    10 20 30 50 40

индекс наименьшего числа:  [5]                └───  область просмотра массив после перестановки:          10 20 30 40 50

Таким образом, перестановка массива завершена. Описание алгоритма:                   Заполнение массива

                  Для i=1 до N-1 выполнять

                  │  Amin=A(i)

                  │  nom=i

                  │  Для j=i+1 до N выполнять    

                  │   │ Если A[j]<Amin то         

                  │   │  │ Amin=A[j]               

                  │   │  │ nom=j                   

                  │  Переставить(A[i];A[nom])    

4. Оптимизированный метод выбора

Формулировка метода выбора является наиболее естественной,  так как содержит стандартный фрагмент поиска минимального элемента. Но его можно упростить, если заметить, что  для  последующей  перестановке  элементов важна не величина минимального элемента, а его номер в  массиве. Поэтому величину Amin можно не учитывать. 

Тогда получаем следующий вариант алгоритма выбора:

                  Заполнение массива

                  Для i=1 до N-1 выполнять

                  │ nom=i

                  │ Для j=i+1 до N выполнять