7 клас. Інформатика. Дистанційне навчання: Алгоритми сортування одновимірного масиву в Pascal

Сортування елементів у одновимірних масивах

Задача 1. При роботі з масивами даних не рідко виникає завдання їх сортування за зростанням або спаданням, тобто упорядкування. Це означає, що елементи того ж масиву потрібно розташувати строго по порядку. Наприклад, в разі сортування за зростанням попередній елемент повинен бути менше наступного (або дорівнює йому).

Розв’язання

Існує безліч методів сортування. Одні з них є більш ефективними, інші - простіше для розуміння. Досить простий для розуміння є сортування методом бульбашки, який також називають методом простого обміну. У чому ж він полягає, і чому у нього така дивна назва: "метод бульбашки"?

Як відомо повітря легше води, тому бульбашки повітря спливають. Це просто аналогія. У сортуванні методом бульбашки по зростанню легші (з меншим значенням) елементи поступово "спливають" в початок масиву, а більш важкі один за одним опускаються на дно (до кінця масиву).

Алгоритм і особливості цього сортування такі:

1. При першому проході по масиву елементи попарно порівнюються між собою: перший з другим, потім другий з третім, слідом третій з четвертим і т.д. Якщо попередній елемент виявляється більше наступного, то їх міняють місцями.

2. Не важко здогадатися, що поступово найбільше число виявляється останнім. Інша частина масиву залишається відсортованої, хоча деяке переміщення елементів з меншим значенням в початок масиву спостерігається.

3. При другому проході нема чого порівнювати останній елемент з передостаннім. Останній елемент вже стоїть на своєму місці. Значить, число порівнянь буде на одне менше.

4. На третьому проході вже не треба порівнювати передостанній і третій елемент з кінця. Тому число порівнянь буде на два менше, ніж при першому проході.

5. В кінці кінців, при проході по масиву, коли залишаються тільки два елементи, які треба порівняти, виконується тільки одне порівняння.

6. Після цього перший елемент нема з чим порівнювати, і, отже, останній прохід по масиву не потрібен. Іншими словами, кількість проходів по масиву m-1, де m - це кількість елементів масиву.

7. Кількість порівнянь в кожному проході одно m-i, де i - це номер проходу по масиву (перший, другий, третій і т.д.).

8. При обміні елементів масиву зазвичай використовується "буферна" (третя) змінна, куди тимчасово поміщається значення одного з елементів.

Програма на мові Паскаль:

const

m = 10;

var

arr: array[1..m] of integer;

i, j, k: integer;

begin

randomize;

write ('Початковий масив: ');

for i := 1 to m do begin

arr[i] := random(256);

write (arr[i]:4);

end;

writeln; writeln;

for i := 1 to m-1 do

for j := 1 to m-i do

if arr[j] > arr[j+1] then begin

k := arr[j];

arr[j] := arr[j+1];

arr[j+1] := k

end;

write ('Відсортований масив: ');

for i := 1 to m do

write (arr[i]:4);

writeln;

readln

end.

Найшвидший алгоритм Хоора(Гоара) для сортування одновимірного масиву у вигляді процедури мовою програмування Pascal

Ця процедура, після її оголошення, сортує масив mas, який складається з елементів типу integer.

Procedure QuickSort(first, last :integer);
Var v, x, left, right :integer;
begin
  left := first;
  right := last;
  v := mas[(left + right) div 2];
  while left <= right do
    begin
    while mas[left] < v do
      left := left + 1;
    while mas[right] > v do
      right := right - 1;
    if left <= right then
      begin
        x := mas[left];
        mas[left] := mas[right];
        mas[right] := x;
        left := left + 1;
        right := right - 1;
      end;
    end;
  if first < right then 
    QuickSort(first, right);
  if left < last then
    QuickSort(left, last);
end;

Задача 2. Випадковим чином задається двомірний масив(цe таблиця чисeл) , що складається із nxn елементів, якщо n менше 100. Вивести масив на екран у вигляді таблиці чисел та знайти суму елементів, що розташовані на обох діагоналях масиву. Вивести одномірними масивами елементи окрeмо верхнього і окрeмо нижнього трикутника матриці без головної діагоналі знайти суму елементів верхнього трикутника та сума елементів нижнього трикутника квадратної матриці nxn.

Розв′язання.

Program Summa_trukutnuk_matriza;

const m=100; n=100;

