вступ

Сортування — це важлива операція в інформатиці, яка включає впорядкування елементів у певному порядку, наприклад у числовому або алфавітному порядку. Розроблено різні алгоритми сортування, кожен з яких має показники часу та ефективності. Лінійне сортування за часом — це підмножина алгоритмів сортування зі значною перевагою: вони можуть сортувати заданий набір елементів за лінійний час, час виконання лінійно збільшується зі збільшенням розміру вхідних даних.

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

1. Щоб визначити діапазон, визначте мінімальне та максимальне значення вхідного масиву.
2. Створіть робочий аркуш, ініціалізований розміром діапазону та нулями.
3. Перебирайте вхідний масив і збільшуйте кожен знайдений елемент.
4. Змініть робочий аркуш, підрахувавши сукупну суму, щоб отримати правильні позиції для кожного елемента.
5. Створіть вихідний масив такого ж розміру, як і вхідний масив.
6. Знову перемістіть вхідний масив, розмістивши кожен елемент у правильній позиції у вихідному масиві на основі аркуша.
7. Таблиця результатів тепер містить відсортовані елементи.

Основна перевага сортування за спаданням полягає в тому, що воно досягає лінійної часової складності O(n), що робить його дуже ефективним для великих розмірів вхідних даних. Однак його застосування обмежене сценаріями, де вибір вхідних елементів відомий заздалегідь і відносно невеликий.

сортування вставкою

Важливо відзначити, що інші алгоритми сортування, такі як швидке сортування або злиття, зазвичай мають часову складність O(n log n), що вважається ефективним для багатьох практичних застосувань. Алгоритми лінійного сортування часу, такі як числове сортування, надають альтернативу, коли певні обмеження або властивості вхідних даних дозволяють використовувати лінійну часову складність.

історія

Алгоритми лінійного сортування часу мають багату історію в інформатиці. Розвиток лінійного порядку часу можна простежити до середини 20 століття, і внесок вчених і математиків був значним. Одним із найперших алгоритмів лінійного сортування в часі є ковшове сортування, запропоноване Гарольдом Х. Сьюардом у 1954 році. ковшове сортування ділить вхідні елементи на кінцеву кількість ковшів, а потім сортує кожне відро окремо. Цей алгоритм має лінійну часову складність, якщо розподіл вхідних елементів є відносно рівномірним.

У 1959 році Кеннет Е. Айверсон запропонував радикальний алгоритм, який досягає лінійної часової складності. Radix сортує елементи за їх номерами або знаками від найменш значущого до найбільш значущого. Він використовує надійні алгоритми сортування, такі як числове або групове сортування, щоб сортувати елементи в кожній позиції цифри. Сортування за системою Radix стало популярним в епоху перфокарт і ранніх комп'ютерних систем. Однак найвідомішим алгоритмом лінійного сортування за часом є перерахування, представлене Гарольдом Х. Сьюардом і Пітером Еліасом у 1954 році, а пізніше незалежно від нього знову відкрито Гарольдом Х. «Боббі» Джонсоном у 1961 році. Числовому сортуванню приділено значну увагу.

Це особливо ефективно, коли діапазон вхідних елементів відомий і відносно невеликий. Історія лінійного сортування часу продовжилася з розвитком інших спеціалізованих алгоритмів. Наприклад, у 1987 році Ханан Самет запропонував двійкове сортування дерева розподілу, лінійний алгоритм сортування за часом для багатовимірних даних. Протягом багатьох років дослідники продовжували вивчати та вдосконалювати алгоритми лінійного планування, зосереджуючись на конкретних сценаріях і обмеженнях. Хоча такі алгоритми, як швидке сортування та злиття, ширше використовуються через їхню ефективність у більшій кількості сценаріїв, алгоритми лінійного сортування надають цінні альтернативи, коли певні обставини дозволяють використати складність лінійного часу. Загалом, історія лінійного сортування за часом характеризується пошуком ефективних алгоритмів, які можуть сортувати великі набори даних за лінійний час, долаючи обмеження алгоритмів сортування на основі порівняння. Внесок різних дослідників проклав шлях для розробки та розуміння цих спеціалізованих методів сортування.

