69893

Алгоритми сортування даних в оперативній пам’яті

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

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

Під сортуванням розуміють процес перестановки об’єктів даної множини в певному порядку. Мета сортування – полегшити подальший пошук елементів у відсортованій множині. В цьому значенні сортування присутнє майже у всіх задачах обробки інформації.

Украинкский

2014-10-12

59.5 KB

4 чел.

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

Тема. Алгоритми сортування даних в оперативній пам'яті

Мета: ознайомитися з основними методами сортування даних.

Професійна спрямованість: дана лабораторна робота є складовою частиною професійної підготовки фахівця з інформатики до роботи.

Теоретичні питання (план)

  1.  Поняття та види сортування.
  2.  Методи внутрішнього сортування.
  3.  Порівняння алгоритмів сортування.

Хід виконання роботи

  1.  Ознайомтеся з основними теоретичними відомостями.
  2.  Згідно номеру свого варіанту оберіть умову задачі.
  3.  Побудувати блок-схему.
  4.  Провести аналіз складності алгоритму.

Теоретичні відомості

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

сортування  масивів (внутрішнє сортування)

сортування файлів (зовнішнє сортування).

ПОСТАНОВКА ЗАДАЧІ

ДАНО   

ПОТРІБНО  

ЗВ'ЯЗОК  

і послідовність є перестановкою початкової послідовності.

Основна вимога до методів внутрішнього сортування – економне використання пам'яті. Це означає, що переупорядкування елементів треба виконувати на тому ж місці.

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

сортування включенням(вставкою);

сортування вибором;

сортування обміном;

розділенням.

СОРТУВАННЯ ВКЛЮЧЕННЯМ. Цей метод полягає в тому, що на кожному кроці  беруть i-ий елемент послідовності і передають його в готову відсортовану частину послідовності, вставляючи його на своє місце. Алгоритм сортування включенням виглядає таким чином:

FOR I := 2 TO N DO

   BEGIN X := а[I];

      <вставить X на відповідне місце в а[1],a[2],...,a[I]>

   END

СОРТУВАННЯ ВИБОРОМ. Цей метод базується на наступному правилі. Вибирається мінімальний (максимальний) елемент послідовності і обмінюється з першим елементом послідовності. Очевидно, один елемент при цьому стане на своє місце у відсортованій частині послідовності. Далі все вище викладене треба повторити в не відсортованій частині послідовності і т.д.

FOR I = 1 TO N-1 DO

BEGIN

<присвоїти К індекс найменшого елемента з а[I]...а[N]>

<поміняти місцями а[I] і а[K]>

END

СОРТУВАННЯ ОБМІНОМ. Алгоритм обміну заснований на принципі порівняння і обміну пари сусідніх елементів до тих пір, поки не будуть відсортовані всі елементи. Як приклад розглянемо сортування методом бульбашки.

FOR I:= 2 TO N DO

FOR J:= N DOWNTO I DO

IF а[J-1]> а[J] THEN

BEGIN X := а[J-1]; а[J-1]:= а[J]; а[J]:= X  END

СОРТУВАННЯ РОЗДІЛЕННЯМ. Алгоритм розділенням заснований на розбитті послідовності на дві підпослідовності за деяким правилом. При цьому кожна з них може не бути впорядкованою, але послідовне застосування вказаного правила призводить до впорядкованості послідовності. Прикладом цього класу алгоритмів є алгоритм швидкого сортування.

Procedure quicksort(S);

begin

if  <S містить один елемент> then <повернути S>

else begin <выбрать довільний елемент а з S>;

<нехай S1,S2  і S3  - послідовності елементів з S, відповідно менших, рівних і більших a>;

<повернути quicksort(S1), потім S2, потім quicksort(S3)>

end

end

Варіанти завдань

Завдання 1

Відповідно до свого варіанту реалізувати алгоритм сортування в цілочисельному масиві. Будь-яким способом заповнити елементи масиву значеннями.

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

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

1.

1) Бульбашкове; 2) Швидке.

8.

1) Бульбашкове; 2) Вставками.

2.

1) Вибором; 2) Шелла.

9.

1) Вставками; 2) Вибором.

3.

1) Вставками; 2) Швидке.

10.

1) Шейкерне; 2) Вставками.

4.

1) Бульбашкове; 2) Шелла.

11.

1) Шейкерне; 2) Шелла.

5.

1) Вибором; 2) Швидке.

12.

1) Швидке; 2) Шейкерне.

6.

1) Вставками; 2) Шелла.

13.

1) Шелла; 2) Швидке.

7.

1) Вибором; 2) Бульбашкове.

14.

1) Вибором; 2) Шейкерне.

Побудуйте блок-схему алгоритму.

Завдання 2

Провести аналіз складності алгоритмів сортування із завдання 1, для цього включити в алгоритм підрахунок числа базових операцій (порівняння і обміну) і обчислення часу роботи програми на даному масиві. Результати представити в табличній формі запису.

Рекомендована література

Базова

  1.  Ахо А.В. Структуры данных и алгоритмы / Ахо А.В., Хопкрофт Д.Э., Ульман Д.Д./ М: Вильямс, 2003.— 384 с.
  2.  Вирт Н. Алгоритмы и структуры данных. — М.: Мир, 1989. — 360 с.

Зміст звіту

Тема роботи; умова задачі; реалізація алгоритмів сортування; блок-схема алгоритму;  табличне представлення аналізу складності алгоритмів сортування; висновки за результатами розв’язання.

