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


 

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

1428. Вирощування молодняка великої рогатої худоби 507.5 KB
  Закономірності росту органів і тканин у різні вікові періоди тварин і використання їх при вирощуванні ремонтного молодняку. Проектування технології вирощування ремонтного молодняку. Розрахунок потреби в скотомісцях і засобах механізації розміщення поголів'я.
1429. Реконструкция станции технического обслуживания 330 KB
  Наличие подвижного состава на АТП. Подвижной состав АТП с распределением годами выпуска. Технологический процесс ТО и ТР. Управление производством ТО и ремонта в системе ЦУП с использованием элементов АСУ. Характеристика объекта реконструкции (зоны ТР). Общий технологический процесс ТО и ремонта на объекте реконструкции.
1430. Строительство канализационных очистных сооружений производительностью 25 м3/сутки для промплощадки Мокроусского ЛПУМГ ООО Югтрансгаз 129.5 KB
  Цель работы – проектирование канализационных очистных сооружений производительностью 25м3/сутки для промплощадки Мокроусского ЛПУМГ ООО Югтрансгаз ОАО Газпром.
1431. Система управления и контроля радиоприемным устройством 1.07 MB
  Обеспечение функционирования вычислительного комплекса, обнаружения сбоев и отказов модулей и горячего восстановления. Требования к организации и оборудованию рабочих мест с ПЭВМ для взрослых пользователей. Команды буфера интерфейсной информации.
1432. Расчет параметров двигателя 147.5 KB
  При выборе отношения хода поршня к диаметру цилиндра S/D необходимо учитывать следующие обстоятельства. Предназначен для преобразования возвратно-поступательного движения поршня во вращательное движение коленчатого вала.
1433. Проект для строительства завода по ремонту бытовых машин в городе Белово 128.5 KB
  Проект разработан для строительства в городе Белово, преобладающее направление ветров ЮЗ с силой 0.38 кПа. Нормативное значение веса снегового покрова принято 1.5 кПа. Глубина промерзания грунтов 2.2 м. Температура наружного воздуха наиболее холодной пятидневки – 400С.
1434. Экономическое обоснование проектирования двигателя 124.5 KB
  Целью расчетов является обоснование экономической целесообразности создания и применения спроектированного двигателя. Решение принимается на основе расчета экономического эффекта путем сопоставления результатов и затрат по проектируемому и базовому вариантам при условии сопоставимости их по объему
1435. Уровневые фронтальные лабораторные работы 231.52 KB
  Составной частью исследуемой проблематики является уровневый подход к формированию практических умений и навыков школьников. Для реализации этой цели учителем разработаны уровневые фронтальные лабораторные работы, и примеры использования проектной технологии как возможности вариативной организации учебных занятий.
1436. Алгоритм решения задачи с использованием программ Microsoft Excel и MathCAD 265.69 KB
  Данная работа посвящена автоматизации процессов расчетов. Ее целью является закрепление знаний по всем разделам дисциплины Информатика, проверка навыков практической работы с программными средствами обработки информации.