42553

Швидке сортування

Лабораторная работа

Информатика, кибернетика и программирование

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

Украинкский

2013-10-30

31 KB

2 чел.

Міністерство освіти і науки України

Хмельницький національний університет

Кафедра системного програмування

Лабораторна робота №2

З дисципліни структури даних і алгоритми

Тема: 

«Швидке сортування»

 

                                                                                       Виконав ст. гр. КІ-10-3

                                                                    Матвєєв П.

                                                                                          Перевірив Кльоц Ю. П.

Хмельницький 2011

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

Лістинг програми:

uses crt;

const n=8;

type mas=array[1..n,1..n] of integer;

     tmas=array[1..n] of integer;

var m:mas; m2:tmas;

    i,j: integer;

    t: text;

procedure gen(var m:mas; var t:text);

var i,j:integer;

 begin

 randomize;

 rewrite(t);

 for i:=1 to n do begin

 for j:=1 to n do begin

 m[i,j]:=random(10);

 write(t,m[i,j],' ');

 end;

 writeln(t);

 end;

 close(t);

end;

procedure qsort(var m2:tmas; left,right:integer);

var j:integer;

    l,r:integer;

    temp,sred:integer;

 begin

 l:=left; r:=right;

 sred:=round((left+right) div 2);

 repeat

  while (m2[l]>sred) do inc(l);

  while (m2[r]<sred) do dec(r);

  if l<r then begin

   temp:=m2[l];

   m2[l]:=m2[r];

   m2[r]:=temp;

   inc(l); dec(r);

  end;

  until l>r;

  if left<r then qsort(m2,left,r);

  if l<right then qsort(m2,l,right);

 end;

 procedure regen(var m2:tmas; var t:text);

 var i,j:integer;

  begin

  rewrite(t);

  for j:=1 to n do begin

  write (t,m2[j],' ');

  writeln(t);

  end;

  close(t);

 end;

begin

 assign(t,paramstr(1));

 gen(m,t);

 for i:=1 to n do begin

  for j:=1 to n do m2[j]:=m[i,j];

  qsort(m2,1,n);

  for j:=1 to n do m[i,j]:=m2[j];

  regen(m2,t)

 end;

end.

Результат:

Вміст вихідного файлу:

0 1 2 3 3 3 3 7

0 1 3 4 4 6 6 8

1 1 1 4 5 6 7 8

0 1 1 5 6 8 8 9

0 1 1 1 3 8 8 9

0 1 1 2 4 5 6 9

0 0 1 1 4 4 5 8

2 2 3 3 4 6 6 6


 

А также другие работы, которые могут Вас заинтересовать

54020. Лексические игры на уроках английского языка 28 KB
  Лексические игры используются в самых различных целях: при введении нового лексического материала для закрепления его в памяти учащихся и для развития их устной речи. Лексические игры преследуют следующие цели: познакомить учащихся с новыми словами и их сочетаниями; тренировать учащихся в употреблении лексике в ситуациях приближенных к естественной обстановке; активизировать речемыслительную деятельность учащихся; развивать речевую реакцию. Лексические игры сосредоточивают внимание учащихся исключительно на лексическом материале...
54023. I need a book. At the library 101.5 KB
  Teacher: Right you are. A book is a main source of knowledge. It is impossible to imagine our life without books. They play an important role in educating, upbringing and help us to get useful information. Where can we get books?
54024. Life of a Society. Inventors and Inventions 52.5 KB
  First I intended to use canvas to make tents and wagon coverings. But miners complained that their ordinary trousers wore out too quickly. So, I thought and thought and …
54025. Я вибираю життя без шкідливих звичок. Розвиток усного мовлення з теми 81.5 KB
  In 1870 the British Government adopted a law: every packet of cigarette must have a health warning on it. Now we have such a law in Ukraine. But very often a great number of modern advertisements show us beautiful girls or boys who smoke. And many teenagers want to imitate them. There are some rules, which don’t allow people to smoke in public places, such as cinemas, theatres, public transport etc.
54026. Ліквідація Української козацької держави 52.5 KB
  Мета: ознайомити учнів з подіями що передували процесу ліквідації Української козацької держави; розвивати навички роботи з історичною картою; вміння визначати причиннонаслідкові зв’язки подій; Виховувати в учнів почуття патріотизму інтересу і поваги до історичного минулого своєї держави. Після цього уроку учні зможуть: розкривати зміст термінів Малоросія наказний гетьман кріпацтво; називати прізвища видатних осіб цього часу; показувати на карті підручника територію Гетьманщини Запорозької Січі; розповідати про...
54027. Цікава лінгвістика 31.5 KB
  Другорядні члени речення. Напишіть власний твір про однорідні члени речення уявивши велику світлу споруду в якій дружно живе сім’я однорідних членів речення суворо дотримуючись законів співжиття як люди у суспільстві. Другорядні члени речення Плин життя завжди вимагає змін. Ой варто було б побачити що сталося із другорядними членами речення.
54028. Цікаві завдання з української мови для учнів шостого класу 401.5 KB
  Цікаві завдання що включені до розповіді про подорож у пошуках скарбів різноманітні ігрові ситуації допоможуть дітям легше засвоїти граматичні категорії що стосуються зазначених тем. Вступ Призначення цієї книги –- сприяти засвоєнню тем Іменник та Прикметник зокрема завдання побудовано таким чином щоб сформувати уміння визначати граматичні категорії слів зазначених частин мови розвивати словниковий запас учня. Завдання побудовано в ігровій формі їх можна виконувати як поодинці так і удвох з товаришем тоді мандрівку сторінками...