Типи лінійного сортування часу

Існує кілька різних алгоритмів лінійного сортування часу. Два основних типи — це алгоритми на основі підрахунку та алгоритми на основі основ. Ось найпоширеніші алгоритми лінійного сортування часу, класифіковані за такими типами:

Алгоритми на основі підрахунку

Сортування на основі підрахунку:Counting-Based — це непорівняльний алгоритм сортування. Він підраховує появу кожного окремого елемента у вхідному масиві та використовує цю інформацію для визначення правильної позиції кожного елемента у відсортованому вихідному масиві. Сортування на основі підрахунку передбачає, що вхідні елементи є цілими чи можуть бути додані до цілих чисел.

Алгоритми на основі Radix

Основа сортування:Radix Sort — це алгоритм сортування без порівняння, який сортує елементи за їх номерами або символами. Він підраховує кожне число або знак в елементах від найменшого числа до найбільшого. Радикальна сортування передбачає, що вхідні елементи є цілими числами або рядками.Сортування відра:Bucket Sort є варіантом Radix Sort, який поділяє елементи на фіксовані групи на основі їх діапазону або розподілу. Кожен сегмент сортується окремо за допомогою іншого алгоритму сортування або рекурсивного bin-сортування.MSD (старша цифра) Сортування за основою:Сортування за принципом MSD — це варіант сортування за принципом, який починає сортувати елементи на основі їх найбільш значущих. Він рекурсивно ділить елементи на підгрупи на основі значення поточного числа та застосовує сортування за принципом MSD до кожної підгрупи, доки не буде підраховано всі числа.LSD (молодша значуща цифра) Сортування за основою:LSD Radix Sort — ще один варіант, який починає сортувати елементи на основі їх найменшого значення. Він рекурсивно сортує елементи на основі кожного числа від крайнього правого до крайнього лівого, створюючи відсортований результат. Алгоритми сортування як на основі підрахунку, так і на основі кореня досягають лінійної складності в часі, використовуючи специфічні властивості вхідних елементів, такі як їхній діапазон або структуру представлення (наприклад, числа або символи). Однак їх застосовність може відрізнятися в залежності від характеристик вхідних даних.

Переваги лінійного сортування часу

Алгоритми лінійного сортування за часом, такі як числове сортування, пропонують кілька переваг у конкретних сценаріях.

Ефективно для великих розмірів вхідних даних:Часова складність алгоритмів лінійного сортування часу дорівнює O(n), що означає, що час виконання лінійно збільшується із розміром вхідних даних. Це робить їх дуже ефективними для великих наборів даних порівняно з алгоритмами сортування на основі порівняння, такими як алгоритми швидкого сортування або злиття, які зазвичай мають часову складність O(n log n).Без операцій порівняння:Алгоритми сортування в лінійному часі, такі як сортування за перерахуванням, не покладаються на елементарне порівняння, натомість вони використовують певні атрибути або інформацію про вхідні елементи, такі як їх екстент або розподіл. Ця функція робить їх вигідними, коли вартість порівняння висока, наприклад для складних об’єктів або дорогих операцій порівняння.Придатність до конкретних вхідних властивостей:Алгоритми лінійного сортування часто мають конкретні вимоги або припущення щодо вхідних елементів. Наприклад, щоб обчислити порядок сортування, вам потрібно заздалегідь знати діапазон вхідних елементів. Коли ці умови виконуються, алгоритми лінійного сортування за часом можуть запропонувати значні переваги в продуктивності порівняно з алгоритмами загального сортування.Стабільний сорт:Багато алгоритмів лінійного сортування в часі, включно з числовим сортуванням і сортуванням за принципом, за своєю суттю стабільні. Узгодженість означає, що елементи з повторюваними ключами або значеннями зберігають відносний порядок у відсортованому виведенні. Це може бути критично важливим, коли сортуються об’єкти чи записи з декількома атрибутами або коли важливо зберегти вихідний порядок елементів однакової вартості.Простота використання:Алгоритми лінійного сортування за часом, такі як сортування за переліком, часто відносно прості у реалізації порівняно зі складнішими алгоритмами сортування на основі порівняння. Їх легше зрозуміти та налагодити, що робить їх придатними для ситуацій, де потрібні простота та ясність.

