учебая практика маи фортран. учёбая практика_уэзо Ругамас. Сортировка данных перемешиванием (шейкерная)
 Скачать 212.65 Kb.
|
|
МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ Московский авиационный институт (национальный исследовательский университет) Кафедра №201 “ Алгоритмические языки и программирование” “Учёбая практика” Выполнил: студент группы М20-114бки-20 Уэзо Ругамас Давид Улисес Проверил: Преподаватель Кафедры №201 “Алгоритмические языки и программирование” Киктев Сергей Игоревич Тема:” Сортировка данных перемешиванием (шейкерная)” Г. Москва, 2021 г. Содержание: Сортировка перемешиванием (cocktail sort, shaker sort), или шейкерная сортировка – это усовершенствованная разновидность сортировки пузырьком, при которой сортировка производиться в двух направлениях, меняя направление при каждом проходе. Описание алгоритма шейкерной сортировки Проанализировав алгоритм пузырьковой сортировки, можно заметить: если при обходе части массива не было обменов элементов, то эту часть можно исключить, так как она уже отсортирована; при проходе от конца массива к началу минимальное значение сдвигается на первую позицию, при этом максимальный элемент перемещается только на один индекс вправо. Исходя из приведенных идей, модифицируем сортировку пузырьком следующим образом: на каждой итерации, фиксируем границы части массива в которой происходит обмен; массив обходиться поочередно от начала массива к концу и от конца к началу; При этом минимальный элемент перемещается в начало массива, а максимальный - в конец, после этого уменьшается рабочая область массива. Сортировка данных перемешиванием (шейкерная) Шейкерную сортировку часто называют «двунаправленная пузырьковая сортировка», что достаточно точно описывает процесс работы алгоритма. Это действительно альтернативная версия рассмотренного ранее метода. Перестановка элементов в шейкерной сортировке выполняется аналогично пузырьковой сортировке, т. е. два соседних элемента при необходимости меняются местами. Отличие заключается в том, что упорядочение происходит не строго в одном направлении (от меньшего индекса к большему), как в случае пузырьковой сортировки, а вначале от меньшего к большему, затем наоборот. (также известна как сортировка перемешиванием и коктейльная сортировка). Заметим, что сортировка пузырьком работает медленно на тестах, в которых маленькие элементы стоят в конце (их еще называют «черепахами»). Такой элемент на каждом шаге алгоритма будет сдвигаться всего на одну позицию влево. Поэтому будем идти не только слева направо, но и справа налево. Будем поддерживать два указателя begin и end, обозначающих, какой отрезок массива еще не отсортирован. На очередной итерации при достижении end вычитаем из него единицу и движемся справа налево, аналогично, при достижении begin прибавляем единицу и двигаемся слева направо. Асимптотика у алгоритма такая же, как и у сортировки пузырьком, однако реальное время работы лучше. пример сортировки program shakesort implicit none real(4) rand integer(4),allocatable :: A(:) integer N,j,t integer l,r write(*,*)'Enter N' read(*,*) N allocate(A(N)) do j=1,N A(j)=N-j write(*,'(i4)') A(j) enddo write(*,'(8i4)') A write(*,'(3a)') l=1 r=size(a)-1 do while(l < r) do j=l,r,1 if(A(j)>A(j+1)) then t=A(j) A(j)=A(j+1) A(j+1)=t endif end do do j=r,l+1,-1 if(A(j) t=A(j) A(j)=A(j-1) A(j-1)=t endif enddo l=l+1 r=r-1 write(*,'(8i4)') A end do write(*,'(8i4)') A deallocate(A) end program Метод Хоара - Быстрая сортировка Быстрая сортировка представляет собой усовершенствованный метод сортировки, основанный на принципе обмена. Пузырьковая сортировка является самой неэффективной из всех алгоритмов прямой сортировки. Однако усовершенствованный алгоритм является лучшим из известных методом сортировки массивов. Он обладает столь блестящими характеристиками, что его изобретатель Ч. Хоар назвал его быстрой сортировкой. Для достижения наибольшей эффективности желательно производить обмен элементов на больших расстояниях. В массиве выбирается некоторый элемент, называемый разрешающим. Затем он помещается в то место массива, где ему полагается быть после упорядочивания всех элементов. В процессе отыскания подходящего места для разрешающего элемента производятся перестановки элементов так, что слева от них находятся элементы, меньшие разрешающего, и справа — большие (предполагается, что массив сортируется по возрастанию). Тем самым массив разбивается на две части: не отсортированные элементы слева от разрешающего элемента; не отсортированные элементы справа от разрешающего элемента. Чтобы отсортировать эти два меньших подмассива, алгоритм рекурсивно вызывает сам себя. Если требуется сортировать больше одного элемента, то нужно выбрать в массиве разрешающий элемент; переупорядочить массив, помещая элемент на его окончательное место; отсортировать рекурсивно элементы слева от разрешающего; отсортировать рекурсивно элементы справа от разрешающего. Ключевым элементом быстрой сортировки является алгоритм переупорядочения. Выберем некоторый опорный элемент. После этого перекинем все элементы, меньшие его, налево, а большие – направо. Рекурсивно вызовемся от каждой из частей. В итоге получим отсортированный массив, так как каждый элемент меньше опорного стоял раньше каждого большего опорного. Асимптотика: O(nlogn) в среднем и лучшем случае, O(n2). Наихудшая оценка достигается при неудачном выборе опорного элемента. Моя реализация этого алгоритма совершенно стандартна, идем одновременно слева и справа, находим пару элементов, таких, что левый элемент больше опорного, а правый меньше, и меняем их местами. Помимо чистой быстрой сортировки, участвовала в сравнении и сортировка, переходящая при малом количестве элементов на сортировку вставками. Константа подобрана тестированием, а сортировка вставками — наилучшая сортировка, подходящая для этой задачи (хотя не стоит из-за этого думать, что она самая быстрая из квадратичных). Пример module Sort use iso_c_binding implicit none interface subroutine qsort(array,elem_count,elem_size,compare) bind(C,name="qsort") import type(c_ptr),value :: array integer(c_size_t),value :: elem_count integer(c_size_t),value :: elem_size type(c_funptr),value :: compare !int(*compare)(const void *, const void *) end subroutine qsort !standard C library qsort end interface end module Sort program trand use Sort external compar integer(c_int) compar integer(c_int),target :: array(10) = [5,1,9,0,8,7,3,4,6,2] integer(c_size_t) l/10/,isize/4/ call qsort( c_loc(array(1)), l, isize, c_funloc(compar) ) write(*,'(10i3)') array end program trand integer(c_int) function compar( a, b ) bind(C) use iso_c_binding integer(c_int) a, b if ( a .lt. b ) compar = -1 if ( a .eq. b ) compar = 0 if ( a .gt. b ) compar = 1 end function compar Преимущества и недостатки программ.  метод quick sort является одним из самых быстрых методов сортировки матриц в среднем (n log 2 n) он обычно используется для классификации с некоторыми изменениями в его структуре меньшие элементы отправляются слева, а большие-справа для более упорядоченной сортировки  метод шейкера работает медленно в тестах, где меньшие элементы находятся в конце метод шейкера намного лучше, чем метод пузырьков текст программы- Сортировка данных перемешиванием (шейкерная)” program test integer(4) :: n, i ! n - размер масива, i - счётчик integer(4), allocatable :: mas(:) ! инициализируем массив write(*,*) "Enter size massiv: "; read(*,*) n ! Вводим размер массива allocate(mas(n)) ! Выделяем память под массив write(*,*) "Enter massiv: "; read(*,*) (mas(i), i=1, n) ! Вводим элементы массива call sort_cocktail(n, mas) ! вызываем процедуру сортировки write(*,*) "Sorting data by shuffling: " write(*,*) (mas(j), j=1, n) ! вывод отсортированного массива write(*,*) if(allocated(mas)) deallocate(mas) ! чистим память contains subroutine sort_cocktail(array_size,array) integer i,j integer last_unsorted, firs_unsorted, exchange ! last_unsorted позиция, firs_unsorted - первая позиция, exchange- замена logical way integer,intent(in) :: array_size ! размер масива integer,intent(inout) :: array(array_size) last_unsorted = array_size ! присвиваем размер массива firs_unsorted = 1 ! усанавливаем первую позицию way = .true. ! устанавливаем флаг do j=1,array_size ! пробигаем весь массив if (way) then ! если тру , то идём в цикл до минус одного элемента масиива do i=firs_unsorted,last_unsorted-1 if (array(i) .gt. array(i+1)) then !Если i элемент больше чем предыдущего то exchange = array(i) ! делаем замену элементов, т.е. миняем местами array(i) = array(i+1) array(i+1) = exchange end if end do last_unsorted = last_unsorted -1 ! Уменьшаем счётчик else ! иначе do i=last_unsorted-1,firs_unsorted,-1 ! идём с конца массива до первго if (array(i) .gt. array(i+1)) then ! Если i элемент больше чем предыдущего то exchange = array(i) ! делаем замену array(i) = array(i+1) array(i+1) = exchange end if end do firs_unsorted = firs_unsorted +1 ! увеличиваем первую позицию end if way = .not. way ! меняем флаг if(firs_unsorted .ge. last_unsorted) exit ! если не меньше, то выходим из цикла внешгнго end do end subroutine end program test  Список литературы https://habr.com/ru/post/335920/ https://neerc.ifmo.ru/wiki/index.php?title=Быстрая_сортировка https://forkettle.ru/vidioteka/programmirovanie-i-set/108-algoritmy-i-struktury-dannykh/sortirovka-i-poisk-dlya-chajnikov/1010-metod-khoara-bystraya-sortirovka-quick-sort http://accessdb.ru/msd/index-bystraya_sortirovka_hoara.htm https://kvodo.ru/quicksort.html https://fooobar.com/questions/7825203/sorting-in-fortran-undefined-reference-to-qsort https://forkettle.ru/vidioteka/programmirovanie-i-set/108-algoritmy-i-struktury-dannykh/sortirovka-i-poisk-dlya-chajnikov/1007-sortirovka-shejkernaya-peremeshivaniem-shaker-cocktail-sort https://programm.top/c-sharp/algorithm/array-sort/quick-sort/ http://lampalap.blogspot.com/2011/03/blog-post_31.html http://py-algorithm.blogspot.com/2011/11/quicksort.html https://prog-cpp.ru/sort-fast/ https://programm.top/c-sharp/algorithm/array-sort/shaker-sort/ https://purecodecpp.com/archives/1895 https://rosettacode.org/wiki/Sorting_algorithms/Quicksort#Fortran https://gist.github.com/1AdAstra1/6f7785373efe5bb6c254d2e20c78ccc4/revisions#diff-9d780c0a7564ca0345e275672d233c4d250d2dfc0748778583cf44404f48429a https://retrolib.ru/shejkernaya-sortirovka-pascalpaskal/ |