Introducció

L'ordenació és una operació essencial en informàtica que consisteix a ordenar els elements en un ordre específic, com ara l'ordre numèric o alfabètic. S'han desenvolupat diversos algorismes d'ordenació, cadascun amb indicadors de temps i eficiència. L'ordenació temporal lineal és un subconjunt d'algorismes d'ordenació amb un avantatge significatiu: poden ordenar un conjunt determinat d'elements en temps lineal, el temps d'execució augmenta linealment amb la mida d'entrada.

L'algorisme d'ordenació temporal lineal més conegut és l'ordenació descendent. L'ordenació computacional és particularment eficient quan el rang d'elements d'entrada és conegut i relativament petit. Això elimina la necessitat de comparar elements, la principal operació que consumeix temps en molts altres algorismes d'ordenació. Utilitzant el coneixement del domini d'entrada, l'ordenació computacional aconsegueix una complexitat temporal lineal. Una ordenació numèrica explora primer la matriu d'entrada per determinar el recompte de cada element. A continuació, utilitza aquests números per calcular les posicions correctes dels elements a la taula de resultats ordenada. L'algorisme consta dels passos següents:

1. Per determinar l'interval, identifiqueu els valors mínims i màxims de la matriu d'entrada.
2. Creeu un full de treball inicialitzat amb la mida de l'interval i els zeros.
3. Itereu sobre la matriu d'entrada i incrementeu cada element trobat.
4. Modifiqueu el full de treball calculant el total acumulat per obtenir les posicions correctes per a cada element.
5. Creeu una matriu de sortida de la mateixa mida que la matriu d'entrada.
6. Torneu a moure la matriu d'entrada, col·locant cada element a la posició correcta a la matriu de sortida segons el full de treball.
7. La taula de resultats ara conté elements ordenats.

El principal avantatge de l'ordenació descendent és que aconsegueix una complexitat temporal lineal de O(n), cosa que la fa molt eficient per a grans mides d'entrada. No obstant això, la seva aplicabilitat es limita a escenaris on l'elecció dels elements d'entrada és coneguda per endavant i relativament petita.

És important tenir en compte que altres algorismes d'ordenació, com ara quicksort o merge, solen tenir una complexitat temporal de O(n log n), que es considera eficient per a moltes aplicacions pràctiques. Els algorismes d'ordenació temporal lineal, com ara l'ordenació numèrica, ofereixen una alternativa quan determinades restriccions o propietats de l'entrada permeten utilitzar la complexitat temporal lineal.

Història

Els algorismes d'ordenació temporal lineal tenen una rica història en informàtica. El desenvolupament de l'ordre temporal lineal es remunta a mitjans del segle XX, i les contribucions de científics i matemàtics van ser importants. Un dels primers algorismes d'ordenació lineal de temps és l'ordenació de cubs, proposat per Harold H. Seward el 1954. Una classificació de cubs divideix els elements d'entrada en un nombre finit de cubs i després ordena cada cub per separat. Aquest algorisme té una complexitat temporal lineal si la distribució dels elements d'entrada és relativament uniforme.

El 1959, Kenneth E. Iverson va introduir un algorisme de radix que aconsegueix una complexitat temporal lineal. Radix ordena els elements segons els seus nombres o signes de menys significatiu a més significatiu. Utilitza algorismes d'ordenació robustos, com ara l'ordenació numèrica o de cub, per ordenar els elements a la ubicació de cada dígit. La classificació Radix es va fer popular a l'era de les targetes perforades i els primers sistemes informàtics. No obstant això, l'algorisme d'ordenació temporal lineal més conegut és una enumeració, introduïda per Harold H. Seward i Peter Elias el 1954 i posteriorment redescoberta independentment per Harold H. 'Bobby' Johnson el 1961. L'ordenació numèrica ha rebut una atenció considerable.

