Обчислення суми елементів масиву

Сортування із злиттям

Сортування із злиттям, як правило, застосовуються в тих випадках, коли потрібно відсортувати послідовний файл, що не поміщається цілком в основній пам'яті. Існують і ефективні методи внутрішнього сортування, засновані на розбитті і злитті.

Один з популярних алгоритмів внутрішнього сортування із злиттям заснований на наступних ідеях (для простоти вважатимемо, що число елементів в масиві, як і в нашому прикладі, є ступенем числа 2). Спочатку пояснимо, що таке злиття. Хай є два відсортованих в порядку зростання масиву p[1], p[2]..., p[n] і q[1], q[2]..., q[n] і є порожній масив r[1], r[2]..., r[2?n], який ми хочемо заповнити значеннями масивів p і q в порядку зростання. Для злиття виконуються наступні дії: порівнюються p[1] і q[1], і менше із значень записується в r[1]. Припустимо, що це значення p[1]. Тоді p[2] порівнюється з q[1] і менше із значень заноситься в r[2]. Припустимо, що це значення q[1]. Тоді на наступному кроці порівнюються значення p[2] і q[2] і так далі, поки ми не досягнемо меж одного з масивів. Тоді залишок іншого масиву просто дописується в "хвіст" масиву r.

Для сортування із злиттям масиву а, а,..., а[n] заводиться парний масив b[1], b[2]..., b[n]. На першому кроці проводиться злиття а[1] і а[n] з розміщенням результату в b[1], b[2], злиття а[2] і а[n-1] з розміщенням результату в b[3], b[4]..., злиття а[n/2] і а[n/2+1] з приміщенням результату в b[n-1], b[n]. На другому кроці проводиться злиття пар b[1], b[2] і b[n-1], b[n] з приміщенням результату в а, а, а, а, злиття пар b[3], b[4] і b[n-3], b[n-2] з приміщенням результату в а, а, а, а,..., злиття пар b[n/2-1], b[n/2] і b[n/2+1], b[n/2+2] з приміщенням результату в а, а, а, а[n]. І так далі На останньому кроці, наприклад (залежно від значення n), проводиться злиття послідовностей елементів масиву завдовжки n/2 а, а,..., а[n/2] і а, а,..., а[n] з приміщенням результату в b[1], b[2]..., b[n].

Для випадку масиву, використовуваного в наших прикладах, послідовність кроків показана в таблиці 3.

Таблиця 3. Приклад сортування із злиттям

Початковий стан масиву	8 23 5 65 44 33 1 6
Крок1	6 8 1 23 5 33 44 65
Крок2	6 8 44 65 1 5 23 33
Крок3	1 5 6 8 23 33 44 65

 

 

Мал. 25.

 

 

Приклад злиття двох масивів показаний на малюнку 25.

Порівняння часу сортувань

Зображений нижче графік ілюструє різницю в ефективності вивчених алгоритмів.

· коричнева лінія: сортування бульбашкою; · синя лінія: шейкер-сортування; · рожева лінія: сортування вибором; · жовта лінія: сортування вставками; · блакитна лінія: сортування вставками із сторожовим елементом; · фіолетова лінія: сортування Шелла

Обчислення суми елементів масиву

Даний масив X, що складається з n елементів. Знайти суму елементів цього масиву. Процес накопичення суми елементів масиву достатньо простий і практично нічим не відрізняється від підсумовування значень деякої числової послідовності. Змінною S привласнюється значення рівне нулю, потім послідовно підсумовуються елементи масиву X. Блок-схема алгоритму розрахунку суми приведена на мал. 3.5.

Обчислення добутка елементів масиву

Даний масив X, що складається з n елементів. Знайти добуток елементів цього масиву. Рішення цієї задачі зводиться до того, що значення змінної Р, в яку заздалегідь була записана одиниця, послідовно умножається на значення i-го елементу масиву. Блок-схема алгоритму приведена на мал. 3.6.

Мал. 26. Алгоритм обчислення суми елементів масиву	Мал. 27. Обчислення добутка елементів масиву

Видалення елементу з масиву

Необхідно видалити з масиву X, що складається з n елементів, m-й по номеру елемент. Для цього досить записати елемент (m+1) на місце елементу m, (m+2) - на місце (m+1) і так далі, n - на місце (n-1) і при подальшій роботі з цим масивом використовувати n-1 елемент (мал. 28).

 

Мал. 28. Процес видалення елементу з масиву

 

Алгоритм видалення з масиву Х розмірністю n елементу з номером m приведений на мал. 29.

Мал. 29 Алгоритм видалення елементу з масив

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

1. Ідеальний алгоритм сортування.***2. Параметри оцінки алгоритмів.***3. Які основні алгоритми сортування.***4. Як провести аналіз сортування за часом.****

 

Література:

1. Иванова Г.С., Ничушкина Т.Н., Пугачев Е.К. И21 Объектно-ориентированное программирование: Учеб. для вузов/ Под ред. Г.С. Ивановой. - М.: Изд-во МГТУ им. Н.Э. Баумана, 2001. - 320 с, ил.

2. Архангельский А.Я., Программирование в Delphi 7. М.: ООО «Бином-Пресс», 2003 г. 1152 с.: ил.

3. Колосов С.В.,Программирование в среде Delphi. Учеб. пособие для студентов специальностей «Автоматизированные системы обработки информации» и «Автоматическое управление в технических системах» БГУИР., - Мн.:БГУИР, 2005,-164 с: ил. 34.

4. Пестриков В. М., Маслобоев Л. Н, П28 Delphi на примерах, — СПб.: БХВ-Петербург, 2005. — 496 с: ил. ISBN 5-94157-713-3

5. Дарахвелидзе П. Г., Марков Е. П.Программирование в Delphi 7. — СПб.: БХВ-Петербург, 2003. — 784 с: ил.

6. Алексеев В.Е., Таланов В.А. Графы и алгоритмы. Структуры данных. Модели вычислений БИНОМ. Лаборатория знаний, Интернет-университет информационных технологий - ИНТУИТ.ру, 2006

7. Костюкова Н.И. Графы и их применение. Комбинаторные алгоритмы для программистов БИНОМ. Лаборатория знаний, Интернет-университет информационных технологий - ИНТУИТ.ру, 2007