ІНШІ МЕТОДИ СОРТУВАННЯ

Для настільки ж тривалого опису інших методів сортування просто не вистачить місця Тому ми обмежимося короткими коментарями з приводу їх дії Повні описи методів сортування можна знайти в багатьох книгах, присвячених алгоритмам для ЕОМ Особливо рекомендуємо книгу 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)&gt=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 SahiFundamentals of  Data Structures, випущеної видавництвом Pitman в Лондоні в 1977 році, а хороша реалізація на Бейсике наводиться в книзі R M JonesIntroduction  to  Computer  Applications  Using  BASIC, випущеної видавництвом Allyn and Bacon (США) в 1981 році

Джерело: Уолш Б Програмування на Бейсике: Пер з англ М: Радіо і звязок, 1988 336 с: ил

Схожі статті:


Сподобалася стаття? Ви можете залишити відгук або підписатися на RSS , щоб автоматично отримувати інформацію про нові статтях.

Коментарів поки що немає.

Ваш отзыв

Поділ на параграфи відбувається автоматично, адреса електронної пошти ніколи не буде опублікований, допустимий HTML: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

*

*