Контрольні запитання

  1.  Що таке «сортування»?
  2.  Скільки існує груп алгоритмів сортування?
  3.  Скільки існує алгоритмів сортування?
  4.  За якими ознаками характеризуються алгоритми сортування?
  5.  Що потрібно враховувати при виборі алгоритму сортування?
  6.  Який алгоритм сортування вважається найпростішим?
  7.  Який алгоритм сортування вважається найефективнішим?
  8.  Що означає поняття «швидкість сортування»?
  9.  В чому полягає метод бульбашкового сортування?
  10.  В чому полягає метод сортування вибором?
  11.  В чому полягає метод сортування вставками?
  12.  В чому полягає метод сортування розділенням?
  13.  В чому полягає метод швидкого сортування?
  14.  В чому полягає метод сортування Шелла?


 

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

29875. Виды и характеристика профессиональных участников фондового рынка 27.5 KB
  Виды и характеристика профессиональных участников фондового рынка. При этом вид товара ценные бумаги определяет структуру фондового рынка и компоненты этой структуры осуществляющие как собственно его функционирование так и управление его работой: состав участников рынка местоположение порядок функционирования правила регулирования и т. В целом структуру фондового рынка можно представить следующим образом: субъекты рынка; собственно рынок биржевой и внебиржевой фондовые рынки; органы государственного регулирования и надзора в...
29876. Государственные внебюджетные фонды: источники формирования доходов и направления использования средств 37 KB
  В России действуют следующие государственные внебюджетные фонды: Пенсионный фонд Российской Федерации Фонд социального страхования Российской Федерации Федеральный фонд обязательного медицинского страхования. Фонд социального страхования Российской Федерации ФСС РФ один из государственных внебюджетных фондов созданный для обеспечения обязательного социального страхования граждан России. Регулируется Бюджетным кодексом РФ и федеральным законом Об основах обязательного социального страхования. Федеральный фонд обязательного...
29877. Сущность, функции денег и их роль в системе экономических отношений 32 KB
  сущность функции денег и их роль в системе экономических отношений Деньги это средство выражающее ценности товарных ресурсов участвующих в данное время в хозяйственной жизни общества универсальное воплощение ценности в формах соответствующих данному уровню товарных отношений. В другом определении деньги это абсолютно ликвидное средство обмена которое обладает двумя свойствами: обменивается на любой другой товар; измеряет стоимость любого другого товара эта функция выражается в цене и в масштабах этих цен. Сущность денег...
29878. Краткосрочная финансовая политика на предприятии 45.12 KB
  Успешность работы предприятия в краткосрочном периоде в решающей степени зависит от качества разработанной им краткосрочной финансовой политики под которой понимается система мер направленных на обеспечение бесперебойного финансирования его текущей деятельности. Цели КФП: создание регулирование и контроль денежных потоков; обеспечение производства в рамках имеющихся производственных мощностей и основных фондов; обеспечение гибкости текущего финансирования; генерирование накапливание собственных источников финансирования. Основная задача...
29879. Сущность, формы и виды инфляции. Социально-экономические последствия инфляции 14.69 KB
  Инфля́ция повышение общего уровня цен на товары и услуги. В этом случае говорят что за прошедшее время покупательная способность денег снизилась деньги обесценились утратили часть своей реальной стоимости. Этому способствовал целый ряд факторов глобального порядка: быстрый рост товарного производства усложнение его структуры; системы цен и социальных трансфертов стали универсальными; изменилась практика ценообразования под влиянием монополистических предприятий резко снизилась сфера ценовой конкуренции. Повышение эффективности...
29880. Страховые резервы и пути повышения надежности их использования страховыми компаниями 12.61 KB
  Средства страховых резервов не подлежат изъятию в федеральный бюджет и бюджеты других уровней и используются исключительно для осуществления страховых выплат. Страховщик вправе инвестировать и иным образом размещать средства страховых резервов в порядке установленном нормативным правовым актом органа государственного страхового надзора. Размещение средств страховых резервов должно осуществляться на условия диверсификации возвратности прибыльности и ликвидности. Страховые резервы технические резервы по видам страхования не относящимся к...
29881. Сущность и практика деятельности негосударственных пенсионных фондов 13.8 KB
  Негосударственный пенсионный фонд НПФ особая организационноправовая форма некоммерческой организации социального обеспечения исключительными видами деятельности которой являются[1]: деятельность по негосударственному пенсионному обеспечению участников НПФ в соответствии с договорами негосударственного пенсионного обеспечения НПО; деятельность в качестве страховщика по обязательному пенсионному страхованию в соответствии с Законом Об обязательном пенсионном страховании в Российской Федерации[2] и договорами об обязательном пенсионном...
29882. Мировая, европейская, национальная валютные системы и их взаимодействие на современном этапе 34 KB
  Валютная система это форма орга низации и регулирования валютных отношений закрепленная национальным законодательством или межгосударственными соглашениями. Мировая валютная система это совокупность экономических отношений в мировой хозяйственной сфере связанных с функционированием валюты. Развитие мировой валютной системы Международная валютная система мировая валютная система мировая денежная система всех стран в рамках которой формируются и используются валютные ресурсы и осуществляется международный платежный оборот. Мировая...
29883. Государственное регулирование рынка страхования 20.39 KB
  Государственное регулирование рынка страхования Страховой рынок это особая социальноэкономическая среда определенная сфера денежных отношений где объектом куплипродажи выступает страховая защита формируется предложение и спрос на нее. Страховой рынок можно рассматривать также: как форму организации денежных отношений по формированию и распределению страхового фонда для обеспечения страховой защиты общества; как совокупность страховых организаций страховщиков которые принимают участие в оказании соответствующих страховых услуг....