Això és especialment eficaç quan el rang d'elements d'entrada és conegut i relativament petit. La història de l'ordenació temporal lineal va continuar amb el desenvolupament d'altres algorismes especialitzats. Per exemple, l'any 1987, Hanan Samet va proposar l'ordenació d'arbres de distribució binària, un algorisme d'ordenació temporal lineal per a dades multidimensionals. Al llarg dels anys, els investigadors han continuat estudiant i millorant els algorismes de programació lineal, centrant-se en escenaris i limitacions específics. Tot i que els algorismes com ara quicksort i merge són més utilitzats per la seva eficiència en més escenaris, els algorismes d'ordenació en temps lineal ofereixen alternatives valuoses quan determinades circumstàncies permeten explotar la complexitat del temps lineal. En general, la història de l'ordenació temporal lineal es caracteritza per la recerca d'algorismes eficients que puguin ordenar grans conjunts de dades en temps lineal, superant les limitacions dels algorismes d'ordenació basats en comparacions. Les contribucions de diversos investigadors van obrir el camí per desenvolupar i comprendre aquestes tècniques de classificació especialitzades.

Tipus d'ordenació temporal lineal

Hi ha diversos algorismes d'ordenació temporal lineal diferents. Els dos tipus principals són algorismes basats en el recompte i algorismes basats en radix. Aquests són els algorismes d'ordenació temporal lineal més comuns, classificats segons els tipus següents:

Algorismes basats en el recompte

Ordenació basada en el recompte:Basat en el recompte és un algorisme d'ordenació no comparatiu. Compta l'aparició de cada element en particular a la matriu d'entrada i utilitza aquesta informació per determinar la posició correcta de cada element a la matriu de sortida ordenada. L'ordenació basada en el recompte suposa que els elements d'entrada són nombres enters o es poden afegir a nombres enters.

Algorismes basats en radis

Radix Sort:Radix Sort és un algorisme d'ordenació no basat en comparacions que ordena els elements segons els seus números o caràcters. Compta cada nombre o signe dels elements des del nombre menys significatiu fins al més significatiu L'ordenació radical suposa que els elements d'entrada són nombres enters o cadenes.Ordenació de cubs:Bucket Sort és una variant de Radix Sort que divideix els elements en grups fixos en funció del seu rang o distribució. Cada segment s'ordena per separat utilitzant un algorisme d'ordenació diferent o bin-sort recursivament.MSD (dígit més significatiu) Ordenació de base:MSD Radix Sort és una variant de l'ordenació radix que comença a ordenar els elements en funció dels seus més significatius. Divideix recursivament els elements en subgrups segons el valor del nombre actual i aplica MSD Radix Sort a cada subgrup fins que s'han comptat tots els nombres.LSD (dígit menys significatiu) Ordenació de base:LSD Radix Sort és una altra variant que comença a ordenar els elements en funció del seu menys significatiu. Ordena recursivament els elements en funció de cada nombre de l'extrem dret a l'esquerra, produint un resultat ordenat. Tant els algorismes d'ordenació basats en el recompte com els basats en arrels aconsegueixen una complexitat temporal lineal aprofitant propietats específiques dels elements d'entrada, com ara el seu rang o estructura de representació (per exemple, números o caràcters). Tanmateix, la seva aplicabilitat pot variar en funció de les característiques de les dades d'entrada.

Avantatges de l'ordenació temporal lineal

Els algorismes d'ordenació temporal lineal, com ara l'ordenació numèrica, ofereixen diversos avantatges en escenaris específics.

