Въведение

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

Най-известният алгоритъм за линейно сортиране по време е низходящото сортиране. Изчислителното сортиране е особено ефективно, когато обхватът на входните елементи е известен и сравнително малък. Това елиминира необходимостта от сравняване на елементи, основната отнемаща време операция в много други алгоритми за сортиране. Използвайки знания за входна област, изчислителното сортиране постига линейна времева сложност. Числовото сортиране първо сканира входния масив, за да определи броя на всеки елемент. След това използва тези числа, за да изчисли правилните позиции на елементите в подредената таблица с резултати. Алгоритъмът се състои от следните стъпки:

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

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

конвертиране на int в низ java

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

История

Алгоритмите за линейно сортиране на време имат богата история в компютърните науки. Развитието на линейния времеви ред може да бъде проследено до средата на 20-ти век и приносът на учени и математици е значителен. Един от най-ранните алгоритми за линейно сортиране във времето е сортирането по кофа, предложено от Харолд Х. Сюърд през 1954 г. Сортирането по кофа разделя входните елементи на краен брой кофи и след това сортира всяка кофа поотделно. Този алгоритъм има линейна времева сложност, ако разпределението на входните елементи е относително равномерно.

През 1959 г. Кенет Е. Айвърсън въвежда радикален алгоритъм, който постига линейна времева сложност. Radix сортира елементите по техните номера или знаци от най-малко значими към най-значими. Той използва стабилни алгоритми за сортиране, като числово или групово сортиране, за сортиране на елементите на всяко място на цифра. Сортирането по Radix стана популярно в ерата на перфокартите и ранните компютърни системи. Въпреки това, най-известният алгоритъм за линейно сортиране по време е изброяването, въведено от Харолд Х. Сюърд и Питър Елиас през 1954 г. и по-късно независимо преоткрито от Харолд Х. „Боби“ Джонсън през 1961 г. Численото сортиране получи значително внимание.

Това е особено ефективно, когато диапазонът от входни елементи е известен и сравнително малък. Историята на линейното сортиране на времето продължи с разработването на други специализирани алгоритми. Например през 1987 г. Ханан Самет предложи сортиране на двоично дърво на разпределение, алгоритъм за линейно сортиране на време за многоизмерни данни. През годините изследователите продължиха да изучават и подобряват линейните алгоритми за планиране, като се фокусираха върху конкретни сценарии и ограничения. Въпреки че алгоритми като бързо сортиране и сливане се използват по-широко поради тяхната ефективност в повече сценарии, алгоритмите за сортиране с линейно време предоставят ценни алтернативи, когато определени обстоятелства позволяват да се използва сложността на линейното време. Като цяло, историята на линейното сортиране във времето се характеризира с търсене на ефективни алгоритми, които могат да сортират големи масиви от данни в линейно време, преодолявайки ограниченията на базираните на сравнение алгоритми за сортиране. Приносът на различни изследователи проправи пътя за разработване и разбиране на тези специализирани техники за сортиране.

Видове линейно сортиране на времето

Има няколко различни алгоритма за линейно сортиране по време. Двата основни типа са базирани на преброяване алгоритми и базирани на радикс алгоритми. Ето най-често срещаните алгоритми за линейно сортиране по време, класифицирани въз основа на следните типове:

Алгоритми, базирани на броене

Сортиране на базата на броене:Counting-Based е несравнителен алгоритъм за сортиране. Той отчита появата на всеки отделен елемент във входния масив и използва тази информация, за да определи правилната позиция на всеки елемент в сортирания изходен масив. Сортирането на базата на броене предполага, че входните елементи са цели числа или могат да бъдат добавени към цели числа.

Алгоритми, базирани на Radix

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

Предимства на линейното сортиране на времето

Алгоритмите за линейно сортиране по време, като например числово сортиране, предлагат няколко предимства в конкретни сценарии.

