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


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

 

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

 

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

 

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

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

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

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

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

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

Сортировка перемешиванием(Шейкерная) - устойчивая(слож-ть n^2)

(по возраст) 1.Обозначим каждый пройденный путь от начала до конца Wi, а обратный Wj

2. После Wi один из неустойч. эл-тов будет перемещен в поз справа как наиб, а после Wj наим из неотсорт. переместится в поз слева

3. И т.д. до отсортировки массива

procedure ShakerSort(Mas: Massiv; Start, m: integer);

var Left, Right, temp, i: integer;

begin

 Left:=Start; Right:=m;

  while Left<=Right do

begin

   for i:=Right downto Left do

   if (Mas[i-1]>Mas[i]) then

begin

    temp:=Mas[i];

    Mas[i]:=Mas[i-1];

   Mas[i-1]:=temp;

  end;

 Left:=Left+1;

  for i:=Left to Right do

   if Mas[i-1]>Mas[i] then begin

    temp:=Mas[i];

    Mas[i]:=Mas[i-1];

    Mas[i-1]:=temp;

  end; Right:=Right-1;

end;

for i:=1 to M do write(' ', Mas[i]); end;

Сортировка вставками - устойчивая, сложность n^2

"+" Простота, эффект на частично упоряд. или состоящих из небольшого числа эл-тов

(По возраст) 1. Сравниваем 2 первых эл-та, если 2<1, то 1<->2, если 2>1, то ничего не меняется

2. Рассмотрим 3 эл-т. 2.1. 1<3,2<3, =>1-2-3

2.2. 1>3, 2>3, => 3-1-2

2.3. 1<3, 2>3 => 1-3-2

2.4. 1>3, 2<3 => 3-2-1

3. И т.д. до последнего эл-та

var i, j, temp, nom, n: integer;

procedure InsertSort(mas: arr; n: integer);

begin

 for i:=1 to n-1 do begin

  nom:=i+1;

  temp:=mas[nom];

   for j:=i+1 downto 2 do begin

    if (temp

     mas[j]:=mas[j-1];

     nom:=j-1;

    end; end;

  mas[nom]:=temp; end;

write('Результирующий массив: ');

for i:=1 to n do write(mas[i], ' ');  end;

Блочная сортировка - устойчивая, сложность n, требуется K доп памяти

1. Разделяем все элементы по конечному числу отдел блоков

2. Сортируем каждый блок отдельно

3. Помещаем элементы обратно в массив

var i,j,n,k:longint;

     a:array[1..100000] of longint;

     b:array[1..1000,1..1000] of longint;

     razmer:array[1..1000] of integer;

{с помощью QSort мы будем сортировать карманы}  

     procedure QSort(first,last:integer);

     var L,R,c,X:integer;

     begin

        if first < last then begin

           X:= b[i,(first + last) div 2];

           L:= first;R:= last;

           while L <= R do begin

               while b[i,L] < X do

                  L:= L + 1;

               while b[i,R] > X do

                  R:= R - 1;

               if L <= R then begin

                  c:=b[i,L]; b[i,L]:=b[i,R];

                  b[i,R]:=c;L:=L+1;

                  R:=R-1;end;end;

    QSort(first, R);   

    QSort(L, last);

    end;end;

{заполняем массив}

  begin

     read(n);

     for i:=1 to n do

        a[i]:=random(10000);  

{разбиваем массив на карманы}

     for i:=1 to n do begin

        b[(a[i] div 10)+1,razmer[(a[i] div 10)+1]+1]:=a[i];

        razmer[(a[i] div 10)+1]:=razmer[(a[i] div 10)+1]+1;

     end;

{сортируем карманы}

 for i:=1 to 1000 do

        if razmer[i]<>0 then Qsort(1,razmer[i]);

{восстанавливаем массив}  

     k:=0;

     for i:=1 to 1000 do

     for j:=1 to razmer[i] do begin

        k:=k+1; a[k]:=b[i,j];

     end;

 {выводим отсортированный массив}

     writeln; writeln;

     for i:=1 to n do

     write(a[i],' ');

  end.

11.


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