пользователей: 30398
предметов: 12406
вопросов: 234839
Конспект-online
РЕГИСТРАЦИЯ ЭКСКУРСИЯ


Язык программирования 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
хиты: 977
рейтинг:0
Точные науки
информатика
Языки программирования
для добавления комментариев необходимо авторизироваться.
  Copyright © 2013-2024. All Rights Reserved. помощь