Ефективно за големи входни размери:Времевата сложност на алгоритмите за линейно сортиране на време е O(n), което означава, че времето за работа нараства линейно с размера на входа. Това ги прави много ефективни за големи масиви от данни в сравнение с алгоритми за сортиране, базирани на сравнение, като алгоритми за бързо сортиране или сливане, които обикновено имат времева сложност от O(n log n).Няма операции за сравнение:Алгоритмите за линейно сортиране по време, като сортирането чрез изброяване, не разчитат на елементарно сравнение, вместо това те използват специфични атрибути или информация за входните елементи, като техния обхват или разпределение. Тази функция ги прави изгодни, когато цената на сравнението е висока, като например за сложни обекти или скъпи операции за сравнение.Пригодност за специфични входни свойства:Алгоритмите за линейно сортиране често имат специфични изисквания или предположения относно входните елементи. Например, за да изчислите ред на сортиране, трябва предварително да знаете обхвата на входните елементи. Когато тези условия са изпълнени, алгоритмите за линейно сортиране по време могат да предложат значителни предимства в производителността пред общите алгоритми за сортиране.Стабилно сортиране:Много алгоритми за линейно сортиране по време, включително числово и радикално сортиране, са по своята същност стабилни. Съгласуваност означава, че елементите с дублиращи се ключове или стойности поддържат относителен ред в сортирания изход. Това може да бъде критично, когато сортирате обекти или записи с множество атрибути или когато запазването на оригиналния ред на елементи с еднаква стойност е от съществено значение.Лесна употреба:Алгоритмите за линейно сортиране по време като сортиране чрез изброяване често са сравнително лесни за изпълнение в сравнение с по-сложните алгоритми за сортиране, базирани на сравнение. Те могат да бъдат по-лесни за разбиране и отстраняване на грешки, което ги прави подходящи за ситуации, в които са желани простота и яснота.

Недостатъци на линейното сортиране на времето

Въпреки че линейните алгоритми за планиране имат своите предимства, те също имат определени ограничения и недостатъци:

jsp javatpoint

Ограничаващи изисквания за въвеждане:Алгоритмите за линейно сортиране по време често имат специфични изисквания или предположения относно входните елементи. Например, за да изчислите ред на сортиране, трябва предварително да знаете обхвата на входните елементи. Това ограничение ограничава тяхната приложимост до ситуации, в които тези условия са изпълнени. Изискванията към паметта може да станат непрактични или да надхвърлят наличните ресурси, ако диапазонът е обширен или неизвестен.Допълнителни изисквания за пространство:Някои алгоритми за линейно сортиране по време, като числено сортиране, изискват допълнително пространство за съхраняване на други масиви или структури от данни. Необходимото пространство често е пропорционално на броя на входните елементи. Това може да е недостатък, когато използването на паметта е проблем, особено когато се работи с големи набори от данни или ограничени ресурси на паметта.Липса на гъвкавост:Алгоритмите за линейно сортиране по време са специализирани алгоритми, предназначени за конкретни сценарии или ограничения. Може да се наложи те да бъдат по-подходящи и ефективни за общи задачи за сортиране или различни входни разпределения. Алгоритмите за сортиране, базирани на сравнение, като бързо сортиране или сливане, са по-гъвкави и могат да обработват по-широк диапазон от входни данни.Неефективно за малки диапазони или оскъдни данни:Алгоритмите за линейно сортиране като изброяване са най-ефективни, когато диапазонът от входни елементи е малък и гъсто разпределен. Ако диапазонът е обширен или данните са оскъдни (т.е. само няколко отделни стойности), алгоритъмът може да спести време и усилия при обработката на празни или рядко попълнени части от входния диапазон.Ограничено до конкретни типове данни:Алгоритмите за линейно сортиране по време, като сортиране чрез изброяване, са предназначени основно за сортиране на неотрицателни цели числа или обекти ключ-стойност. Те може да не са подходящи за сортиране на други типове данни, като числа с плаваща запетая, низове или сложни структури от данни. Адаптирането на алгоритми за линейно сортиране по време за работа с различни типове данни или персонализирани функции за сравнение може да изисква допълнителна предварителна обработка или модификации.

