Языки программирования

   largestLocation=1

for j=2 to N-(i-1) do

    if list[j]>largest then

         largest=list[j]

                 largestLocation=j

  end if

  end for

  Swap(list[N-(i-1)], list[largestLocation])

  end for

return largest

 

 

 

 

 

 

3.  Алгоритмы сортировки

 

3.1. Сортировка  вставками

 

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

Сортировка вставками считает  первый элемент любого списка отсортированным  списком длины 1. Двухэлементный отсортированный  список создается добавлением второго  элемента исходного списка в нужное место одноэлементного списка, содержащего первый элемент. Затем вставляется третий элемент исходного спсика. Процесс повторится до тех пор, пока все элементы исходного списка не окажутся в расширяющейся  отсортированной части списка.

Ниже приведен алгоритм, реализующий этот процесс:

 

InsertionSort(list, N)

List   сортирующий список элементов

N       число элементов в списке

  For i=2 to N do

  newElement=list[i]

   location=i-1

while(location>=1) and (list[location]>newElement) do

  //    сдвигаем все элементы, большие очередного

list[location+1]=list[location]

location=location-1

  end while

  list[location+1]= newElement

  end for

 

 

 

 

 

 

 

 

3.2. Пузырьковая  сортировка

 

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

Ниже приведен алгоритм, реализующий вариант пузырьковой  сортировки.

 

BubbleSort(list, N)

list   сортируемый список элементов

N       число элементов в списке

 

number0fPairs=N

swappedElements=true

while  swappedElements  do

   number0fPairs= number0fPairs-1

swappedElements= false

  for i=1 to  number0fPairs  do

       if    list[i] > list[i+1]  then

Swap(list[i], list[i+1])

swappedElements=true

         end  if

     end for

end while

 

 

 

3.3. Сортировка  Шелла

 

Сортировку Шелла придумал Дональд Л.Шелл. Ее  необычность состоит в том, что она рассматривает весь список как совокупность  перемешанных подсписков. На первом шаге эти подсписки представляют собой  простые пары элементов. На втором шаге в каждой группе  по четыре элемента.  При  повторении процесса    число элементов    в каждом подсписке   увеличивается, а число подсписков, соответственно, падает.    

 

Ниже приведен алгоритм сортировки Шелла.

 

Shellsort(list, N)

list   сортируемый список элементов

N       число элементов в списке

 

Passes=[log_2 N]

number0fPairs=N

  while( passes >=1) do

   increment = 2^Passes -1

  for  start =1 to     increment  do

        InsertionSort(list, N, start, increment)     

     end for

  passes= passes-1

    end while

 

 

3.4. Корневая сортировка

 

При корневой сортировке упорядочивание списка происходит без непосредственного  сравнения ключевых значений между  собой. При этом создается набор  «стопок», а элементы  распределяются по стопкам в зависимости от значений ключей.  Собрав значения обратно и повторив  всю процедуру для последовательных частей ключа, мы получаем отсортированный список.

Ниже приведен алгоритм   корневой сортировки .

 

RadixSort(list, N)

list   сортируемый список элементов

N       число элементов в списке

 

shift=1

  for loop =1 to    keySize  do

     for  entry =1 to  N  do

bucketNumber=(list[entry].key/shift) mod 10

  Append(bucket[ bucketNumber], list[entry])

         end for  entry

 

   list = CombineBuckets()

        shift = shift *10

    end for  loop

 

 

 

3.5. Пирамидальная сортировка

В основе пирамидальной  сортировки   лежит специальный  тип бинарного дерева, называемый пирамидой; значение корня  в любом  поддереве     такого дерева больше, чем значение каждого из его потомков. Непосредственные  потомки каждого узла не упорядочены, поэтому иногда левый непосредственный потомок  оказывается больше  правого, а иногда и  наоборот. Пирамида представляет собой полное дерево, в котором заполнение  нового уровня начинается     только после того, как предыдущий уровень заполнен целиком, а все узлы на одном уровне заполняются слева направо.

Ниже приведен алгоритм   пирамидальной  сортировки .

 

сконструировать пирамиду

for  i =1    to    N  do

        скопировать корень пирамиды  в список           

        переформировать пирамиду

    end  for 

 

 

 

 

3.6. Сортировка  слиянием

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

Ниже приведен алгоритм  сортировки слиянием.

 

MergeSort(list, first,last)

list   сортируемый список элементов

first      номер первого элемента  в сортируемой части списка

last       номер последнего элемента  в сортируемой части списка

 

if first < last   then

    middle=(first+last)/2

    MergeSort(list, first, middle)

     MergeSort(list, middle+1, last)

     MergeLists(list, first,middle, middle+1, last)

        end  if

 

 

 

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

Быстрая сортировка  также  является рекурсивным алгоритмом  сортировки. Выбрав элемент в списке, быстрая сортировка делит с его      помощью  список на две части. В первую часть попадают все элементы, меньшие выбранного, а во вторую- большие элементы.

Ниже приведен алгоритм  быстрой  сортировки .

 

Quicksort(list, first,last)

list   упорядочиваемый список элементов

first      номер первого элемента  в сортируемой части списка

last       номер последнего элемента  в сортируемой части списка

 

if first < last   then

    pivot=PivotList(list, first, last)

     Quicksort(list, first, pivot-1)

          Quicksort(list,  pivot+1, last)

        end  if