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.  В чому полягає метод сортування Шелла?


 

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

20272. ОБОРУДОВАНИЕ GPRS. Сервисный узел поддержки услуг GPRS (SGSN) 1.58 MB
  Структурная схема SGSN В структуру SGSN входят: UNIX серверы блок маршрутизации интерфейсные модули интерфейсов на базе ОКС № 7 Gr Gd Gf Gs модули Gb интерфейса. UNIX серверы выполняют основные функции SGSN такие как управление мобильностью управление сессиями тарификация функции протокола GTP и др.Основные функции SGSN разделяются на две плоскости рис.
20273. Высокое качество передачи речевой информации 133.5 KB
  К началу 1994 года сети основанные на рассматриваемом стандарте имели уже 1. Воистину GSM шагает по планете в настоящее время телефоны этого стандарта имеют около 200 миллионов человек а GSMсети можно найти по всему миру. ОСНОВНЫЕ ЧАСТИ СИСТЕМЫ GSM ИХ НАЗНАЧЕНИЕ И ВЗАИМОДЕЙСТВИЕ ДРУГ С ДРУГОМ Начнем с самого сложного и пожалуй скучного рассмотрения скелета или как принято говорить блоксхемы сети.
20274. ПОЛЬЗОВАТЕЛЬСКИЙ ИНТЕРФЕЙС МОБИЛЬНОЙ СТАНЦИИ 82.5 KB
  Примитивы ввода Спецификацией GSM предусмотрен следующий набор элементарных процедур ввода: 1 2 то же что и ABC 3 то же что и DEF 4 то же что и GHI 5 то же что и JKL 6 то же что и MNO 7 то же что и PQRS 8 то же что и TUV 9 то же что и WXYZ 0 то же что и SELECT ACCEPT SEND END для ввода номера в международном формате Код Страны Номер Процедура выбора страны PLMN Процедура ввода дополнительных данных о вызове голос факс данные синхронный асинхронный режим передачи и т. Индикатор...
20275. СЕТЕВЫЕ АСПЕКТЫ УПРАВЛЕНИЯ СПС 96 KB
  Третий уровень протокола обмена сигналами GSM подразделяется на три подуровня: Подуровень управления радио ресурсами Radio Resources Management. Спецификация MAP это одна из самых объемных частей в рекомендациях GSM.В системах GSM существуют четыре основных типа таких процедур: Каналы тайм слоты принадлежат одной соте. Очень важным аспектом GSM является тот факт что MSC так называемая якорная MSC является ответственной за большинство функций имеющих непосредственное отношение к соединению за исключением внутренних BSC хандоверов...
20276. Оборудование подсистемы коммутации (SSS) 254 KB
  Подсистема коммутации системы SSS в рамках СМЕ20 реализована на базе известной коммутационной системы АХЕ10. Каждая подсистема разделена на функциональные блоки. Подсистемы APT Подсистема Наименование подсистемы Функции Назначение станции в сети GSM CCS Common Channel Signalling Subsystem ОКС Управление ОКС № 7 MSC GMSC BSC HLR CHS Charging Subsystem Тарификация Обеспечение тарификации и учет стоимости MSC DTS Data Transmission Subsystem Передача данных Пакетирование сообщений при передаче данных в среде ISDN по Dканалу MSC ESS...
20277. ЯПОНИЯ в 20-30-е гг.20в. основные черты экономического и политического развития 16.94 KB
  В годы первой мировой войны и после нее происходил значительный экономический рост Японии. Политическая власть в Японии принадлежала прежде всего императору совету старейшин генро Тайному совету и правительству. Фашизация Японии. преодолевались в Японии за счет милитаризации экономики т.
20278. Причины и характер войны 19.19 KB
  Разгром Франции. Что касается поведения Англии и Франции то дело тут было более сложным. Объясняется это тем что Англия к войне на суше как военноморская держава подготовлена не была а правительство Франции в свою очередь ориентировалось на Англию. На поведении Англии и Франции отразилось также подписание 28 сентября 1939 г.
20279. КОРЕННОЙ ПЕРЕЛОМ В ХОДЕ ВЕЛИКОЙ ОТЕЧЕСТВЕННОЙ И ВТОРОЙ МИРОВОЙ ВОЙНЫ 19.04 KB
  КОРЕННОЙ ПЕРЕЛОМ В ХОДЕ ВЕЛИКОЙ ОТЕЧЕСТВЕННОЙ И ВТОРОЙ МИРОВОЙ ВОЙНЫ Вспомните. Начался коренной перелом в ходе Великой Отечественной и второй мировой войны. Битва под Курском знаменательное событие второй мировой войны. Победа на Курской дуге и успешное наступление завершили коренной перелом в ходе Великой Отечественной и второй мировой войны.
20280. КИТАЙСКАЯ модель развития 19.78 KB
  СССР признал КНР и в феврале 1950 г. в КНР был восстановлен довоенный уровень экономики. Маоисты решили подавить оппозицию внутри КНР и установить военнобюрократическую диктатуру.