При избора на алгоритъм за сортиране е важно внимателно да се разгледат спецификите на входните данни и изискванията на проблема за сортиране. Докато линейните алгоритми за планиране предлагат предимства в конкретни сценарии, те само понякога са най-подходящият или ефективен избор.

Приложения на алгоритмите за линейно сортиране по време

Алгоритмите за линейно сортиране на времето са ефективни и имат много приложения в различни области. Ето някои типични приложения на линейния времеви ред:

Сортиране на малки цели числа:Алгоритмите за линейно сортиране по време, като сортиране по брой и сортиране по радикс, са идеални за сортиране на масиви от цели числа, когато диапазонът от стойности е. Тези алгоритми постигат линейна времева сложност, като правят предположения относно входните данни, което им позволява да заобиколят сортирането, базирано на сравнение.Сортиране на низове:Алгоритмите за линейно сортиране по време също могат да се прилагат за ефективно сортиране на низове. Като вземат уникални свойства на низовете, като тяхната дължина или знаци, алгоритми като Radix Sort могат да постигнат линейна времева сложност при сортиране на низове.Функции на базата данни:Сортирането е основна функция на алгоритмите за линейно сортиране по време, които могат ефективно да сортират големи набори от данни въз основа на конкретни колони или полета. Това позволява по-бърза обработка на заявки и по-добра производителност при операции с бази данни.Създаване на хистограми:Хистограмите са от съществено значение за различни статистически задачи и задачи за анализ на данни. Алгоритмите за линейно сортиране по време, като числено сортиране, могат да генерират хистограми чрез ефективно преброяване на появяванията на елементи в набор от данни.Външно сортиране:Техниката за външно сортиране се използва в сценарии, при които данните не могат да се поберат изцяло в паметта. Алгоритмите за линейно сортиране по време като External Radix Sort или External Counting Sort могат ефективно да сортират големи набори от данни, съхранявани на диск или други външни устройства за съхранение.График на събитието:Алгоритмите за линейно сортиране на времето могат да планират събития въз основа на тяхното начално или крайно време. Сортирането на събития във възходящ ред улеснява идентифицирането на конфликти, припокриващи се периоди или намирането на следващия наличен период.Анализиране на лог файлове:Анализирането на регистрационните файлове е често срещана задача при системното администриране и отстраняване на грешки. Алгоритмите за линейно сортиране на времето могат да се използват за сортиране на регистрационни файлове въз основа на времеви отпечатъци, което улеснява идентифицирането на модели, аномалии или търсенето на конкретни събития.Компресиране на данни:Сортирането играе съществена роля в различни техники за компресиране на данни. Алгоритми като Burrows-Wheeler Transform (BWT) или Move-To-Front Transform (MTF) разчитат на линейно подреждане във времето, за да пренаредят данните, за да подобрят ефективността на компресията. Това са само няколко примера за приложения на алгоритми за линейно сортиране по време.

Внедряване на линейно сортиране по време в C++

Ето пример за програма, прилагаща Counting Sort, която е линеен алгоритъм за сортиране по време:

сортиране на вмъкване

 #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();>

Това показва, че входният масив е сортиран във възходящ ред с помощта на алгоритъма за сортиране с броене, което води до сортирания масив [1, 2, 2, 3, 3, 4, 8].

В тази програма на C++ функцията за сортиране с броене взема препратка към вектора arr и изпълнява процедурата за сортиране с броене. Той намира максималната стойност на таблицата, за да определи размера на работния лист. След това отчита появата на всеки елемент и изчислява префиксната сума на работния лист. След това създава резултатен вектор и подрежда елементите в съответствие с работния лист. Накрая той копира сортираните елементи обратно в оригиналния масив. В основната функция примерният масив {4, 2, 2, 8, 3, 3, 1} се сортира от алгоритъма за сортиране чрез изброяване и се отпечатва като сортирана матрица. Имайте предвид, че програмата използва библиотеки за работа с вектори и намиране на максималния елемент от масив с помощта на функцията max_element.