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

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

                  │ Обмен(A[i];A[nom]);

По сравнению с методом пузырька, в котором перестановки призводятся при каждом сравнении, оптимизированный метод  выбора  дает  значительный выигрыш времени, так как удается обойтись (да и то не при каждом сравнении) только одним присваиванием вместо трех.

5. Метод сдвига

В этом методе выполняется упорядочение массива, начиная с его самых первых элементов (A[1] и A[2]). Затем в область  упорядочения включается A[3], A[4] и так далее, до полного исчерпания массива.

Пусть элементы A[1]..A[k] уже  упорядочены.  Тогда  элемент  A[k+1] ставится на надлежащее место последовательными перестановками  с элементами A[k], A[k-1].., т.е., все элементы, большие A[k+1]  сдвигаются вниз на одну позицию.  

Описание алгоритма:

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

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

                 │ t=A[i]

                 │ j=i-1

                 │ Пока A[j]>t и j>0 выполнять

                 │  │ A[j+1]=A[j]

                 │  │ j=j-1

                 │ A[j+1]=t

6. Метод подсчета (вспомогательного массива)

В этом методе используется,  помимо  обрабатываемого  массива,  еще один массив такого же размера. Кроме того, предполагается, что  в исходном массиве нет одинаковых элементов. Затраты оперативной  памяти оправдываются простотой выполняемых действий. Алгоритм основан на использовании очевидного

                                                                                                                                              4

факта: элемент, стоящий на k-м месте в  уже упорядоченном массиве, по величине превосходит (k-1) остальных элементов.

Описание алгоритма:

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

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

                 │ k=0

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

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

                 │ B[k+1]=A[i]

Примечание: Если по сути задачи требуется сохранение  результата  в массиве А, после выполнения сортировки достаточно выполнить присваивание A:=B; (в Турбо-Паскале допускается присваивание массивов  одинакового типа).

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

В этом методе объединены черты  метода  сдвига  и  метода вспомогательного массива. Элементы исходного массива берутся по очереди  и записываются во вспомогательный массив, но так, чтобы  получился упорядоченный набор данных. Вначале элемент A[1] записывают первым в массиве В, т. е. B[1]=A[1]. Далее элемент A[2] сравнивается с В[1]. Если  в результате сравнения оказалось, что A[2]<B[1], то элемент B[1] передвигается на одну позицию дальше, а элемент A[2] занимает его место в массиве В. Теперь в массиве В размещены два элемента B[1]  и  B[2],  образующих последовательность, упорядоченную по возрастанию значений.

На каждом i-м просмотре процесса сортировки очередной  элемент A[i] сравнивается поочередно со всеми элементами, записанными ранее  в массив В (их i-1 штук), начиная с B[1].  При  обнаружении  B[j],  большего  чем A[i], элементы B[j], B[j+1], B[j+1], ... , B[i-1] передвигаются  на одну позицию, освобождая место для элемента A[i], который занимает  j-ю позицию (это означает, что выполняется присваивание B[j]=A[i]).