пользователей: 21244
предметов: 10456
вопросов: 177505
Конспект-online
зарегистрируйся или войди через vk.com чтобы оставить конспект.
РЕГИСТРАЦИЯ ЭКСКУРСИЯ

Язык программирования Pascal. Составные типы данных. Массивы. Сортировка массивов. Сортировка Хоара (основная идея, пример реализации).

 

Паскаль (Pascal) разрабатывался, как учебный язык выского уровня, структурного программирования. Относится к 3-му поколению языков программирования.  На основе ALGOL.

 

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

 

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

Массивы могут быть одномерными и многомерными

Описание при помощи слова array в разделе описания типов

Алгоритм сортировки - алгоритм упорядочения элементов в списке

Сортировка массива - процесс перестановки его элементов в опред порядке

Основ требов к методам сортировки - экономия использования памяти

Быстрая сортировка — широко извест алгоритм сортировки, разработ англ информатиком Чарльзом Хоаром. Самый быстрый из извест универс алгоритмов сортировки массивов (в среднем O(n log n) обменов).

            Разделяй и властвуй — в информатике важная парадигма разработки алгоритмов. Основана на рекурсивном разбиении решаемой задачи на 2 или более подзадач. Разбиения выполняются до тех пор, пока все подзадачи не станут элементарными.

            Рекурсия - ситуация, когда какой-то алгоритм вызывает себя прямо или через другие алгоритмы в качестве вспомогательного.

            Любая рекурсия содержит 2 условия:

1.вычисление результата через другие значения, не  влечет нового рекурсивного вызова;

2.вычисление значения с помощью самовызова функции (рекурс вызов).

Идея быстрой сортировки (по возраст) Массив разделяется на 2 равные части, каждая сортируется и они сливаютсяя в одну. Эта процедура выполняется, пока не останется отсортировать массивы длины 1 и 2.

Шаг 1. Выбираем в массиве элемент, кот назовем опорным. Обычно средний или последний по положению или вообще любой.

Шаг 2. Разделение массива: элементы <=опорному слева, а > справа.

Шаг3. Рекурсивно упорядочиваем подмассивы, лежащие слева и справа от опорного элемента

Шаг 4. Базой рекурсии являются наборы, состоящие из 1 или 2 эл-тов. Если 1, то возвращается в исход виде, если 2: при необходимости меняем местами.

"+" Самый быстродействующий из всех алгоритмов обмен сортировки

Простая реализация

Хорошая работа на "почти отсорт" данных

"-" Требует в худшем случае много доп памяти. Но вероятность худшего случая ничтожна

Не является устойчивым

Пример          type  list = array[1..20] of integer;

            procedure quicksort(var a: list; Lo,Hi: integer);  

                        procedure sort(l,r: integer);

                        var i,j,x,y: integer;

                         begin   

                         i:=l; j:=r; x:=a[random(r-l+1)+l]; { x := a[(r+l) div 2]; - для выбора среднего элемента }     

                                   repeat      

                                   while a[i]

           while x

           if i<=j then begin        

                                     if a[i] > a[j] then begin  

           y:=a[i]; a[i]:=a[j]; a[j]:=y;  end;                                 

                 i:=i+1; j:=j-1;end;    

                                   until i>j;    

                                   if l

                                   if i

                        end;

            begin {quicksort};

  sort(Lo,Hi); end;

 

13.


22.01.2015; 18:52
хиты: 31
рейтинг:0
Точные науки
информатика
Языки программирования
для добавления комментариев необходимо авторизироваться.
  Copyright © 2013-2016. All Rights Reserved. помощь