var sum,f,s, d, c:real; b:array[1..m*n] of real;

xn:array[1..m*n] of real; xv:array[1..m*n] of real; a:array[1..m,1..n] of real;

i,j,p, g, k:integer;

begin

writeln(' Ввeдіть кількість рядків квадратного масиву, яка мeншe 100 ');

readln(k); s:=0;

for i:=1 to k do

for j:=1 to k do begin

a[i,j]:=int(random*20-10);

b[(i-1)*k+j]:=a[i,j]; end; writeln(' ');

writeln(' Масив випадкових чисeл: '); writeln(' ');

for i:=1 to k do begin

for j:=1 to k do begin write(' a[',i,';',j,']:= ',a[i,j] {' b[',i-1*k+j,']= ',b[(i-1)*k+j]});

end; writeln(' '); end;

s:=0; for i:=1 to k do begin s:=s+a[i,i]; end;

f:=0; for i:=1 to k do begin f:=f+a[i,k+1-i]; end;

if k mod 2 =1 then sum:=s+f- a[k div 2 +1, k div 2 +1] else sum:=s+f;

p:=1; g:=1; for i:=1 to k do begin

for j:=k downto 1 do begin

if i<j then begin

xv[g]:= a[i,j]; g:=g+1; end; end; end;

for i:=1 to k do begin

for j:=1 to i-1 do begin

if i>j then begin

xn[p]:= a[i,j]; p:= p+1; end; end; end;

writeln(' Масив чисeл нижнього трикутника матриці : ');

d:=0; for i:=1 to ((k-1)*k) div 2 do begin d:=d+ xn[i];

write(' xn[',i,']= ', xn[i]); end; writeln(' ');

writeln(' Масив чисeл вeрхнього трикутника матриці : ');

c:=0; for i:=1 to ((k-1)*k) div 2 do begin

c:=c+ xv[i]; write(' xv[', i, ']= ', xv[i]); end; writeln(' ');

writeln(' Сума чисел головної діагоналі матриці:', s); writeln(' ');

writeln(' Сума чисел бічної діагоналі матриці :', f); writeln(' ');

writeln(' Сума чисел на обох діагоналях: ', sum); writeln(' ');

writeln(' Сума чисел верхнього трикутника матриці ' , c); writeln(' ');

writeln(' Сума чисел нижнього трикутника матриці ' , d); writeln(' '); end.

Задача 3. Вагони

(Час: 1 сек. Пам'ять: 16 Мб Складність: 23%)

Щодня диспетчеру залізничної станції доводиться переставляти вагони в багатьох поїздах, щоб вони йшли в заданому порядку. Для цього диспетчер може розчепити прийшов на станцію складу в довільних місцях і переставити утворилися зчіпки з одного або декількох вагонів в довільному порядку. Порядок вагонів в одній зчепленні міняти не можна, також не можна розгорнути всю зчеплення так, щоб останній вагон в зчепленні виявився першим в ній.

Відомі алгоритми сортування

За час

\;O(n^{2})

Сортування вибором — ( англ. Selection sort ) — пошук найменшого або найбільшого елемента і переміщення його в початок або кінець впорядкованого списку.
Сортування вставкою — (англ. Insertion sort) — Визначаємо місце де поточний елемент повинен знаходитися в упорядкованому списку, і вставляємо його туди.
Сортування обміном (сортування бульбашкою ( англ. Bubble sort )) — для кожної пари індексів проводиться обмін, якщо елементи розташовані не по порядку.
Сортування методом бінарної вставки

За час

O(n\log \;n)

Плавне сортування (англ. Smoothsort)

За час

\;O(n)

з використанням додаткової інформації про елементи

За час

O(n\log ^{2}\;n)

За час

O(nn!)

В даному розділі розглянуто набір реалізацій А.Нікітін на мові Pascal стандартних алгоритмів, застосовуваних при вирішенні завдань олімпіадного програмування.

7 клас. Інформатика. Дистанційне навчання

вівторок, 2 червня 2020 р.

Алгоритми сортування одновимірного масиву в Pascal

Відомі алгоритми сортування

Немає коментарів:

Дописати коментар

вівторок, 2 червня 2020 р.

Алгоритми сортування одновимірного масиву в Pascal

Відомі алгоритми сортування

Немає коментарів:

Дописати коментар

вівторок, 2 червня 2020 р.