Недоліки лінійного сортування часу

Хоча лінійні алгоритми планування мають свої переваги, вони також мають певні обмеження та недоліки:

різниця між двома рядками python

Обмежувальні вимоги до вхідних даних:Алгоритми лінійного сортування часу часто мають конкретні вимоги або припущення щодо вхідних елементів. Наприклад, щоб обчислити порядок сортування, вам потрібно заздалегідь знати діапазон вхідних елементів. Це обмеження обмежує їх застосовність до ситуацій, коли ці умови виконуються. Вимоги до пам’яті можуть стати непрактичними або перевищити доступні ресурси, якщо діапазон великий або невідомий.Додаткові вимоги до місця:Деякі алгоритми лінійного сортування за часом, такі як числове сортування, потребують додаткового простору для зберігання інших масивів або структур даних. Необхідний простір часто пропорційний кількості вхідних елементів. Це може бути недоліком, коли використання пам’яті є проблемою, особливо під час роботи з великими наборами даних або обмеженими ресурсами пам’яті.Відсутність універсальності:Алгоритми лінійного сортування часу — це спеціалізовані алгоритми, розроблені для конкретних сценаріїв або обмежень. Вони можуть бути більш придатними та ефективними для загальних завдань сортування або різних розподілів вхідних даних. Алгоритми сортування на основі порівняння, такі як швидке сортування або злиття, більш універсальні та можуть обробляти ширший діапазон вхідних даних.Неефективно для малих діапазонів або розріджених даних:Алгоритми сортування в лінійному часі, такі як перерахування, найбільш ефективні, коли діапазон вхідних елементів невеликий і щільно розподілений. Якщо діапазон великий або дані розріджені (тобто лише кілька різних значень), алгоритм може заощадити час і зусилля на обробці порожніх або рідко заповнених частин вхідного діапазону.Обмежено певними типами даних:Алгоритми сортування в лінійному часі, такі як сортування за перерахуванням, в основному призначені для сортування невід’ємних цілих чисел або об’єктів «ключ-значення». Вони можуть бути непридатними для сортування інших типів даних, таких як числа з плаваючою комою, рядки або складні структури даних. Адаптація алгоритмів лінійного сортування за часом для обробки різних типів даних або спеціальних функцій порівняння може вимагати додаткової попередньої обробки або модифікацій.

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

Застосування алгоритмів лінійного сортування часу

Алгоритми лінійного сортування часу ефективні та мають багато застосувань у різних сферах. Ось кілька типових застосувань лінійного порядку часу:

Сортування малих цілих чисел:Алгоритми лінійного сортування за часом, такі як сортування за кількістю та сортування за основою, ідеально підходять для сортування масивів цілих чисел, коли діапазон значень дорівнює. Ці алгоритми досягають лінійної складності за часом, роблячи припущення щодо вхідних даних, що дозволяє їм обійти сортування на основі порівняння.Сортування рядків:Алгоритми лінійного сортування за часом також можна застосовувати для ефективного сортування рядків. Враховуючи унікальні властивості рядків, такі як їх довжина або символи, такі алгоритми, як Radix Sort, можуть досягти лінійної складності за часом під час сортування рядків.Функції бази даних:Сортування є важливою функцією алгоритмів лінійного сортування за часом, які можуть ефективно сортувати великі набори даних на основі певних стовпців або полів. Це забезпечує швидшу обробку запитів і кращу продуктивність операцій з базою даних.Створення гістограм:Гістограми необхідні для виконання різних статистичних завдань і завдань аналізу даних. Алгоритми лінійного сортування в часі, такі як числове сортування, можуть генерувати гістограми шляхом ефективного підрахунку появи елементів у наборі даних.Зовнішнє сортування:Техніка зовнішнього сортування використовується в сценаріях, коли дані не можуть повністю поміститися в пам’ять. Алгоритми лінійного сортування за часом, такі як External Radix Sort або External Counting Sort, можуть ефективно сортувати великі набори даних, що зберігаються на диску чи інших зовнішніх пристроях зберігання.Розклад подій:Алгоритми лінійного сортування часу можуть планувати події на основі часу їх початку або закінчення. Сортування подій у порядку зростання полегшує виявлення конфліктів, періодів, що збігаються, або пошуку наступного доступного періоду.Аналіз файлів журналу:Аналіз файлів журналу є поширеним завданням системного адміністрування та налагодження. Алгоритми лінійного сортування часу можна використовувати для сортування журналів на основі часових позначок, що полегшує ідентифікацію шаблонів, аномалій або пошук конкретних подій.Стиснення даних:Сортування відіграє важливу роль у різних методах стиснення даних. Алгоритми, такі як перетворення Берроуза-Вілера (BWT) або перетворення переходу на передній план (MTF), покладаються на лінійне впорядкування часу для перевпорядкування даних для підвищення ефективності стиснення. Це лише кілька прикладів застосування алгоритмів лінійного сортування часу.

