| dbpprop:abstract
|
- In computer science, radix sort is a sorting algorithm that sorts integers by processing individual digits. Because integers can represent strings of characters (e.g. , names or dates) and specially formatted floating point numbers, radix sort is not limited to integers. Radix sort dates back as far as 1887 to the work of Herman Hollerith on tabulating machines. Most digital computers internally represent all of their data as electronic representations of binary numbers, so processing the digits of integer representations by groups of binary digit representations is most convenient. Two classifications of radix sorts are least significant digit (LSD) radix sorts and most significant digit (MSD) radix sorts. LSD radix sorts process the integer representations starting from the least significant digit and move towards the most significant digit. MSD radix sorts work the other way around. The integer representations that are processed by sorting algorithms are often called "keys," which can exist all by themselves or be associated with other data. LSD radix sorts typically use the following sorting order: short keys come before longer keys, and keys of the same length are sorted lexicographically. This coincides with the normal order of integer representations, such as the sequence 1, 2, 3, 4, 5, 6, 7, 8, 9, 10. MSD radix sorts use lexicographic order, which is suitable for sorting strings, such as words, or fixed-length integer representations. A sequence such as "b, c, d, e, f, g, h, i, j, ba" would be lexicographically sorted as "b, ba, c, d, e, f, g, h, i, j". If lexicographic ordering is used to sort variable-length integer representations, then the representations of the numbers from 1 to 10 would be output as 1, 10, 2, 3, 4, 5, 6, 7, 8, 9, as if the shorter keys were left-justified and padded on the right with blank characters to make the shorter keys as long as the longest key for the purpose of determining sorted order.
- Radixsort (von lat. Wurzel, Basis) oder auch Distributionsort (von engl. Distribution – „Verteilung“), oder im Deutschen Fachverteilen, ist ein lineares, stabiles Sortierverfahren, das out-of-place arbeitet und auf Countingsort basiert. Das Sortierverfahren hat unter der Voraussetzung, dass die maximale Länge der zu sortierenden Schlüssel von vornherein bekannt ist, lineare Laufzeit (abhängig von der Anzahl der Elemente, die zu sortieren sind).
- Radix sort je řadicí algoritmus, který řadí celá čísla postupným procházením všech číslic (často se vstupní čísla převádějí do soustavy o jiném základu, odtud tedy název). Jelikož celočíselné hodnoty mohou reprezentovat řetězce (jména, data apod. ), a dokonce i vhodně formátovaná čísla s plovoucí desetinnou čárkou, radix sort není omezen pouze na řazení celých čísel. Většina digitálních počítačů vnitřně reprezentuje všechna data jako binární čísla, nejpřirozenější je pro něj tedy řazení podle skupin bitů (tj. podle číslic o základu 8, 16, 32, 256 apod.). V některých případech lze dosáhnout asymptotické časové složitosti až O(n) (dolní hranice). Obecně je časová složitost Radix sortu O(*logzu), kde z je základ zvolené číselné soustavy, n počet čísel na vstupu a u je maximální rozmezí čísel na vstupu. Tedy pokud zvolíme za základ soustavy počet čísel na vstupu (z=n), dostáváme složitost O(n*lognu). Pokud je rozmezí čísel polynomiálně velké k velikosti vstupu, lze tedy dosáhnout časové složitosti O(n). Pro neomezeně velký rozsah vstupních čísel se Radixsort nehodí.
- En informática, el ordenamiento Radix (radix sort en inglés) es un algoritmo de ordenamiento que ordena enteros procesando sus dígitos de forma individual. Como los enteros pueden representar cadenas de caracteres (por ejemplo, nombres o fechas) y, especialmente, números en punto flotante especialmente formateados, radix sort no está limitado sólo a los enteros.
- Tietojenkäsittelytieteessä kantalukulajittelu (kantalukujärjestäminen, reikäkorttijärjestäminen, engl. radix sort) on lajittelualgoritmi, joka lajittelee lukuja suuruusjärjestykseen numeroiden merkitsevyyden perusteella. Siten se ei ole yleiskäyttöinen vertailuun pohjautuva lajittelualgoritmi, mutta käyttäen apuna laskentalajittelua se suoriutuu lineaarisessa ajassa. Myös kirjaimia voidaan ajatella numeroina, jolloin voidaan lajitella merkkijonoja. Kantalukulajittelu on vakaa eli se ei sotke alkioiden alkuperäistä järjestystä.
- Le tri par base (ou tri radix) est, en informatique, un algorithme de tri rapide et stable qui peut être utilisé pour ordonner des éléments identifiés par une clef unique. Chaque clef est une chaîne de caractères ou un nombre que le tri par base trie selon un ordre lexical. Le temps d'exécution est O(nk) où n est le nombre d'objets et k la taille moyenne des clefs. Cet algorithme était utilisé pour trier des cartes perforées en plusieurs passages. Le tri par base a été réutilisé comme une alternative à des algorithmes de tri plus puissants qui demandent O(n log n) comparaisons où n est le nombre d'objets à trier. Ces algorithmes sont plus efficaces pour trier des données selon un ordre qui n'est pas lexical, mais c'est de peu d'importance pour les applications pratiques. Si la taille de l'espace possible de clefs est proportionnel au nombre d'éléments, alors chaque clef aura une taille de log n caractères et le tri par base s'effectura en un temps O(n log n) dans ce cas. En pratique, si les clefs utilisées sont de petits entiers, le tri peut être réalisé en deux temps, les comparaisons peuvent alors être faite avec quelques opérations qui opèrent en un temps constant. Dans ce cas, le tri par base s'exécutera en O(n) et en pratique il s'avérera plus rapide que d'autres algorithmes de tri. Le plus grand désavantage du tri par base est qu'il nécessite O(n) espace mémoire supplémentaire et il requiert une analyse de chaque caractère des clefs de la liste d'entrée, il peut donc être très lent pour des clefs longues. L'ordre de tri est typiquement le suivant : les clefs courtes viennent avant les clefs longues, les clefs de même taille sont triées selon un ordre lexical. Cette méthode correspond à l'ordre naturel des nombres s'ils sont représentés par des chaînes de chiffres. Son mode opératoire est : prend le chiffre (ou groupe de bits) le moins significatif de chaque clef, trie la liste des éléments selon ce chiffre, mais conserve l'ordre des éléments ayant le même chiffre (ce qui est un tri stable). répète le tri avec chaque chiffre plus significatif.
- Il Radix Sort è un algoritmo di ordinamento per valori numerici interi con complessità computazionale O(<math>n</math>), dove <math>n</math> è la lunghezza dell'array e <math>k</math> è la media del numero di cifre degli <math>n</math> numeri. Radixsort utilizza un procedimento controintuitivo per l'uomo, ma più facilmente implementabile. Esegue gli ordinamenti per posizione della cifra ma partendo dalla cifra meno significativa. Questo affinché l'algoritmo non si trovi a dovere operare ricorsivamente su sottoproblemi di dimensione non valutabili a priori.
- 基数ソートは、ソートのアルゴリズムの一つ。計算時間はO(nk)と高速だが、O(n)の外部記憶（高速なメモリーでなくても良い）が必要。（ここで、nはデータの数、kはキーの数を意味する。）
- Radix sort is een sorteeralgoritme dat in staat is om verzamelingen van bepaalde elementen te sorteren. Radix sort maakt gebruik van een combinatie van een vaste sorteer-strategie en een apart, tweede sorteer-algoritme (een hulpalgoritme) om een gegeven verzameling elementen te ordenen. Radix sort kan, afhankelijk van het gebruikte hulpalgoritme, zeer efficiënt zijn in het ordenen van een verzameling.
- Sortowanie pozycyjne (ang. radix sort) to algorytm sortowania porządkujący stabilnie ciągi wartości (liczb, słów) względem konkretnych cyfr, znaków itp, kolejno od najmniej znaczących do najbardziej znaczących pozycji. Złożoność obliczeniowa jest równa <math>O(d)</math>, gdzie <math>k</math> to ilość różnych cyfr, a <math>d</math> ilość cyfr w kluczach. Wymaga <math>O(n+k)</math> dodatkowej pamięci. Przewagą sortowania pozycyjnego nad innymi metodami jest fakt, iż nie wykonuje on żadnych operacji porównania na danych wejściowych. Załóżmy że mamy dużą liczbę bardzo długich liczb, bardzo do siebie podobnych – w tym sensie, że większość z nich ma takie same cyfry na początkowych pozycjach. Nie jest łatwo powiedzieć która jest większa, gdyż za każdym razem musimy porównać dużo cyfr zanim trafimy na różnicę. Czas porównania takich liczb jest zatem proporcjonalny do ich długości. Gdybyśmy do posortowania tych liczb zastosowali algorytm porównujący liczby, np. sortowanie szybkie, otrzymalibyśmy dla niego złożoność <math>O(d n \log n)</math> gdzie <math>d</math> to ilość cyfr w liczbach. Algorytmy pozycyjne sprawdzają się także w roli algorytmów sortujących listy.
- O Radix sort é um algoritmo de ordenação rápido e estável que pode ser usado para ordenar itens que estão identificados por chaves únicas. Cada chave é uma cadeia de caracteres ou número, e o radix sort ordena estas chaves numa qualquer ordem relacionada com a lexicografia. Na ciência da computação, radix sort é um algoritmo de ordenação que ordena inteiros processando dígitos individuais. Já que os inteiros podem representar strings composta de caracteres (ex, nome ou datas) e pontos flutuantes especialmente formatados, radix sort não é limitado somente a inteiros. Computadores na sua maioria internamente representam todos os tipo de dados por números binários, por isso processar os dígitos na forma de inteiros em grupos representados por dígitos binários se torna mais conveniente. Existem duas classificações do radix sorts que são elas: - Least significant digit (LSD – Dígito menos significante) radix sorts; - Most significant digit (MSD – Dígito mais significante) radix sorts. Radix sorts LSD começa do dígito menos significante até o mais significante. Radix sorts MSD trabalha no sentido contrário. As representações de inteiros que são processadas pelo algoritmo de ordenação são frequentemente chamadas de “chaves”, que podem existir por si próprias ou associadas a outros dados. Radix sorts LSD tipicamente usa a seguinte ordem de ordenação: chaves curtas vem antes de chaves longas, e chaves de mesmo tamanho são ordenadas lexicograficamente. Isso coincide com a ordem normal de representação dos inteiros, como a seqüência 1, 2, 3, 4, 5, 6, 7, 8, 9, 10. Radix sorts MSD usa a ordem lexicográfica, que é adequada para ordenação de strings, assim como palavras, ou representações inteiros fixa com tamanho fixo. A seqüência "b, c, d, e, f, g, h, i, j, ba" será ordenada lexicograficamente assim "b, ba, c, d, e, f, g, h, i, j". Se a ordenação lexicográfica é usada para ordenar representações de inteiros com tamanho variável, então a representação de números inteiros de 1 a 10 terá a saída 1, 10, 2, 3, 4, 5, 6, 7, 8, 9, já que as chaves mais curtas são selecionadas primeiro pela esquerda e pulando para direita com espaços em branco para fazer as chaves também serem chaves longas para cumprir o proposito determinado pela ordenação. LSD é um algoritmo de ordenação rápido e estável, que pode ser usado para ordenar chaves curtas em ordem lexicográfica. Chaves deve ser uma string de caracteres, ou numérica. O processo das chaves começa no dígito meno significante, o mais a direta, até o mais significante, o mais a esquerda. A seqüência que cada digito é processada pelo radix sort LSD é contraria a seqüência que cada digito é processada pelo radix sort MSD. O radix sort LSD opera na notação Big O, em O(nk), onde n é o número de chaves, e o comprimento médio da chave. Você pode garantir esse desempenho para um comprimento variável da chave agrupando todas as chaves que tem o mesmo comprimento juntas e separadamente agindo como um radix sort LSD em cada grupo de chaves para cada comprimento, do mais curto para o mais comprido, em ordem para evitar o processamento de um lista inteira de chaves em cada passo da ordenação. O algoritmo de ordenação radix foi originalmente usado para ordenar cartões perfurados em uma número grande de passos. Um algoritmo computador radix sort foi inventado em 1954 na MIT por Harold H. Seward. Em muitas aplicações em que seja necessário velocidade, o computador radix sort é uma melhora nas ordenações por comparação. O radix sort LSD tem se mostrado uma alternativa de alta performance em relação a algoritmos baseados na comparação (assim como heapsort e o mergesort) que requerê comparações Ω(n · log n), onde n é o número de itens a serem ordenados. Algoritmos de ordenação baseados em comparações não atingem mais que Ω(n · log n) em tempo de execução, mas oferecem flexibilidade por ser aptos a ordenar respeitando formas mais complicadas de ordenação do que uma forma lexicográfica, no entanto, essa habilidade é de pouca importância em várias aplicações práticas. Características Complexidade de Tempo: Θ(nk). Complexidade de espaço: Θ(n + s). – n = número de elementos. – k = tamanho string. – s = tamanho do alfabeto.
- Поразрядная сортировка (Цифровая сортировка) — алгоритм сортировки за линейное время.
- Basamağa göre sıralama bilgisayar bilimlerinde sayıları basamaklarının üzerinde işlem yaparak sıralayan bir sıralama algoritmasıdır. Sayma sayıları adlar ya da tarihler gibi karakter dizilerini göstermek için kullanılabildiği için basamağa göre sıralama algoritması yalnızca sayma sayılarını sıralamak için kullanılan bir algoritma değildir. Çoğu bilgisayar veri saklamak için ikilik tabandaki sayıların elektronikteki gösterim biçimlerini kullandığı için sayma sayılarının basamaklarını ikilik tabandaki sayılardan oluşan öbekler biçiminde göstermek daha kolaydır. Basamağa göre sıralama algoritması en anlamlı basamağa göre sıralama ve en anlamsız basamağa göre sıralama olarak ikiye ayrılır. En anlamsız basamağa göre sıralama algoritması sayıları en anlamsız (en küçük, en sağdaki) basamaktan başlayıp en anlamlı basamağa doğru yürüyerek sıralarken en anlamlı basamağa göre sıralama bunun tam tersini uygular. Sıralama algoritmaları tarafından işlenen ve kendi sayı değerlerini gösterebildiği gibi başka tür verilerle de eşleştirilebilen sayma sayılarına çoğu zaman "anahtar" denir. En anlamsız basamağa göre sıralamada kısa anahtarlardan uzunlardan önce gelirken aynı uzunluktaki anahtarlar sözlükteki sıralarına göre sıralanırlar. Bu sıralama biçimi sayma sayılarının kendi değerlerine göre sıralandıklarında oluşan sırayla aynı sırayı oluşturur. Örneğin 1'den 10'a kadar olan sayılar sıralandığında ortaya 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 dizisi çıkacaktır. En anlamlı basamağa göre sıralama sözcükler ya da aynı uzunluktaki sayılar gibi dizgileri sıralamak için uygun olan sözlükteki sıraya göre sıralar. Örneğin "b, c, d, e, f, g, h, i, j, ba" dizisi sözlük sırasına göre "b, ba, c, d, e, f, g, h, i, j" olarak sıralanacaktır. Eğer sözlük sıras değişken uzunluktaki sayılarda uygulanırsa sayılar değerlerinin gerektirdiği konumlara konulmazlar. Örneğin 1'den 10'a kadar olan sayılar sıralandığında, algoritma kısa olan sayıların sonuna boş karakter koyarak bütün anahtarları en uzun anahtarla aynı boyuta getireceğinden sonuç 1, 10, 2, 3, 4, 5, 6, 7, 8, 9 olacaktır.
- Сортування за розрядами — швидкий стабільний алгоритм впорядкування даних. Застосовується для впорядкування елементів, що є ланцюжками над будь-яким скінченним алфавітом (напр. рядки, або цілі числа). В якості допоміжного використовує будь-який інший стабільний алгоритм сортування. Алгоритм застосовувався для впорядкування перфокарт.
- 基数排序是一种排序算法，它是这样实现的： 将所有待比较数值(正整数)统一为同样的数位长度,数位较短的数前面补零. 然后, 从最低位开始, 依次进行一次排序. 这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列. 基数排序的方式可以采用LSD（Least significant digital）或MSD（Most significant digital），LSD的排序方式由键值的最右边开始，而MSD则相反，由键值的最左边开始。 假设需排序数列的取值范围从1... k,我们于是建一个K+1元的数组 a，并赋初值为0，然后便开始排序工作： 按输入顺序读入数列，如果所读的元素为i(1<=i<=k),我们就将a[i]的值加一，这样直到读完所有的元素。 读出元素并排序：我们遍历整个数组，如果a[i]=j(j>=0),我们就输出j次i(表示元素i在原先数列中出现了j次),这样输出的序列就是已排序的。 由于一般排序算法涉及到元素之间的比较，如果化成比较树可以知道，这样的排序算法复杂度的下限是O(N*lnN),而计数排序没有比较元素，所以所需排序时间就少了，我们可以看到计数排序的复杂度为O(n*k)，其中k（k的定义同上）为合并排列所需的时间，是个常数。 此算法适合所需排列的元素取值范围不大的情况下，否则会造成空间的消耗，比如，一共100个元素，其取值范围从1-100000，显然这个时候用基数排序是不合适的。
|
| rdfs:comment
|
- In computer science, radix sort is a sorting algorithm that sorts integers by processing individual digits. Because integers can represent strings of characters (e.g. , names or dates) and specially formatted floating point numbers, radix sort is not limited to integers. Radix sort dates back as far as 1887 to the work of Herman Hollerith on tabulating machines.
- Radixsort (von lat. Wurzel, Basis) oder auch Distributionsort (von engl. Distribution – „Verteilung“), oder im Deutschen Fachverteilen, ist ein lineares, stabiles Sortierverfahren, das out-of-place arbeitet und auf Countingsort basiert. Das Sortierverfahren hat unter der Voraussetzung, dass die maximale Länge der zu sortierenden Schlüssel von vornherein bekannt ist, lineare Laufzeit (abhängig von der Anzahl der Elemente, die zu sortieren sind).
- Radix sort je řadicí algoritmus, který řadí celá čísla postupným procházením všech číslic (často se vstupní čísla převádějí do soustavy o jiném základu, odtud tedy název). Jelikož celočíselné hodnoty mohou reprezentovat řetězce (jména, data apod. ), a dokonce i vhodně formátovaná čísla s plovoucí desetinnou čárkou, radix sort není omezen pouze na řazení celých čísel.
- En informática, el ordenamiento Radix (radix sort en inglés) es un algoritmo de ordenamiento que ordena enteros procesando sus dígitos de forma individual. Como los enteros pueden representar cadenas de caracteres (por ejemplo, nombres o fechas) y, especialmente, números en punto flotante especialmente formateados, radix sort no está limitado sólo a los enteros.
- Tietojenkäsittelytieteessä kantalukulajittelu (kantalukujärjestäminen, reikäkorttijärjestäminen, engl. radix sort) on lajittelualgoritmi, joka lajittelee lukuja suuruusjärjestykseen numeroiden merkitsevyyden perusteella. Siten se ei ole yleiskäyttöinen vertailuun pohjautuva lajittelualgoritmi, mutta käyttäen apuna laskentalajittelua se suoriutuu lineaarisessa ajassa. Myös kirjaimia voidaan ajatella numeroina, jolloin voidaan lajitella merkkijonoja.
- Le tri par base (ou tri radix) est, en informatique, un algorithme de tri rapide et stable qui peut être utilisé pour ordonner des éléments identifiés par une clef unique. Chaque clef est une chaîne de caractères ou un nombre que le tri par base trie selon un ordre lexical. Le temps d'exécution est O(nk) où n est le nombre d'objets et k la taille moyenne des clefs. Cet algorithme était utilisé pour trier des cartes perforées en plusieurs passages.
- Il Radix Sort è un algoritmo di ordinamento per valori numerici interi con complessità computazionale O(<math>n</math>), dove <math>n</math> è la lunghezza dell'array e <math>k</math> è la media del numero di cifre degli <math>n</math> numeri. Radixsort utilizza un procedimento controintuitivo per l'uomo, ma più facilmente implementabile. Esegue gli ordinamenti per posizione della cifra ma partendo dalla cifra meno significativa.
- 基数ソートは、ソートのアルゴリズムの一つ。計算時間はO(nk)と高速だが、O(n)の外部記憶（高速なメモリーでなくても良い）が必要。（ここで、nはデータの数、kはキーの数を意味する。）
- Radix sort is een sorteeralgoritme dat in staat is om verzamelingen van bepaalde elementen te sorteren. Radix sort maakt gebruik van een combinatie van een vaste sorteer-strategie en een apart, tweede sorteer-algoritme (een hulpalgoritme) om een gegeven verzameling elementen te ordenen. Radix sort kan, afhankelijk van het gebruikte hulpalgoritme, zeer efficiënt zijn in het ordenen van een verzameling.
- Sortowanie pozycyjne (ang. radix sort) to algorytm sortowania porządkujący stabilnie ciągi wartości (liczb, słów) względem konkretnych cyfr, znaków itp, kolejno od najmniej znaczących do najbardziej znaczących pozycji. Złożoność obliczeniowa jest równa <math>O(d)</math>, gdzie <math>k</math> to ilość różnych cyfr, a <math>d</math> ilość cyfr w kluczach. Wymaga <math>O(n+k)</math> dodatkowej pamięci.
- O Radix sort é um algoritmo de ordenação rápido e estável que pode ser usado para ordenar itens que estão identificados por chaves únicas. Cada chave é uma cadeia de caracteres ou número, e o radix sort ordena estas chaves numa qualquer ordem relacionada com a lexicografia. Na ciência da computação, radix sort é um algoritmo de ordenação que ordena inteiros processando dígitos individuais.
- Поразрядная сортировка (Цифровая сортировка) — алгоритм сортировки за линейное время.
- Basamağa göre sıralama bilgisayar bilimlerinde sayıları basamaklarının üzerinde işlem yaparak sıralayan bir sıralama algoritmasıdır. Sayma sayıları adlar ya da tarihler gibi karakter dizilerini göstermek için kullanılabildiği için basamağa göre sıralama algoritması yalnızca sayma sayılarını sıralamak için kullanılan bir algoritma değildir.
- Сортування за розрядами — швидкий стабільний алгоритм впорядкування даних. Застосовується для впорядкування елементів, що є ланцюжками над будь-яким скінченним алфавітом (напр. рядки, або цілі числа).
- 基数排序是一种排序算法，它是这样实现的： 将所有待比较数值(正整数)统一为同样的数位长度,数位较短的数前面补零. 然后, 从最低位开始, 依次进行一次排序. 这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列.
|
![[RDF Data]](/statics/sw-cube.png)
