Форум программистов, компьютерный форум, киберфорум
WH
Войти
Регистрация
Восстановить пароль
Оценить эту запись

Быстрая сортировка

Запись от WH размещена 03.11.2020 в 10:10
Обновил(-а) WH 03.11.2020 в 12:45

Программа быстрой сортировки:

Fortran
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
! qsort_reals.f90 --
!
!     Example belonging to "Modern Fortran in Practice" by Arjen Markus
!
!     This work is licensed under the Creative Commons Attribution 3.0 Unported License.
!     To view a copy of this license, visit http://creativecommons.org/licenses/by/3.0/
!     or send a letter to:
!     Creative Commons, 444 Castro Street, Suite 900, Mountain View, California, 94041, USA.
!
!     Compact implementation of the QuickSort algorithm
!
!     Note:
!     Because the function uses Fortran 90 features, its interface should be made
!     explicit when using it in an actual program. This is easiest via a module.
!
module qsort_functions
    implicit none
 contains
recursive function qsort_reals( data ) result( sorted )
    real, dimension(:), intent(in) :: data
    real, dimension(1:size(data))  :: sorted
 
    if ( size(data) > 1 ) then
        sorted = &
            (/ qsort_reals( pack( data(2:), data(2:) > data(1) ) ), &
               data(1),                                             &
               qsort_reals( pack( data(2:), data(2:) <= data(1) ) ) /)
    else
        sorted = data
    endif
end function qsort_reals
end module qsort_functions


Вызов осуществляется:

Fortran
1
b = qsort_reals (a)
где
а - исходный массив вещественных чисел
b - отсортированный массив

При этом в вызывающей программе нужно не забыть указать возможность использования модуля:

Fortran
1
use qsort_functions
В модуле через рекурсивную функцию реализован алгоритм быстрой сортировки. Тестирование показало весьма неплохой результат, массив из 1 млн. вещественных чисел был отсортирован, на очень старом для нашего времени ПК, за 1 секунду.

Ниже 2 пункта которые рекомендуется проверить перед использованием, поскольку это не авторская рекомендация:
1. По умолчанию реализована сортировка на убывание. Если нужна сортировка на возрастание в строках 25 и 27 меняем знаки сравнения на противоположные.
2. Эксперимент на небольшом массиве показал, что массивы можно совместить, т.е. указать:
Fortran
1
a = qsort_reals (a)
Источник программы и лицензия на использование указаны в преамбуле к программе (являющейся ее неотъемлемой частью!), там же указана рекомендация по использованию интерфейса.
Размещено в Без категории
Просмотров 390 Комментарии 0
Всего комментариев 0
Комментарии
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2020, vBulletin Solutions, Inc.