Eficaç per a mides d'entrada grans:La complexitat temporal dels algorismes d'ordenació temporal lineal és O(n), el que significa que el temps d'execució augmenta linealment amb la mida d'entrada. Això els fa molt eficients per a grans conjunts de dades en comparació amb algorismes d'ordenació basats en comparacions, com ara algorismes de classificació ràpida o de fusió, que normalment tenen una complexitat temporal de O(n log n).Sense operacions de comparació:Els algorismes d'ordenació en temps lineal, com ara l'ordenació per enumeració, no es basen en comparacions elementals, sinó que utilitzen atributs o informació específics sobre els elements d'entrada, com ara la seva extensió o distribució. Aquesta característica els fa avantatjoses quan el cost de la comparació és elevat, com per exemple per a objectes complexos o operacions de comparació cares.Adequació a propietats d'entrada específiques:Els algorismes d'ordenació en temps lineal sovint tenen requisits o supòsits específics sobre els elements d'entrada. Per exemple, per calcular un ordre d'ordenació, cal conèixer per endavant el rang d'elements d'entrada. Quan es compleixen aquestes condicions, els algorismes d'ordenació temporal lineal poden oferir avantatges significatius de rendiment respecte als algorismes d'ordenació generals.Classificació estable:Molts algorismes d'ordenació en temps lineal, inclòs l'ordenació numèrica i radix, són inherentment estables. La coherència significa que els elements amb claus o valors duplicats mantenen un ordre relatiu a la sortida ordenada. Això pot ser fonamental a l'hora d'ordenar objectes o registres amb múltiples atributs o quan és essencial preservar l'ordre original dels elements d'igual valor.Facilitat d'ús:Els algorismes d'ordenació temporal lineal, com ara l'ordenació d'enumeració, sovint són relativament fàcils d'implementar en comparació amb els algorismes d'ordenació basats en comparacions més complexos. Poden ser més fàcils d'entendre i depurar, fent-los adequats per a situacions en què es desitgen simplicitat i claredat.

Inconvenients de l'ordenació temporal lineal

Tot i que els algorismes de programació lineal tenen els seus avantatges, també tenen certes limitacions i desavantatges:

Requisits d'entrada limitants:Els algorismes d'ordenació temporal lineal solen tenir requisits o supòsits específics sobre els elements d'entrada. Per exemple, per calcular un ordre d'ordenació, cal conèixer per endavant el rang d'elements d'entrada. Aquesta restricció limita la seva aplicabilitat a situacions en què es compleixen aquestes condicions. Els requisits de memòria poden arribar a ser poc pràctics o superar els recursos disponibles si l'abast és extens o desconegut.Requisits d'espai addicionals:Alguns algorismes d'ordenació temporal lineal, com ara l'ordenació numèrica, requereixen espai addicional per emmagatzemar altres matrius o estructures de dades. L'espai requerit sovint és proporcional al nombre d'elements d'entrada. Això pot ser un desavantatge quan l'ús de la memòria és un problema, especialment quan es tracta de grans conjunts de dades o recursos de memòria limitats.Falta de versatilitat:Els algorismes d'ordenació temporal lineal són algorismes especialitzats dissenyats per a escenaris o restriccions específiques. És possible que hagin de ser més adequats i eficients per a tasques d'ordenació generals o diferents distribucions d'entrada. Els algorismes d'ordenació basats en la comparació, com ara l'ordenació ràpida o la combinació, són més versàtils i poden gestionar un rang d'entrada més ampli.Ineficient per a intervals petits o dades escasses:Els algorismes d'ordenació en temps lineal com l'enumeració són més eficients quan el rang d'elements d'entrada és petit i densament distribuït. Si l'interval és extens o les dades són escasses (és a dir, només uns quants valors diferents), l'algorisme pot estalviar temps i esforç processant parts buides o poc poblades de l'interval d'entrada.Limitat a tipus de dades específics:Els algorismes d'ordenació en temps lineal, com ara l'ordenació per enumeració, estan dissenyats principalment per ordenar nombres enters no negatius o objectes de valor-clau. És possible que no siguin adequats per ordenar altres tipus de dades, com ara números de coma flotant, cadenes o estructures de dades complexes. L'adaptació dels algorismes d'ordenació temporal lineal per gestionar diferents tipus de dades o funcions de comparació personalitzades pot requerir un preprocessament o modificacions addicionals.

A l'hora d'escollir un algorisme d'ordenació, és essencial tenir en compte les especificitats de les dades d'entrada i els requisits del problema d'ordenació. Tot i que els algorismes de programació lineal ofereixen avantatges en escenaris específics, només de vegades són l'opció més adequada o eficient.

llista de matrius d'ordenació de java

Aplicacions dels algorismes d'ordenació temporal lineal

