Главная » Basic » ДРУГИЕ МЕТОДЫ СОРТИРОВКИ

0

Для столь же длительного описания других методов сортировки просто не хватит места. Поэтому мы ограничимся краткими комментариями по   поводу  их    действия. Полные   описания методов сортировки можно найти во многих книгах, посвященных  алгоритмам  для ЭВМ. Особо рекомендуем книгу Peter Naur Concise Survey of Computer Methods, выпущенную издательством Studentliteratur в Лунде (Швеция)  в 1974 году.

Сортировка Шелла быстрее метода пузырька и  требует выполнения Nlog2(N) операций, где N — число сортируемых элементов данных. Она  похожа на  метод  пузырька, но,  в  отличие    от  него, начинает  сравнивать не смежные, а далеко отстоящие друг от друга значения (примерно на N/2) и сортирует все эти значения, а затем уменьшает расстояние между сравниваемыми значениями.  На последнем проходе расстояние между ними равно 1 и поэтому фактически этот проход выполняется по методу пузырька. Такая сортировка  предложена Д. А. Шеллом и  основана на процедуре Дж. Бутройда, написанной на языке Алгол 60.

Этой структограмме отвечает следующий фрагмент программы: 1000   REM СОРТИРОВКА ШЕЛЛА

l010 REM ПРЕДПОЛАГАЕТСЯ, ЧТО В МАССИВЕ А$(1)…..A$(N)

1020   REM СОДЕРЖАТСЯ СТРОКИ СИМВОЛОВ. КОТОРЫЕ

1030   RЕМ НАДО ОТСОРТИРОВАТЬ ПО АЛФАВИТУ

1040   D=N/2

1050        REM

1060         IF D=0 THEN 1210

1070             K=N-D

1080             FOR J=1 TO К

1090                 L=J

1100                      H=L+D

1110                      S=0

1120                      IF A$(L)>=A$(H) THEN 1180

1130                      T$=A$(L)

1140                      A$(L)=A$(H)

1150                      A$(H)=T$

1160                      L=L-D

1170                      S=1

1180                  IF L=1 AND S=1 THEN 1100

1190            NEXT J

1195            D=INT(D/2)

1200       GOTO 1060

1210        REM ВЫХОД С ОТСОРТИРОВАННЫМ МАССИВОМ

Если Вы хотите сравнить метод пузырька и  сортировку Шелла, то примените   их для сортировки нескольких наборов данных, варьируя число сортируемых значений от 10 до 100. Вы обнаружите, что сортировка  Шелла гораздо быстрее при большем числе элементов. Исполнение приведенной выше программы на одной из ЭВМ показало, что сортировка Шелла отсортировала 100 элементов в пять раз быстрее, чем сортировка по методу пузырька.

Среди многих других алгоритмов сортировки одним из лучших является  метод быстрой сортировки, придуманный Ч. А. Р. Хоаром. Хотя в наихудшем случае время его работы пропорционально N2 (как у метода пузырька) , среднее время работы меньше Nlog2N (как у сортировки Шелла). Однако для реализации   метода  быстрой  сортировки   требуется  дополнительная рабочая  область  в   памяти. Полный анализ этого  алгоритма содержится в   книге Е.  Horowitz, S.  Sahi  Fundamentals of  Data Structures, выпущенной издательством  Pitman в  Лондоне в  1977  году, а  хорошая реализация  на Бейсике приводится    в   книге R.  M.  Jones  Introduction  to  Computer  Applications  Using  BASIC, выпущенной издательством Allyn and Bacon (США) в 1981 году.

Источник: Уолш Б.    Программирование на Бейсике: Пер. с англ. М.: Радио и связь, 1988. 336 с: ил.

По теме:

  • Комментарии