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


 

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

1850. ОБРАЗ ЖИЗНИ БРИТАНСКОЙ ЭЛИТЫ В ТРЕТЬЕЙ ЧЕТВЕРТИ XIX ВЕКА 1.26 MB
  Изменение положения британской элиты в третьей четверти XIX в. Распределение социального, экономического и политического влияния в элитных группах британского общества. Трансформация ценностных ориентиров элитных групп. Досуговая культура средневикторианского высшего общества.
1851. ПЕДАГОГИЧЕСКИЕ АСПЕКТЫ ПРЕОДОЛЕНИЯ НЕГАТИВНЫХ ПОСЛЕДСТВИЙ УЧЕБНЫХ ФАКТОРОВ РИСКА, ОТРАЖАЮЩИХСЯ НА ЗДОРОВЬЕ УЧАЩИХСЯ КОЛЛЕДЖА 1.26 MB
  Современные научные подходы к выделению факторов риска в образовательном процессе. Педагогические подходы в выявлении негативных последствий учебных факторов риска, отражающихся на здоровье учащихся колледжа. Изучение взаимосвязи учебных факторов риска и состояния здоровья учащихся. Анализ результатов изучения педагогических подходов к преодолению учебных факторов риска в образовательном процессе колледжа.
1852. СЕМАНТИЧЕСКИЕ, ГРАММАТИЧЕСКИЕ И ФУНКЦИОНАЛЬНЫЕ ОСОБЕННОСТИ СЛОВА 1.26 MB
  Аспекты изучения проблемы переходности в области неполнозначных слов. Трудные случаи морфологической квалификации слова так. Пословицы, поговорки, крылатые выражения с элементом так. Возможности транспозиции слова "так".
1853. Промисловий аналіз продуктів какао 337.08 KB
  Какао продукти, какао напої та екстракти. Какао як продукт харчування. Виробництво шоколаду. Кондитерська промисловість. Замінники какао-масла.
1854. Теории и современные воспитательные концепции 163 KB
  Современные воспитательные концепции. Системное построение процесса воспитания. Воспитательная система образовательного учреждения. Характеристика компонентов воспитательной системы. Педагогическая поддержка ребенка и процесса его развития.
1855. Оружие геноцида 3.13 MB
  “Нормальная” культура ненормальных людей. Общее воздействие алкоголя на организм. Гипоксия — алкогольная эйфория. Почему пьющие избегают трезвых. О главной причине употребления психотропов. Творчество под угнетением табака. Курение и детородная функция. Целомудрие здравомыслие.
1856. Сегментация изображений и поиск объектов медицины и биологии 3.01 MB
  Программные системы и методы 3D-реконструкции биомедицинских данных. Модели, методы и алгоритмы, положенные в основу сегментации и поиска объектов. Сегментация данных компьютерной томографии и электронной микроскопии. Описание реализации программной системы. Примеры результатов сегментации и идентификации объектов.
1857. МАТЕМАТИЧЕСКОЕ МОДЕЛИРОВАНИЕ ЗАНОСА АВТОМОБИЛЯ 1.09 MB
  Анализ подходов к математическому и численному моделированию движения автомобиля. Постановка задачи. Оценка области применимости велосипедной модели. Математические модели движения автомобиля без потери сцепления колес с дорогой. Математическая модель переменной структуры для описания заноса автомобиля.
1858. МЕТОДИЧЕСКИЕ ОСНОВЫ ФОРМИРОВАНИЯ СИСТЕМЫ ЦЕНООБРАЗОВАНИЯ БАНКОВСКИХ УСЛУГ 1.26 MB
  Необходимость и специфика ценообразования в коммерческих банках. Банковская услуга как объект ценообразования в кредитных организациях. Анализ влияния внешних факторов на ценообразование в коммерческих банках. Стратегия банка как основа моделирования системы ценообразования банковских услуг.