Реалізація лінійного сортування часу в C++

Ось приклад програми, що реалізує Counting Sort, який є лінійним алгоритмом сортування за часом:

перерва java

 #include #include using namespace std; void countingSort(vector&amp; arr) { // Find the maximum element in the array int max_val = *max_element(arr.begin(), arr.end()); // Create a count array to store the count of each element vector count(max_val + 1, 0); // Count the occurrences of each element for (int num : arr) { count[num]++; } // Compute the prefix sum for (int i = 1; i <count.size(); i++) { count[i] +="count[i" - 1]; } create a sorted output array vector output(arr.size()); place the elements in order for (int i="arr.size()" 1;>= 0; i--) { output[count[arr[i]] - 1] = arr[i]; count[arr[i]]--; } // Copy the sorted elements back to the original array for (int i = 0; i <arr.size(); i++) { arr[i]="output[i];" } int main() vector arr="{4," 2, 8, 3, 1}; sort the array using counting countingsort(arr); print sorted cout << 'sorted array: '; for (int num : arr) ' endl; return 0; < pre> <p> <strong>Sample Output</strong> </p> <pre> Sorted array: 1 2 2 3 3 4 8 </pre> <p>This indicates that the input array has been sorted in ascending order using the Counting Sort algorithm, resulting in the sorted array [1, 2, 2, 3, 3, 4, 8].</p> <p>In this C++ program, the counting sort function takes a reference to the vector arr and runs the counting sort routine. It finds the table&apos;s maximum value to determine the worksheet&apos;s size. It then counts each element&apos;s occurrence and calculates the worksheet&apos;s prefix sum. Then, it creates a result vector and puts the elements in order according to the worksheet. Finally, it copies the sorted elements back into the original array. In the primary function, the example array {4, 2, 2, 8, 3, 3, 1} is sorted by the enumeration sort algorithm and printed as a sorted matrix. Note that the program uses libraries to work with vectors and find the maximum element of an array using the max_element function.</p> <hr></arr.size();></count.size();>

Це вказує на те, що вхідний масив було відсортовано за зростанням за допомогою алгоритму Counting Sort, у результаті чого отримано відсортований масив [1, 2, 2, 3, 3, 4, 8].

У цій програмі C++ функція сортування підрахунком приймає посилання на вектор arr і запускає процедуру сортування підрахунком. Він знаходить максимальне значення таблиці для визначення розміру аркуша. Потім він підраховує випадки появи кожного елемента та обчислює суму префіксів аркуша. Потім він створює вектор результатів і розміщує елементи в порядку відповідно до аркуша. Нарешті, він копіює відсортовані елементи назад у вихідний масив. У основній функції приклад масиву {4, 2, 2, 8, 3, 3, 1} сортується за допомогою алгоритму сортування за перерахуванням і друкується як відсортована матриця. Зверніть увагу, що програма використовує бібліотеки для роботи з векторами та пошуку максимального елемента масиву за допомогою функції max_element.