Рrogram Sort_Obmen;
var а: array of integer;
n, i, k, x: integer;
begin write ( "кількість елементів масиву");
for i: \u003d 1 to n do read ([i]);
for k: \u003d n-1 downto 1 do (кількість порівнюваних пар)
for i: \u003d 1 to k do if a [i]\u003e a then (міняємо місцями сусідні елементи)
for i: \u003d 1 to n do write (a [i], ""); (Упорядкований масив)
Поряд з сортуванням методом бульбашки, існують і деякі інші, більш ефективні методи сортування: швидке сортування, метод Шелла, сортування вставками ... Однак розглянутий алгоритм найбільш простий в реалізації і логічний.
Наведемо, проте, процедуру "швидкої сортування", яка крок за кроком шукає максимальний, другий за величиною і т.д. елементи і переносить: їх в кінець масиву. Зупинка циклу відбудеться тоді, коли при черговому проході не відбудеться (тобто, елементи встали на свої місця):
ім'яфала: FastSort.pas
Procedure FastSort (Var aa: Massive);
Var ii, kk, nn: byte;
For ii: \u003d 1 to nn-1 Do Begin
If (aa\u003e aa) Then Begin
Swap (aa, a);
У той час, як при сортуванні попередньому методом для масиву з 10 елементів знадобиться 9 проходів, для даного алгоритму це число може зменшитися. Наприклад, масив із значень (1, -3,7, -10,11,4, -6,2,5, -4) буде відсортований за 8 проходів, а масив (1,4,3,2,4, 5,6,7,10,11) - всього за 1.
Дотримуючись схожою, логіці відсортуємо масив по зростанню:
ім'яфала: Sort_Inc.pas
Procedure Sort_Inc (Var aa: Massive);
For kk: \u003d 1 to n-1 Do Begin
For ii: \u003d 1 to n-kk Do Begin
If (aa\u003e aa) Then Begin
Swap (aa, a);
Обробка двовимірних масивів
Основні принципи введення двовимірних масивів багато в чому схожі з принципами введення одновимірних. При його описі можна засилати на введені як константи число рядків матриці MіN, наприклад
Type Matrix \u003d array of Real;
Var a, b, c, d: Matrix;
e: array of Byte;
Як і в разі одновимірного масиву, обробка його двовимірного родича може бути локальної або глобальної, глобальна - обробкою по індексу, за значеннями або комбінованої.
Зауважимо, що двовимірний масив завжди можна розгорнути в одновимірний, а одновимірний - згорнути в двовимірний. Розглянемо приклади розв'язання задач на практичному занятті.
Література Основна література
Ахметов К.С. Курс молодого бійця. Вид. 5-е. М., Комп'ютер-Прес, 1998..
Фігурне В.Е. IBM PC для користувача. Вид. 7-е. М., Инфра-М, 1997, і 1999.
Олександр Левін Самовчитель Роботи на комп'ютері 8-е видання Розділ «з чого складається комп'ютер." - Пітер, 2004 р
Електронне методичний посібник МГАПІ 2005 р
Алексєєв Є.Р., Чеснокова О.В., Павлиш В.Р., Славінська Л.Ф. Турбо Паскаль 7.0 2-е видання - NT Press, М., 2006 р
Коротаєв Д.Г. TURBO-PASCAL в прикладах і задачах. Навчальний посібник МГАПІ, М, 2000 г.
Програмування на мові Паскаль Задачник. Під редакцією О.Ф.Усковой - Питер, 2003 р
Фаронов В.В. Навчальний посібникTurbo- Pascal- Питер, 2007.
Відомі результати змагання 9 учасників зі стрільби. Розташувати дані результати в порядку зростання набраних при стрільбі очок.
Алгоритм вирішення даного завдання є найбільш складним з наведених вище прикладів і вимагає використання вкладених циклів.
Один із способів сортування масивів полягає в наступному. Спочатку перший елемент масиву в циклі порівнюється по черзі з усіма залишилися елементами. Якщо черговий елемент масиву менше за величиною, ніж перший, то ці елементи переставляються місцями. Порівняння триває далі вже для оновленого першого елемента. В результаті закінчення даного циклу буде знайдений і встановлений на перше місце самий найменший елемент масиву. Далі триває аналогічний процес вже для решти елементів масиву, тобто другий елемент порівнюється з усіма іншими і, при необхідності, переставляється з ними місцями. Після визначення і установки другого елемента масиву, даний процес триває для третього елемента, четвертого елемента і т.д. Алгоритм завершується, коли порівнюються і упорядковуються передостанній і останній з елементів масиву.
Програма реалізації викладеного алгоритму може мати наступний вигляд:
Program pr4;
Type STREL \u003d arrayof integer;
Var rez: strel;
i, j, s: integer;
For i: \u003d 1 to 9 do
writeln ( 'Введіть результати ", i," - го учасника ");
readln (rez [i]);
for i: \u003d 1 to 8 do
for j: \u003d i + 1 to 9 do
if rez [i]\u003e rez [j] then
s: \u003d rez [j];
rez [j]: \u003d rez [i];
rez [i]: \u003d s;
writeln ( 'Відсортовані по зростанню результати: ");
for i: \u003d 1 to 9 do write (rez [i]: 5, " ');
Тут STREL - тип масиву результатів стрільби учасників, rez [i] - змінна для опису результатів i-го учасника (i змінюється від 1 до 9). Допоміжна змінна s використовується при перестановці місцями елементів масиву.
Алгоритм сортування вибором в Turbo Pascal
Очевидно, що перше місце в масиві повинен зайняти мінімальний елемент масиву, друге - найменший з усіх інших, третій - найменший з решти і т.д.
Для цього необхідно виконати наступну послідовність дій:
1. Визначити мінімальний елемент масиву;
2. Поміняти його місцями з першим елементом;
3. Визначити мінімальний елемент серед решти;
4. Поміняти його місцями з другим елементом і т.д .;
Ця послідовність дій повинна виконуватися до тих пір, поки не буде визначено останній мінімальний елемент.
Даний спосіб називається сортування вибором.
Всю операцію по упорядкуванню масиву можна розбити на більш прості завдання і назвати сортуванням вибору.
Перша - пошук мінімального елемента. Пропонований фрагмент програми нагадає Вам, як це робиться.
min: \u003d m; (Припустимо, що 1-й елемент - мінімальний)
t: \u003d 1; (І його номер \u003d 1)
FOR i: \u003d 1 TO 30 DO
if m [i]\u003e
m [t]: \u003d m [i];
m [i]: \u003d buf;
END;
Описаний метод «сортування вибором» сортування масивів можна застосовувати як для сортування масивів по зростанню, так і для сортування масивів по спадаючій. Для цього просто необхідно визначати не мінімальний елемент масиву, а максимальний. У тексті програми це виражається заміною в деяких місцях знака "".
41. Сила-силенна в Паскалі
безліч - це структурований тип даних, що представляє собою набір взаємозалежних по будь-якою ознакою або групі ознак об'єктів, які можна розглядати як єдине ціле. Кожен об'єкт в безлічі називається елементом множини.
Всі елементи множини повинні належати одному з порядкових типів, що містить не більше 256 значень. Цей тип називається базовим типом множини. Базовий тип задається діапазоном або перерахуванням.
Область значень типу безліч - набір всіляких підмножин, складених з елементів базового типу. У виразах на мові Паскаль значення елементів множини вказуються в квадратних дужках: [ "а", "b", "с"], [ "a" .. "z"].
Якщо безліч не має елементів, воно називається порожнім і позначається як. Кількість елементів множини називається його потужністю.
Безліч може приймати всі значення базового типу. Базовий тип не повинен перевищувати 256 можливих значень. Тому базовим типом множини можуть бути byte, char, boolean і похідні від них типи.
Безліч в пам'яті зберігається як масив бітів, в якому кожен біт вказує чи є елемент належить оголошеному безлічі чи ні. Максимальне число елементів безлічі 256, а дані типу безліч можуть займати не більше 32 байт.
Число байтів, що виділяються для даних типу безліч, обчислюється за формулою:
ByteSize \u003d (max div 8) - (min div 8) + 1,
де max і min - верхня і нижня межі базового типу даного безлічі.
Номер байта для конкретного елемента Е обчислюється за формулою:
ByteNumber \u003d (E div 8) - (min div 8),
номер біта всередині цього байта за формулою:
BitNumber \u003d E mod 8
Не має значення порядок запису елементів множини всередині конструктора. Наприклад, і - це еквівалентні множини.
Кожен елемент в множині враховується тільки один раз. Тому безліч еквівалентно.
Змінні множинного типу описуються так:
Var<идентификатор> : Set of<базовый тип>;
наприклад:
Var A, D: Set Of Byte; B: Set Of "a" .. "z"; C: Set Of Boolean;
Не можна вводити значення у множинну змінну процедурою введення і виводити процедурою виведення.
Множинна змінна може отримати конкретне значення тільки в результаті виконання оператора присвоювання:
<множественная переменная> := <множественное выражение>;
наприклад:
A: \u003d; B: \u003d [ "m", "n", "k"]; C: \u003d; D: \u003d A;
Крім того, вирази можуть включати в себе операції над множинами.
Операції над множинами
об'єднанням двох множин A і B називається множина, що складається з елементів, що входять хоча б в одне з множин A чи B. Знак операції об'єднання в Паскалі «+».
1) + \u003d\u003e 2) + [ 'a' .. 'z'] + [ 'A' .. 'E', 'k'] \u003d\u003e [ 'A' .. 'E', 'a' .. 'z'] 3) + \u003d\u003e
перетином двох множин A і B називається множина, що складається з елементів, одночасно входять в безліч A і в безліч B.
Знак операції перетину в Паскалі «*»
1) * \u003d\u003e 2) [ 'a' .. 'z'] * [ 'A' .. 'E', 'k'] \u003d\u003e [ 'k'] 3) * \u003d\u003e
різницею двох множин A і B називається множина, що складається з елементів множини A, що не входять в безліч B.
1a) - \u003d\u003e 1b) - \u003d\u003e 2a) [ 'a' .. 'z'] - [ 'A' .. 'E', 'k'] \u003d\u003e [ 'a' .. 'j', ' i '..' z '] 2b) [' A '..' E ',' k '] \u200b\u200b- [' a '..' z '] \u003d\u003e [' A '..' E '] 3a) - \u003d\u003e 3b) - \u003d\u003e
операція входження. Це операція, що встановлює зв'язок між безліччю і скалярною величиною, тип якої збігається з базовим типом множини. Якщо x - така скалярна величина, а M - безліч, то операція входження записується так: x in M.
Результат - логічна величина true, якщо значення x входить в безліч M, і false - в протилежному випадку.
Наприклад, 4 in - true, 5 in - false.
Використовуючи дану операцію, можна не тільки працювати з елементами безлічі, але і, навіть якщо в рішенні завдання явно не використовуються безлічі, деякі логічні вирази можна записати більш лаконічно.
1) Натуральне число n є двозначним. замість виразу (N\u003e \u003d 10) and (n<=99) можна записати n in.
2) Символ c є російською буквою. замість виразу (C\u003e \u003d 'А') and (c<= ‘Я’) or (c>\u003d 'А') and (c<=‘п’) or (c>\u003d 'Р') and (c<=‘я’) пишемо c in [ 'А' .. 'Я', 'а' .. 'п', 'р' .. 'я'] і т.д.
Додати новий елемент в безліч можна з використанням операції об'єднання. Наприклад, a: \u003d a + Для цих же цілей в Turbo Pascal 7.0 призначена процедура Include: include (M, A) M - безліч, A - змінна того ж типу, що й елементи безлічі M. Той же приклад можна записати так: Include (a, 5)
Виключити елемент з безлічі можна за допомогою операції «різниця множин». Наприклад, a: \u003d a- Для цих же цілей в Turbo Pascal 7.0 призначена процедура Exclude: exclude (M, A) M - безліч, A - змінна того ж типу, що й елементи безлічі M. Той же приклад можна записати так: Exclude (a, 5)
Розглянемо кілька прикладів використання множин при вирішенні завдань.
Завдання 1. У місті є n вищих навчальних закладів, які виробляють закупівлю комп'ютерної техніки. Є шість комп'ютерних фірм: «Діалог», «Avicom», «Нета», «Сервер», «Декада», «Dega.ru». Відповісти на наступні питання:
1) в яких фірмах закупівля проводилася кожним з вузів?
2) в яких фірмах закупівля проводилася хоча б одним з вузів?
3) в яких фірмах жоден з вищих навчальних закладів не закуповував комп'ютери?
Вирішимо задачу з використанням множин. Для зручності подальших маніпуляцій в порядку проходження Занумеруем комп'ютерні фірми, починаючи з одиниці. Занесемо інформації про місце закупівель комп'ютерів кожним з вузів в окреме безліч.
Відповідь на перше питання можна отримати, виконавши перетин всіх таких множин.
Відповідь на друге питання - результат об'єднання множин.
І, нарешті, на останній - різниця безлічі всіх фірм і безлічі фірм, де хоча б один вуз робив покупки.
Program ex_set_1; type firma \u003d set of 1..6; v \u003d array of firma; const f: array of string \u003d ( "Діалог", "Avicom", "Нетан", "Сервер", "Декада", "Dega.ru"); (процедура введення інформації про закупівлю комп'ютерів в черговий фірмі) procedure vvod (var a: firma); var i: byte; ans: 0..1; begin a: \u003d; for i: \u003d 1 to 6 do begin Write ( "Вуз купував комп'ютери в фірмі", f [i], "(1 - так, 0 - ні)?"); ReadLn (ans); if ans \u003d 1 then a: \u003d a + [i] end; end; (процедура виведення елементів масиву, номери яких містяться в безлічі) procedure Print (a: firma); var i: byte; begin for i: \u003d 1 to 6 do if i in a then write (f [i]: 10); writelnend; (Процедура, що дає відповідь на перше питання) procedure Rez1 (a: v; n: byte; var b: firma); var i: byte; begin b: \u003d; for i: \u003d 0 to n-1 do b: \u003d b * a [i]; end; (Процедура, що дає відповідь на друге питання) procedure Rez2 (a: v; n: byte; var b: firma); var i : byte; begin b: \u003d; for i: \u003d 0 to n-1 do b: \u003d b + a [i]; end; var a: v; n, i: byte; c: firma; begin write ( "Скільки вузів робили закупівлю?"); readln (n); for i: \u003d 0 to n-1 do vvod (a [i]); Rez1 (a, n, c); writeln ( "Кожен з вузів закупив комп'ютери в фірмах:"); Print (c); Rez2 (a, n, c); writeln ( "Хоча б один з вузів закупив комп'ютери в фірмах:"); Print (c); writeln ( "Жоден з вищих навчальних закладів не закупив комп'ютери в фірмах:"); Print (-c); end.
Завдання 2. згенерувати n множин (нумерацію почати з 1). Вивести елементи, які входять в усі безлічі з номерами, кратними трьом, але не входять у першу безліч.
Program ex_set_2; type mn \u003d set of byte; v \u003d array of mn; (процедура введення інформації в чергове безліч) procedure vvod (var a: mn); var i, n, vsp: byte; begin a: \u003d; n: \u003d 1 + random (200); for i: \u003d 1 to n do begin vsp: \u003d random (256); a: \u003d a + end; end; (процедура виведення елементів множини) procedure Print (a: mn); var i: byte; begin for i: \u003d 0 to 255 do if i in a then write (i: 4); writelnend; (Процедура, що дає відповідь на питання) procedure Rez (a: v; n: byte; var b: mn); var i: byte; begin b: \u003d; i: \u003d 3; while i<= n do begin b:= b * a[i]; i:= i + 3 end; b:= b - aend;var a: v; n, i: byte; c: mn;begin randomize; write("Сколько множеств? "); readln(n); for i:= 1 to n do begin vvod(a[i]); print (a[i]) end; Rez(a, n, c); Print(c);end.
Program ex_set_3; var m: set of char; s: string; i: byte; begin write ( "Введіть рядок:"); readln (s); m: \u003d; i: \u003d 1; while i<= length(s) do if s[i] in m then delete(s, i, 1) else begin m:=m+]; i:= i + 1 end; writeln(s)end.
42. Програма пошуку кількості певних символів в тексті.
Тут представлені найбільш часто використовувані функції. Наведемо приклад програми, яка визначає кількість символів і слів в довільній рядку символів.
program pr28;
const YES \u003d 1; (Константи, що визначає чи є)
NO \u003d 0; (Поточний символ елементом слова)
str: string;
nw, (Кількість слів)
nc, (Кількість символів)
inword: integer; (Змінні, пpинимающего значення
констант YES або NO)
i: integer;
writeln ( "Введіть стpоку символів:");
read (str);
nw: \u003d 0; nc: \u003d 0; inword: \u003d NO;
for i: \u003d 1 to length (str) do
nc: \u003d nc + 1;
if str [i] in [ ":", ".", ",", "" ","! ","? ","; "," "] (Якщо pазделітель,)
then inword: \u003d NO (то поточний символ поза слова)
if inword \u003d NO then
begin inword: \u003d YES;
nw: \u003d nw + 1;
writeln ( "nc \u003d", nc, "nw \u003d", nw);
43. Символьний тип даних в мові Турбо-Паскаль.
Сортування масиву - це процес розподілу всіх елементів в певному порядку. Дуже часто це буває корисним. Наприклад, у вашій поштовій скриньці електронні листи відображаються в залежності від часу отримання; нові листи вважаються більш доречними, ніж ті, які ви отримали півгодини, годину, два або день назад; коли ви переходите до свого списку контактів, імена зазвичай знаходяться в алфавітному порядку, тому що так легше щось знайти. Всі ці випадки включають в себе сортування даних перед їх фактичним виведенням.
Як працює сортування?
Сортування даних може зробити пошук всередині масиву більш ефективним не тільки для людей, а й для комп'ютерів. Наприклад, розглянемо випадок, коли нам потрібно дізнатися, чи відображається певний ім'я в списку імен. Щоб це дізнатися, потрібно перевірити кожен елемент масиву на відповідність з нашим значенням. Пошук в масиві з безліччю елементів може виявитися занадто неефективним (витратним).
Однак, припустимо, що наш масив з іменами відсортований в алфавітному порядку. Тоді наш пошук починається з першої літери нашого значення і закінчується буквою, яка йде наступною за алфавітом. У такому випадку, якщо ми дійшли до цієї букви і не знайшли ім'я, то точно знаємо, що воно не знаходиться в іншій частині масиву, так як в алфавітному порядку нашу букву ми вже пройшли!
Не секрет, що є алгоритми пошуку всередині відсортованих масивів і трохи краще. Використовуючи простий алгоритм, ми можемо шукати певний елемент в відсортованому масиві, що містить 1 000 000 елементів, використовуючи всього лише 20 порівнянь! Недоліком, звичайно ж, є те, що сортування масиву з такою величезною кількістю елементів - справа порівняно витратна, і воно точно не виконується заради одного пошукового запиту.
У деяких випадках сортування масиву робить пошук непотрібним. Наприклад, ми шукаємо найкращий результат студента за тест. Якщо маса не впорядкований, то нам доведеться переглянути кожен елемент масиву, щоб знайти найвищу оцінку. Якщо ж масив відсортований, то найвища оцінка буде перебувати або на першій позиції, або на останній (в залежності від методу сортування масиву: в порядку зростання або в порядку убування), тому нам не потрібно шукати взагалі!
Сортування зазвичай виконується шляхом повторного порівняння пар елементів масиву і заміни значень, якщо вони відповідають певним критеріям. Порядок, в якому ці елементи порівнюються, залежить від того, який алгоритм сортування використовується. Критерії складаються з того, як буде сортуватися масив (наприклад, в порядку зростання або в порядку убування).
Щоб поміняти два елементи місцями, ми можемо використовувати функцію std :: swap () зі стандартної бібліотеки C ++, яка визначена в algorithm. У C ++ 11 std :: swap () був перенесений в заголовки utility:
#include
#include #include int main () int a \u003d 3; int b \u003d 5; std :: cout<< "Before swap: a = " << a << ", b = " << b << "\n" ; std :: swap (a, b); // міняємо місцями значення змінних a і b std :: cout<< "After swap: a = " << a << ", b = " << b << "\n" ; |
Результат виконання програми вище:
Before swap: a \u003d 3, b \u003d 5
After swap: a \u003d 5, b \u003d 3
Після виконання операції заміни значення змінних a і b помінялися місцями.
Сортування масивів методом вибору
Існує безліч способів сортування масивів. Сортування масивів методом вибору, мабуть, найпростіша для розуміння, хоч і одна з найбільш повільних.
для сортування масиву методом вибору від найменшого до найбільшого елемента виконуються наступні кроки:
Починаючи з елемента під індексом 0, шукаємо в масиві найменше значення.
Знайдене значення міняємо місцями з нульовим елементом.
Повторюємо кроки №1 і №2 вже для наступного індексу в масиві.
Іншими словами, ми шукаємо найменший елемент в масиві і переміщаємо його на перше місце. Потім шукаємо другий найменший елемент і переміщаємо його вже на друге місце після першого найменшого елемента. Цей процес триває до тих пір, поки в масиві не закінчаться невідсортовані елементи.
Ось приклад роботи цього алгоритму в масиві з 5-ма елементами:
{ 30, 50, 20, 10, 40 }
Спочатку шукаємо найменший елемент, починаючи з індексу 0:
{ 30, 50, 20, 10 , 40 }
Потім міняємо місцями найменший елемент з елементом під індексом 0:
{ 10 , 50, 20, 30 , 40 }
Тепер, коли перший елемент масиву відсортований, ми його ігноруємо. Шукаємо наступний найменший елемент, але вже починаючи з індексу 1:
{ 10 , 50, 20 , 30, 40 }
І міняємо його місцями з елементом під індексом 1:
{ 10 , 20 , 50 , 30, 40 }
Тепер ми можемо ігнорувати перші два елементи. Шукаємо наступний найменший елемент, починаючи з індексу 2:
{ 10 , 20 , 50, 30 , 40 }
І міняємо його місцями з елементом під індексом 2:
{ 10 , 20 , 30 , 50 , 40 }
Шукаємо наступний найменший елемент, починаючи з індексу 3:
{ 10 , 20 , 30 , 50, 40 }
І міняємо його місцями з елементом під індексом 3:
{ 10 , 20 , 30 , 40 , 50 }
Шукаємо наступний найменший елемент, починаючи з індексу 4:
{ 10 , 20 , 30 , 40 , 50 }
І міняємо його місцями з елементом під індексом 4 (виконується самозамена, тобто нічого не робимо):
{ 10 , 20 , 30 , 40 50 }
{ 10, 20, 30, 40, 50 }
Зверніть увагу, останнім порівняння завжди буде поодиноким (тобто самозамена), що є зайвою операцією, тому, фактично, ми можемо зупинити виконання сортування перед останнім елементом масиву.
Сортування масивів методом вибору в C ++
Ось як цей алгоритм реалізований в C ++:
#include
#include #include int main () const int length \u003d 5; // Перебираємо кожен елемент масиву // (крім останнього, він уже буде впорядкований до того часу, коли ми до нього доберемося) < length - 1 ; ++ startIndex ) // В змінної smallestIndex зберігається індекс найменшого значення, яке ми знайшли в цій ітерації // Починаємо з того, що найменший елемент в цій ітерації - це перший елемент (індекс 0) int smallestIndex \u003d startIndex; // Потім шукаємо елемент поменше в іншій частині масиву < length ; ++ currentIndex ) // Якщо ми знайшли елемент, який менше нашого найменшого елемента, if (array [currentIndex]< array [ smallestIndex ] ) // то запам'ятовуємо його smallestIndex \u003d currentIndex; // smallestIndex тепер найменший елемент // Міняємо місцями наше початкове найменше число з тим, яке ми виявили std :: swap (array [startIndex], array [smallestIndex]); // Тепер, коли весь масив відсортований - виводимо його на екран for (int index \u003d 0; index< length ; ++ index ) std :: cout<< array [ index ] << " " ; return 0; |
Найбільш заплутаною частиною цього алгоритму є всередині іншого циклу (так званий вкладений цикл). Зовнішній цикл (startIndex) перебирає елементи один за іншим (по черзі). У кожній ітерації зовнішнього циклу внутрішній цикл (currentIndex) використовується для пошуку найменшого елемента серед елементів, які залишилися в масиві (починаючи зі startIndex + 1). smallestIndex відстежує індекс найменшого елемента, знайденого внутрішнім циклом. Потім smallestIndex змінюється значенням з startIndex. І, нарешті, зовнішній цикл (startIndex) передає цей елемент, і процес повторюється.
Підказка: Якщо у вас виникли проблеми з розумінням того, як працює програма вище, то спробуйте записати її виконання на листку паперу. Запишіть початкові (невідсортовані) елементи масиву горизонтально в рядку у верхній частині листа. Намалюйте стрілки, що вказують, які елементи є startIndex, currentIndex і smallestIndex на даний момент. Прокрутіть виконання програми вручну і перемалюють стрілки у міру зміни індексів. Після кожної ітерації зовнішнього циклу намалюйте новий рядок, що показує поточний стан масиву (розташування його елементів).
Сортування тексту виконується за допомогою того ж алгоритму. Просто змініть тип масиву з -а в і Ініціалізуйте його за допомогою відповідних значень.
std :: sort ()
Оскільки операція сортування масивів дуже поширена, то стандартна бібліотека C ++ надає вбудовану функцію сортування - std :: sort (). Вона знаходиться в заголовки algorithm і викликається наступним чином:
#include
#include #include int main () const int length \u003d 5; int array [length] \u003d (30, 50, 20, 10, 40); std :: sort (array, array + length); for (int i \u003d 0; i< length ; ++ i ) std :: cout<< array [ i ] << " " ; return 0; |
тест
завдання №1
Напишіть на листку паперу виконання сортування наступного масиву методом вибору (так як ми це робили вище):
{30, 60, 20, 50, 40, 10}
відповідь №1
30 60 20 50 40 10
10
60 20 50 40 30
10 20
60
50 40 30
10 20 30
50 40 60
10 20 30 40
50
60
10 20 30 40 50
60 (самозамена)
10 20 30 40 50 60
(Самозамена)
завдання №2
Перепишіть код програми з підзаголовка «Сортування масивів методом вибору в C ++» так, щоб сортування виконувалася в порядку убування (від найбільшого числа до найменшого). Хоча це може здатися складним на перший погляд, але, насправді, це дуже просто.
відповідь №2
Просто змініть:
If (array< array)
if (array [currentIndex]< array [ smallestIndex ] ) |
If (array\u003e array)
if (array [currentIndex]\u003e array [smallestIndex]) |
Також smallestIndex слід перейменувати в largestIndex:
#include
#include #include int main () const int length \u003d 5; int array [length] \u003d (30, 50, 20, 10, 40); // Перебираємо кожен елемент масиву, крім останнього for (int startIndex \u003d 0; startIndex< length - 1 ; ++ startIndex ) // largestIndex - це індекс найбільшого елемента, який ми виявили досі int largestIndex \u003d startIndex; // Перебираємо кожен елемент масиву починаючи з startIndex + 1 for (int currentIndex \u003d startIndex + 1; currentIndex< length ; ++ currentIndex ) // Якщо поточний елемент більший за наш найбільшого елемента, if (array [currentIndex]\u003e array [largestIndex]) // то це новий найбільший елемент в цій ітерації largestIndex \u003d currentIndex; // Міняємо місцями наше стартове число з виявленим найбільшим елементом std :: swap (array [startIndex], array [largestIndex]); // Виводимо відсортований масив на екран for (int index \u003d 0; index< length ; ++ index ) std :: cout<< array [ index ] << " " ; return 0; |
завдання №3
Це завдання вже трохи складніше.
Ще одним простим методом сортування елементів є «Сортування бульбашкою» (Або ще «Бульбашкова сортування»). Суть полягає в порівнянні пари значень, які знаходяться поруч, і, якщо задоволені задані критерії, значення з цієї пари міняються місцями. І таким чином елементи «скачуть бульбашкою» до кінця масиву. Хоча є кілька способів оптимізувати сортування бульбашкою, в цьому завданні ми будемо дотримуватися неоптимізованою версії, так як вона простіше.
При неоптимізованою версії сортування бульбашкою виконуються наступні кроки для сортування масиву від найменшого до найбільшого значення:
Порівнюється елемент масиву під індексом 0 з елементом масиву під індексом 1. Якщо елемент під індексом 0 більше елемента під індексом 1, то значення міняються місцями.
Потім ми подорожуємо до наступної пари значень: елемент під індексом 1 і елемент під індексом 2 і так до тих пір, поки не досягнемо кінця масиву.
Повторюємо крок №1 і крок №2 до тих пір, поки весь масив НЕ БУДЕ відсортований.
Напишіть програму, яка сортує наступний масив методом бульбашки відповідно до правил вище:
const int length (9); int array \u003d (7, 5, 6, 4, 9, 8, 2, 1, 3);
const int length (9); |
В кінці програми виведіть відсортовані елементи масиву.
Підказка: Якщо ми можемо впорядкувати тільки один елемент за одну ітерацію, то це означає, що нам потрібно буде повторити виконання циклу стільки раз, скільки є чисел в нашому масиві (його довжина), щоб гарантувати виконання сортування всього масиву.
відповідь №3
#include
#include #include int main () const int length (9); int array [length] \u003d (7, 5, 6, 4, 9, 8, 2, 1, 3); for (int iteration \u003d 0; iteration< length - 1 ; ++ iteration ) // Перебираємо кожен елемент масиву до останнього елемента (НЕ включно) // Останній елемент не має пари для порівняння for (int currentIndex \u003d 0; currentIndex< length - 1 ; ++ currentIndex) { // Якщо поточний елемент більше елемента після нього, то міняємо їх місцями if(array[ currentIndex] > array[ currentIndex+ 1 ] ) std:: swap(array[ currentIndex] , array[ currentIndex+ 1 ] ) ; } } // Виводимо відсортований масив на екран for(intindex= 0 ; index< length; ++ index) std:: cout<< array[ index] << " " ; return0 ; } |
завдання №4
Реалізуйте наступні два рішення оптимізації алгоритму сортування бульбашкою, який ви написали в попередньому завданні:
Зверніть увагу, з кожним виконанням сортування бульбашкою найбільше значення в масиві «пузириться» до кінця. Після першої ітерації останній елемент масиву вже відсортований. Після другої ітерації відсортований передостанній елемент масиву і т.д. З кожною новою итерацией нам не потрібно перевіряти ще раз елементи, які вже були відсортовані. Змініть свій цикл так, щоб не перевіряти елементи, які вже були відсортовані.
У статті розглянуті одні з найпопулярніших алгоритмів сортування для масивів, що застосовуються як практично, так і в навчальних цілях. Відразу хочу обмовитися, що всі розглянуті алгоритми повільніше, ніж метод класичної сортування масиву через список значень, але тим не менш, заслуговують на увагу. Тексту виходить багато, тому по кожному алгоритму описую найголовніше.
1.Алгорітм "Сортування вибором".
Є одним з найпростіших алгоритмів сортування масиву. Сенс в тому, щоб йти по масиву і кожен раз шукати мінімальний елемент масиву, обмінюючи його з початковим елементом невідсортоване частини масиву. На невеликих масивах може виявитися навіть ефективніше, ніж більш складні алгоритми сортування, але в будь-якому випадку програє на великих масивах. Число обмінів елементів в порівнянні з "бульбашковим" алгоритмом N / 2, де N - число елементів масиву.
алгоритм:
1. Знаходимо мінімальний елемент в масиві.
2. Міняємо місцями мінімальний і перший елемент місцями.
3. Знову шукаємо мінімальний елемент в невідсортоване частини масиву
4. Міняємо місцями вже другий елемент масиву і мінімальний знайдений, тому як перший елемент масиву є відсортованої частиною.
5. Шукаємо мінімальні значення і міняємо місцями елементи, поки маса не буде відсортований до кінця.
// Сортування вибором (--- Функція СортіровкаВибором (Знач Масив) Мін \u003d 0; Для i \u003d 0 За Массів.ВГраніца () Цикл Мін \u003d i; Для j \u003d i + 1 ПО Массів.ВГраніца () Цикл // Шукаємо мінімальний елемент в масиві Якщо Масив [j]< Массив[Мин] Тогда Мин = j; КонецЕсли; КонецЦикла; Если Массив [Мин] = Массив [i] Тогда //Если мин. элемент массива = первому элементу неотс. части массива, то пропускаем. Продолжить; КонецЕсли; Смена = Массив[i]; //Производим замену элементов массива. Массив[i] = Массив[Мин]; Массив[Мин] = Смена; КонецЦикла; Возврат Массив; КонецФункции
2.Алгорітм "Сортування бульбашкою".
Мабуть найвідоміший алгоритм, який застосовується в навчальних цілях, для практичного ж застосування є занадто повільним. Алгоритм лежить в основі більш складних алгоритмів: "шейкерні сортування", "Пірамідальна сортування", "Швидка сортування". Примітно те, що один з найшвидших алгоритмів "Швидкий алгоритм" був розроблений шляхом модернізації одного з найгірших алгоритмів "Сортування бульбашкою". "Швидка" і "шейкерні" сортування будуть розглянуті далі. Сенс алгоритму полягає в тому, що самі "легкі" елементи масиву як би "спливають", а самі "важкі" "тонуть". Звідси і назва "Сортування бульбашкою"
алгоритм:
1. Кожен елемент масиву порівнюється з наступним і якщо елемент [i]\u003e елемент відбувається заміна. Таким чином самі "легкі" елементи "спливають" - переміщаються до початку списку, а найважчі "тонуть" - переміщаються до кінця.
2. Повторюємо Крок 1 n-1 раз, де n - Массів.Колічество ().
// Сортування бульбашкою (--- Функція СортіровкаПузирьком (Знач Масив) Для i \u003d 0 За Массів.ВГраніца () Цикл Для j \u003d 0 ПО Массів.Вграніца () - i - 1 Цикл Якщо Масив [j]\u003e Масив Тоді Заміна \u003d масив [j]; масив [j] \u003d масив; масив \u003d Заміна; КонецЕсли; КонецЦікла; КонецЦікла; Повернення масив; КонецФункціі // ---)
3.Алгорітм "шейкерні сортування" (Сортування перемішуванням, Двунаправленная бульбашкова сортування).
Алгоритм являє собою одну з версій попередньої сортування - "сортування бульбашкою". Головна відмінність в тому, що в класичній сортування бульбашкою відбувається односпрямоване рух елементів знизу - вгору, то в шейкерні сортування спочатку відбувається рух знизу-вгорі, а потім зверху-вниз.
Алгоритм такий же, що і у бульбашкового сортування + додається цикл пробігу зверху-вниз.
У наведеному нижче прикладі, є удосконалення в шейкерні сортуванні. На відміну від класичної, використовується в 2 рази менше ітерацій.
// Сортування перемішування (Шейкер-Сортування) (--- Функція СортіровкаПеремешіваніем (Знач Масив) Для i \u003d 0 ПО Массів.ВГраніца () / 2 Цикл Нітерой \u003d 0; конІтер \u003d Массів.ВГраніца (); Поки Нітерой Масив [Нітерой + 1] Тоді Заміна \u003d Масив [Нітерой]; Масив [Нітерой] \u003d Масив [Нітерой + 1]; Масив [Нітерой + 1] \u003d Заміна; КонецЕсли; Нітерой \u003d Нітерой + 1; // Рухаємо позицію на крок вперед // Проходимо з кінця Якщо Масив [конІтер - 1]\u003e Масив [конІтер] Тоді Заміна \u003d Масив [конІтер - 1]; Масив [конІтер-1] \u003d Масив [конІтер]; Масив [конІтер] \u003d Заміна; КонецЕсли; конІтер \u003d конІтер - 1; // Рухаємо позицію на крок назад КонецЦікла; КонецЦікла; Повернення Масив; КонецФункціі // ---)
4. Алгоритм "Гном сортування".
Алгоритм так дивно названий завдяки голландському вченому Діку Грунь.
Сортування гнома заснована на техніці, використовуваної звичайним голландським садовим гномом (нід. Tuinkabouter). Це метод, яким садовий гном сортує лінію квіткових горщиків. По суті він дивиться на наступний і попередній садові горщики: якщо вони в правильному порядку, він крокує на один горщик вперед, інакше він змінює їх місцями і крокує на один горщик назад. Граничні умови: якщо немає попереднього горщика, він крокує вперед; якщо немає такого горщика, він закінчив.
Дік Грун
Ось власне і все опис алгоритму "Гном сортування". Що цікаво, алгоритм не містить вкладених циклів, а сортує весь масив за один прохід.
// гномів сортування (--- Функція ГномьяСортіровка (Знач Масив) i \u003d 1; j \u003d 2; Поки i< Массив.Количество() Цикл // Сравнение < - Сортировка по возрастанию, > - по спадаючій Якщо Масив i \u003d j; j \u003d j + 1; Інакше Заміна \u003d Масив [i]; Масив [i] \u003d масив; Масив \u003d Заміна; i \u003d i - 1; Якщо i \u003d 0 Тоді i \u003d j; j \u003d j + 1; КонецЕсли; КонецЕсли; КонецЦікла; Повернення Масив; КонецФункціі // ---)
5. Алгоритм "Сортування вставками".
Являє собою простий алгоритм сортування. Сенс полягає в тому, що на кожному кроці ми беремо елемент, шукаємо для нього позицію і вставляємо в потрібне місце.
Елементарний приклад: При грі в дурня, ви тягнете з колоди карту і вставляєте її в відповідне місце по зростанню в наявних у вас картах. або
в магазині вам дали здачу 550 рублів-одна купюра 500, інша 50. заглядати в гаманець, а там купюри гідністю 10,100,1000. Ви вставляєте купюру
достоінсвом 50р. між купюрами номіналом 10р і 100р, а купюру в 500 рублів між купюрами 100р і 1000р. Виходить 10,50,100,500,1000 - Ось вам
і алгоритм "Сортування вставками".
Таким чином з кожним кроком алгоритму, вам необхідно впорядкувати подмассів даних і вставити значення в потрібне місце.
// Сортування вставками (--- Функція СортіровкаВставкамі (Знач Масив) Для i \u003d 0 За Массів.ВГраніца () - 1 Цикл Ключ \u003d i + 1; Заміна \u003d Масив [Ключ]; j \u003d i + 1; Поки j\u003e 0 І Заміна< Массив Цикл Массив[j] = Массив; Замена = j - 1; Ключ = j - 1; j = j - 1; КонецЦикла; Массив[Ключ] = Замена; КонецЦикла; Возврат Массив; КонецФункции //---}
6. Алгортім "Сортування злиттям".
Цікавий в плані реалізації та ідеї алгоритм. Сенс його в тому, щоб розбивати масив на подмассіви, поки довжина кожного подмассіва не дорівнюватиме 1. Тоді ми стверджуємо, що такий подмассів відсортований. Потім зливаємо отримані подмассіви воєдино, одночасно порівнюючи і сортуючи поелементно значення подмассивов.
p / s не зміг вставити сюди малюнок з більш наочною схемою, постійно розмазується. Зате добре видно в блоці скріншотів внизу. Можна подивитися як працює алгоритм.
// Сортування злиттям (---
Функція СортіровкаСліяніем (Знач Масив) Якщо Массів.Колічество () \u003d 1 Тоді Повернення Масив; КонецЕсли; ТочкаРазрив \u003d Массів.Колічество () / 2; лМассів \u003d Новий Масив; прМассів \u003d Новий Масив; Для Сч \u003d 0 ПО Массів.ВГраніца () Цикл Якщо Сч< ТочкаРазрыв Тогда лМассив.Добавить(Массив[Сч]); Иначе прМассив.Добавить(Массив[Сч]); КонецЕсли; КонецЦикла; Возврат Слияние(СортировкаСлиянием(лМассив),СортировкаСлиянием(прМассив)); КонецФункции Функция Слияние(массив1,массив2) a = 0; b = 0; слМассив = Новый Массив; Для Сч = 0 ПО (Массив1.Количество() + Массив2.Количество())-1 Цикл слМассив.Добавить(); КонецЦикла; Для i = 0 ПО (массив1.Количество() + массив2.Количество())-1 Цикл Если b < массив2.Количество() И a < массив1.Количество() Тогда Если (массив1[a] > массів2 [b]) І (b< массив2.Количество()) Тогда слМассив[i] = массив2[b]; b = b + 1; Иначе слМассив[i] = массив1[a]; a = a + 1; КонецЕсли; Иначе Если b < массив2.количество() Тогда слМассив[i] = массив2[b]; b = b + 1; Иначе слМассив[i] = массив1[a]; a = a + 1; КонецЕсли; КонецЕсли; КонецЦикла; Возврат слМассив; КонецФункции //---}
7. Алгортім "Сортування Шелла".
Алгоритм названий так на честь американського вченого Дональда Шелла. За своєю суттю цей алгоритм є вдосконаленим алгоритмом "Сортування вставками". Сенс алгоритму полягає в тому, щоб порівнювати не тільки елементи, що стоять поруч один з одним, але і на деякій відстані. Спочатку вибирається Крок - якийсь проміжок, через який будуть порівнюватися елементи масиву на кожній ітерації. Зазвичай його визначають так:
Для першої ітерації Крок \u003d Цілий (Массів.Колічество () / 2), для подальших Крок \u003d Цілий (Крок / 2). Тобто поступово крок скорочується і коли Крок дорівнюватиме 1 відбудеться останні порівняння і масив буде відсортований.
приклад:
Дан масив (10,5,3,1,14,2,7,12).
1. Крок \u003d 4.
Сортуємо простими вставками кожні 4 групи по 2 елементи (10,14) (5,2) (3,7) (1,12)
10 ,2 ,3 ,1,14 ,5 ,7 ,12
2. Крок \u003d 2
Сортуємо простими вставками кожні 2 групи по 4 елементи (10,3,14,7) (2,1,5,12)
3 ,1 ,7 ,2 ,10 ,5 ,14 ,12
3. Крок \u003d 1
Сортуємо простими вставками кожну 1 групу по 8 елементів.
1,2,3,5,7,10,12,14
// Сортування Шелла (--- Функція СортіровкаШелла (Знач Масив) Крок \u003d Цілий (Массів.Колічество () / 2); Поки Крок\u003e 0 Цикл i \u003d 0; Поки i< (Массив.Количество() - Шаг) Цикл j = i; Пока j >\u003d 0 І Масив [j]\u003e Масив Цикл Заміна \u003d Масив [j]; Масив [j] \u003d масив; Масив \u003d Заміна; j \u003d j - 1; Якщо ПріменітьОтображеніеСортіровкі Тоді ОтобразітьДіаграммуСортіровкі (Масив); КонецЕсли; КонецЦікла; i \u003d i + 1; КонецЦікла; Крок \u003d Цілий (Крок / 2); ОбработкаПрериваніяПользователя (); КонецЦікла; Повернення Масив; КонецФункціі // ---)
8. Алгортім "Швидке сортування".
Найбільш популярний і застосовуваний алгоритм на практиці. Є одним з найбільш ефективних алгоритмів сортування даних.
Вся суть алгоритму зводиться до того, щоб розбити складне завдання на маленькі і вирішити їх окремо. Вибирається якась опорна точка і все значення які менше перекидаються вліво, всі інші вправо. Далі для кожної отриманої частини виполняеться теж саме, до тих пір поки дробити частини вже не можна. В кінці ми отримуємо безліч відсортованих частин, які необхідно просто склеїти в 1 ціле.
// Алгоритм "Швидке сортування" (Процедура б_Сортіровка (Масив, НіжнійПредел, ВерхнійПредел) i \u003d НіжнійПредел; j \u003d ВерхнійПредел; m \u003d Масив [Цілий ((i + j) / 2)]; Поки Істина Цикл Поки Масив [i]< m Цикл i = i + 1; КонецЦикла; Пока Массив[j] > m Цикл j \u003d j - 1; КонецЦікла; Якщо i\u003e j Тоді Перервати; КонецЕсли; КонецЦікла; якщо НіжнійПредел< j Тогда б_Сортировка(Массив,НижнийПредел,j); КонецЕсли; Если i < ВерхнийПредел Тогда б_Сортировка(Массив,i,ВерхнийПредел); КонецЕсли; КонецПроцедуры Функция БыстраяСортировка(Массив) НижняяГраница = 0; ВерхняяГраница = Массив.ВГраница(); б_Сортировка(Массив,НижняяГраница,ВерхняяГраница); Возврат Массив; КонецФункции //---}
9. Класична сортування масиву в 1с.
Передаємо масив в список значень. Сортуємо стандартним методом "Сортувати".
// Сортування списком значень (--- Функція СортіровкаСпіскомЗначеній (Знач Масив) мСпісокЗнч \u003d Новий СпісокЗначеній; мСпісокЗнч.ЗагрузітьЗначенія (Масив); мСпісокЗнч.СортіроватьПоЗначенію (НаправленіеСортіровкі.Возр); Повернення мСпісокЗнч.ВигрузітьЗначенія (); КонецФункціі // ---)
Все сортування можна прискорити розташувавши код в циклах в 1 рядок. Але для читабельності, залишив так.
Написав обробку в якій реалізовані всі перераховані вище алгоритми, також підтримується динамічна анімація процесу сортування (Крім стандартної сортування 1с) .
-При запуску обробки автоматично відбувається формування масиву випадкових чисел від 0 до 100 розмірністю 100 елементів.
-Для створення іншого масиву необхідно натиснути на кнопку "Створення ГСЧ масиву", також можна вибирати необхідний діапазон.
-Для включення динамічної анімації необхідно поставити галочку на "Показати сортування в діаграмі". Раджу на неефективних алгоритмах встановлювати галочку при розмірності масиву до 100 елементів, інакше постарієте чекати сортування :)
Динамічна отрисовка процесу сортування дуже сильно знижує продуктивність, зате наочно видно як працює алгоритм.
Рано чи пізно необхідність сортувати дані з масиву виникає у будь-якого програміста. Будь то висновок даних з бази в алфавітному порядку або сортування імен файлів за датою останньої зміни, можна здійснити завдяки вбудованим php функцій для сортування даних масиву. У даній статті продемонструю і поясню в прикладах як працюють такі функції як: sort (), rsort ().
функція; - Сортування масиву по зростанню і за алфавітом
структура:
($ Масив, $ Прапор);
Функція сортує заданий їй масив $ Масив по зростанню. Функція призначена для роботи зі списками. Списки це звичайні масиви, ключі яких починаються з нуля. Функції можна задати необов'язковий аргумент $ Прапор, який маніпулює тим як саме має відбуватися сортування. Розглянемо опис аргументу $ Прапор:
SORT_REGULAR - Сортування за замовчуванням роботи функції
SORT_NUMERIC - Сортування чисел, за зростанням
SORT_STRING - Сортування рядків, по алфавіту
Розглянемо приклад, у нас є масив де зберігаються в хаотичному вигляді дані про кількість пар студента в різні роки навчання.
";)?\u003e Результат роботи скрипта: Курс: 1 - 72 пар Курс: 2 - 83 пар Курс: 3 - 100 пар Якби ми не застосували функцію результат роботи був би таким: Курс: 1 - 83 пар Курс: 2 - 100 пар Курс: 3 - 72 пар
Сортування за алфавітом
Нижче наведено скрипт який сортує країни їх масиву в алфавітному порядку, другий аргумент функції ($ Прапор) не обов'язково ставити, тому що функція сама зрозуміє, що треба працювати з рядками.
";)?\u003e Результат роботи: Вірменія Італія Росія Японія
Функція rsort () - Сортування масиву за спаданням
функція є алогічною функції тільки сортує масиви по спадаючій. розглянемо структуру синтаксису:
($ Масив, $ Прапор);
Приклад для даної функції буде схожий на приклади вище наведені, крім одного, дані з масиву будуть відсортовані за спаданням. Створюємо масив з призами для тих хто займе 1-е, 2-е і 3-е місце в конкурсі.
";)?\u003e Результат виконання скрипта: 1 місце - приз: 2800 руб. 2 місце - приз: 1200 руб. 3 місце - приз: 500 руб.
