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


 

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

21453. Комплексные числа. Комплексные числа являются естественным обобщением понятия вещественных чисел 392 KB
  Комплексные числа. Комплексные числа являются естественным обобщением понятия вещественных чисел. При этом числа x и y называются вещественной и мнимой частями соответственного комплексного числа z. Два комплексных числа и считаются равными между собой тогда и только тогда когда равны их вещественные и мнимые части т.
21454. Линейные однородные дифференциальные уравнения с постоянными коэффициентами 234 KB
  Линейные однородные дифференциальные уравнения с постоянными коэффициентами. Оператор L можно представить в следующем виде 1б где корни характеристического уравнения 4 их кратности. При n=2 имеем причем где корни характеристического уравнения Далее Пусть теперь при некотором: где мы...
21455. Системы линейных дифференциальных уравнений 293 KB
  Системы линейных дифференциальных уравнений. Напомним что достаточными условиями существования и единственности решения системы обыкновенных дифференциальных уравнений 1 удовлетворяющего начальным условиям 2 являются: непрерывность всех функций в окрестности начальных значений; выполнение условия Липшица для всех...
21456. Системы линейных дифференциальных уравнений с постоянными коэффициентами 282 KB
  Системы линейных дифференциальных уравнений с постоянными коэффициентами. Итак общее решение однородной системы 1 имеет вид 6 причем векторы 7 частные решения системы 1 которые могут быть получены следующим образом. Итак решения линейно...
21457. Матричная экспонента 394 KB
  а матрица j й столбец которой есть решение системы 1а с начальными условиями т. матрица имеет вид и удовлетворяет уравнению Тогда вектор t решение системы 1а с начальным условием может быть записан в виде т. Запишем теперь jе решение уравнения 1а удовлетворяющее начальному условию где диагональная матрица вектор столбец коэффициентов и положим где матрица коэффициентов . Теперь окончательно имеем...
21458. Спектральные приборы 519 KB
  различаются методами спектрометрии приёмниками излучения исследуемым рабочим диапазоном длин волн и др. Форма отверстия в равномерно освещенном экране 1 соответствует функции f описывающей исследуемый спектр распределение энергии излучения по длинам волн . группа 2 информация об исследуемом спектре получается путём одновременной регистрации без сканирования по  несколлькими приёмниками потоков излучения разных длин волн    .
21459. Управление света светом 870.5 KB
  ставит очень амбициозную задачу создание устройств выполняющих функции управления характеристиками оптического излучения с помощью другого оптического излучения. Предлагается воспользоваться свойствами поляризованного электромагнитного оптического излучения а именно использовать эффект оптического гашения который описан например в [3]. 1 Если четвертьволновую пластинку P1 установить так чтобы её быстрая ось была ориентирована под углом к оси OX то для излучения прошедшего через пластинку P1 получим = 1 = . 2 Согласно [4]...
21460. Применение лазерного излучения для управления движением атомами и ионами 789.5 KB
  Этот эффект называется охлаждением атомов давлением лазерного излучения. Методы позволяющие с помощью лазерного излучения охлаждать атомы основаны на эффекте вязкой жидкости оптическая патока в которой атомы медленно перемещаются. При охлаждении вещества его энергия и энтропия понижаются поэтому процесс охлаждения возможен если энергия и энтропия излучения после взаимодействия с веществом повышаются.
21461. Лазерный пинцет 957 KB
  Сила с которой свет действует на окружающие объекты невелика но ее оказывается достаточно чтобы ловить и контролируемо перемещать частицы размером от 10 нм до 10 мкм. В дальнейшем Эшкин и его коллеги продемонстрировали возможности оптической ловушки на основе инфракрасного лазера захватывать удерживать и перемещать в пространстве различные биологические объекты такие как вирусные частицы одиночные бактериальные и дрожжевые клетки и органеллы в живых клетках водорослей. Как будет вести себя частица в поле после Пишейпера В случаях...