Els algorismes d'ordenació temporal lineal són eficients i tenen moltes aplicacions en diversos camps. Aquí hi ha algunes aplicacions típiques de l'ordre temporal lineal:

Ordenació de nombres enters d'interval petit:Els algorismes d'ordenació temporal lineal, com ara l'ordenació per compte i l'ordenació per radix, són ideals per ordenar matrius d'enters quan el rang de valors és. Aquests algorismes aconsegueixen una complexitat de temps lineal fent suposicions sobre les dades d'entrada, cosa que els permet evitar l'ordenació basada en comparacions.Classificació de cadenes:Els algorismes d'ordenació temporal lineal també es poden aplicar per ordenar les cadenes de manera eficient. Prenent propietats úniques de les cadenes, com ara la seva longitud o caràcters, algorismes com Radix Sort poden aconseguir una complexitat temporal lineal a l'hora d'ordenar les cadenes.Funcions de la base de dades:L'ordenació és una funció essencial dels algorismes d'ordenació temporal lineal que poden ordenar de manera eficient grans conjunts de dades basats en columnes o camps específics. Això permet un processament de consultes més ràpid i un millor rendiment en les operacions de la base de dades.Creació d'histogrames:Els histogrames són essencials per a diverses tasques estadístiques i d'anàlisi de dades. Els algorismes d'ordenació temporal lineal, com ara l'ordenació numèrica, poden generar histogrames comptant de manera eficient les ocurrències d'elements en un conjunt de dades.Classificació externa:La tècnica d'ordenació externa s'utilitza en escenaris en què les dades no poden cabre completament a la memòria. Els algorismes d'ordenació temporal lineal, com ara l'ordenació de radix externa o l'ordenació de comptatge extern, poden ordenar de manera eficient grans conjunts de dades emmagatzemats al disc o en altres dispositius d'emmagatzematge externs.Programació d'esdeveniments:Els algorismes d'ordenació temporal lineal poden programar esdeveniments en funció de les seves hores d'inici o de finalització. Ordenar els esdeveniments en ordre ascendent facilita identificar conflictes, períodes superposats o trobar el següent període disponible.Anàlisi dels fitxers de registre:L'anàlisi dels fitxers de registre és una tasca habitual en l'administració i depuració del sistema. Els algorismes d'ordenació temporal lineal es poden utilitzar per ordenar els registres en funció de les marques de temps, facilitant la identificació de patrons, anomalies o cerca d'esdeveniments específics.Compressió de dades:L'ordenació té un paper essencial en diverses tècniques de compressió de dades. Algorismes com ara Burrows-Wheeler Transform (BWT) o Move-To-Front Transform (MTF) es basen en l'ordenació temporal lineal per reordenar les dades per millorar l'eficiència de la compressió. Aquests són només alguns exemples d'aplicacions dels algorismes d'ordenació temporal lineal.

Implementació de l'ordenació temporal lineal en C++

Aquí teniu un exemple d'un programa que implementa Counting Sort, que és un algorisme d'ordenació temporal lineal:

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

Això indica que la matriu d'entrada s'ha ordenat en ordre ascendent mitjançant l'algorisme de Counting Sort, donant lloc a la matriu ordenada [1, 2, 2, 3, 3, 4, 8].

En aquest programa C++, la funció d'ordenació de recompte pren una referència al vector arr i executa la rutina d'ordenació de recompte. Troba el valor màxim de la taula per determinar la mida del full de treball. A continuació, compta l'aparició de cada element i calcula la suma del prefix del full de treball. Aleshores, crea un vector de resultats i posa els elements en ordre segons el full de treball. Finalment, torna a copiar els elements ordenats a la matriu original. A la funció principal, la matriu d'exemple {4, 2, 2, 8, 3, 3, 1} s'ordena mitjançant l'algorisme d'ordenació d'enumeració i s'imprimeix com una matriu ordenada. Tingueu en compte que el programa utilitza biblioteques per treballar amb vectors i trobar l'element màxim d'una matriu mitjançant la funció max_element.