Counting sort (original) (raw)
Counting sort je algoritmus řazení, který je vhodný pro řazení velkého pole prvků, nabývajících jen malý počet různých diskrétních hodnot. Algoritmus řadí stabilně.
| Property | Value |
|---|---|
| dbo:abstract | Counting sort je algoritmus řazení, který je vhodný pro řazení velkého pole prvků, nabývajících jen malý počet různých diskrétních hodnot. Algoritmus řadí stabilně. (cs) Countingsort (von englisch count „zählen“) ist ein stabiles Sortierverfahren, das eine gegebene Folge von Elementen mit linearem Zeitaufwand (Problemkomplexität ) sortiert, wenn deren Sortierschlüssel natürliche Zahlen aus einem beschränkten Intervall mit möglichen Werten sind (oder sich darauf abbilden lassen). Der Algorithmus arbeitet nicht vergleichsbasiert, sondern zählt die Vorkommnisse der Schlüsselwerte – er arbeitet dann adressbasiert. Im Vergleich zum vergleichenden Sortieren mit der bestmöglichen Komplexität ergibt sich ein Vorteil, wenn die Intervalllänge sehr klein gegenüber der Anzahl der zu sortierenden Elemente ist. Gut geeignetes Beispiel: Sortieren aller Einwohner Bayerns (n = 12,85 Mio.) nach ihrem Alter (in vollendeten Jahren: k = 0..150). Schlechtes/nicht umsetzbares Beispiel: Sortieren der Schüler einer Grundschule (n = 300) nach ihrem Nachnamen (Zeichenkette mit max. Länge 40 aus allen möglichen Buchstaben, Umlauten und Sonderzeichen; k ≈ 3540). (de) In computer science, counting sort is an algorithm for sorting a collection of objects according to keys that are small positive integers; that is, it is an integer sorting algorithm. It operates by counting the number of objects that possess distinct key values, and applying prefix sum on those counts to determine the positions of each key value in the output sequence. Its running time is linear in the number of items and the difference between the maximum key value and the minimum key value, so it is only suitable for direct use in situations where the variation in keys is not significantly greater than the number of items. It is often used as a subroutine in radix sort, another sorting algorithm, which can handle larger keys more efficiently. Counting sort is not a comparison sort; it uses key values as indexes into an array and the Ω(n log n) lower bound for comparison sorting will not apply. Bucket sort may be used in lieu of counting sort, and entails a similar time analysis. However, compared to counting sort, bucket sort requires linked lists, dynamic arrays, or a large amount of pre-allocated memory to hold the sets of items within each bucket, whereas counting sort stores a single number (the count of items) per bucket. (en) El ordenamiento por cuentas (counting sort en inglés) es un algoritmo de ordenamiento en el que se cuenta el número de elementos de cada clase para luego ordenarlos. Solo puede ser utilizado por tanto para ordenar elementos que sean contables (como los números enteros en un determinado intervalo, pero no los números reales, por ejemplo). El primer paso consiste en averiguar cuál es el intervalo dentro del que están los datos a ordenar (valores mínimo y máximo). Después se crea un vector de números enteros con tantos elementos como valores haya en el intervalo [mínimo, máximo], y a cada elemento se le da el valor 0 (0 apariciones). Tras esto se recorren todos los elementos a ordenar y se cuenta el número de apariciones de cada elemento (usando el vector que hemos creado). Por último, basta con recorrer este vector para tener todos los elementos ordenados. (es) Le tri comptage (counting sort en anglais), appelé aussi tri casier, est un algorithme de tri par dénombrement qui s'applique sur des valeurs entières. (fr) Il Counting sort è un algoritmo di ordinamento per valori numerici interi con complessità lineare. L'algoritmo si basa sulla conoscenza a priori dell'intervallo in cui sono compresi i valori da ordinare. (it) Counting sort, soms ook count-sort genoemd, is een extreem simpel sorteeralgoritme, dat alleen kan worden gebruikt voor gehele getallen en daarmee vergelijkbare objecten. Juist door de beperkte toepassingsmogelijkheden, kan het een zeer efficiënte manier van sorteren zijn. Een voorwaarde daarvoor is dat de kleinste en de grootste voorkomende waarde bekend zijn, en dat de te sorteren getallen in een relatief klein bereik liggen. (nl) Sortowanie przez zliczanie (ang. counting sort) – metoda sortowania danych, która polega na sprawdzeniu ile wystąpień kluczy mniejszych od danego występuje w sortowanej tablicy. Algorytm zakłada, że klucze elementów należą do skończonego zbioru (np. są to liczby całkowite z przedziału 0..100), co ogranicza możliwości jego zastosowania. (pl) Сортировка подсчётом (англ. counting sort; сортировка посредством подсчёта англ. sorting by counting) — алгоритм сортировки, в котором используется диапазон чисел сортируемого массива (списка) для подсчёта совпадающих элементов. Применение сортировки подсчётом целесообразно лишь тогда, когда сортируемые числа имеют (или их можно отобразить в) диапазон возможных значений, который достаточно мал по сравнению с сортируемым множеством, например, миллион натуральных чисел меньших 1000. Предположим, что входной массив состоит из целых чисел в диапазоне от до , где . Далее алгоритм будет обобщён для произвольного целочисленного диапазона. Существует несколько модификаций сортировки подсчётом, ниже рассмотрены три линейных и одна квадратичная, которая использует другой подход, но имеет то же название. (ru) Counting sort é um algoritmo de ordenação estável cuja complexidade é O(n). As chaves podem tomar valores entre 0 e M-1. Se existirem k0 chaves com valor 0, então ocupam as primeiras k0 posições do vetor final: de 0 a k0-1. A ideia básica do counting sort é determinar, para cada entrada x, o número de elementos menor que x. Essa informação pode ser usada para colocar o elemento x diretamente em sua posição no array de saída. Por exemplo, se há 17 elementos menores que x, então x pertence a posição 18. Esse esquema deve ser ligeiramente modificado quando houver vários elementos com o mesmo valor, uma vez que nós não queremos que sejam colocados na mesma posição. (pt) 计数排序（Counting sort）是一种稳定的线性时间排序算法。该算法于1954年由 Harold H. Seward 提出。计数排序使用一个额外的数组，其中第i个元素是待排序数组中值等于的元素的个数。然后根据数组来将中的元素排到正确的位置。 (zh) Сортування підрахунком (англ. Counting sort) — алгоритм впорядкування, що застосовується при малій кількості різних елементів (ключів) у масиві даних. Час його роботи лінійно залежить як від загальної кількості елементів у масиві так і від кількості різних елементів. (uk) |
| dbo:wikiPageExternalLink | https://web.archive.org/web/20130602221151/http:/users.cs.cf.ac.uk/C.L.Mumford/tristan/CountingSort.html https://xlinux.nist.gov/dads/HTML/countingsort.html%7Caccess-date=2011-04-21 http://users.cs.cf.ac.uk/C.L.Mumford/tristan/CountingSort.html http://www.cs.usfca.edu/~galles/visualization/CountingSort.html |
| dbo:wikiPageID | 99864 (xsd:integer) |
| dbo:wikiPageLength | 12459 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1116038200 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Algorithm dbr:Dynamic_array dbr:Lower_bound dbr:Stable_sort dbr:Comparison_sort dbr:Computer_science dbr:Parallel_algorithm dbr:Prefix_sum dbc:Sorting_algorithms dbr:Linked_list dbr:Histogram dbr:Harold_H._Seward dbr:Array_data_structure dbr:Big_O_notation dbc:Stable_sorts dbr:Collection_(abstract_data_type) dbr:Sorting_Algorithm dbr:Sorting_algorithm dbr:In-place_algorithm dbr:Integer dbr:Integer_sorting dbr:Bucket_sort dbr:Radix_sort dbr:Bit_vector |
| dbp:class | dbr:Sorting_Algorithm |
| dbp:data | dbr:Array_data_structure |
| dbp:date | 2013-06-02 (xsd:date) |
| dbp:time | , where k is the range of the non-negative key values. (en) |
| dbp:url | https://web.archive.org/web/20130602221151/http:/users.cs.cf.ac.uk/C.L.Mumford/tristan/CountingSort.html |
| dbp:wikiPageUsesTemplate | dbt:Citation dbt:Math dbt:Mvar dbt:Reflist dbt:Short_description dbt:Webarchive dbt:Wikibooks dbt:Infobox_algorithm dbt:Sorting |
| dcterms:subject | dbc:Sorting_algorithms dbc:Stable_sorts |
| gold:hypernym | dbr:Algorithm |
| rdf:type | dbo:Software yago:WikicatSortingAlgorithms yago:WikicatStableSorts yago:Abstraction100002137 yago:Act100030358 yago:Activity100407535 yago:Algorithm105847438 yago:Category105838765 yago:Cognition100023271 yago:Concept105835747 yago:Content105809192 yago:Event100029378 yago:Idea105833840 yago:Kind105839024 yago:Procedure101023820 yago:PsychologicalFeature100023100 yago:YagoPermanentlyLocatedEntity yago:Rule105846932 yago:SortingAlgorithm105847658 |
| rdfs:comment | Counting sort je algoritmus řazení, který je vhodný pro řazení velkého pole prvků, nabývajících jen malý počet různých diskrétních hodnot. Algoritmus řadí stabilně. (cs) Le tri comptage (counting sort en anglais), appelé aussi tri casier, est un algorithme de tri par dénombrement qui s'applique sur des valeurs entières. (fr) Il Counting sort è un algoritmo di ordinamento per valori numerici interi con complessità lineare. L'algoritmo si basa sulla conoscenza a priori dell'intervallo in cui sono compresi i valori da ordinare. (it) Counting sort, soms ook count-sort genoemd, is een extreem simpel sorteeralgoritme, dat alleen kan worden gebruikt voor gehele getallen en daarmee vergelijkbare objecten. Juist door de beperkte toepassingsmogelijkheden, kan het een zeer efficiënte manier van sorteren zijn. Een voorwaarde daarvoor is dat de kleinste en de grootste voorkomende waarde bekend zijn, en dat de te sorteren getallen in een relatief klein bereik liggen. (nl) Sortowanie przez zliczanie (ang. counting sort) – metoda sortowania danych, która polega na sprawdzeniu ile wystąpień kluczy mniejszych od danego występuje w sortowanej tablicy. Algorytm zakłada, że klucze elementów należą do skończonego zbioru (np. są to liczby całkowite z przedziału 0..100), co ogranicza możliwości jego zastosowania. (pl) 计数排序（Counting sort）是一种稳定的线性时间排序算法。该算法于1954年由 Harold H. Seward 提出。计数排序使用一个额外的数组，其中第i个元素是待排序数组中值等于的元素的个数。然后根据数组来将中的元素排到正确的位置。 (zh) Сортування підрахунком (англ. Counting sort) — алгоритм впорядкування, що застосовується при малій кількості різних елементів (ключів) у масиві даних. Час його роботи лінійно залежить як від загальної кількості елементів у масиві так і від кількості різних елементів. (uk) In computer science, counting sort is an algorithm for sorting a collection of objects according to keys that are small positive integers; that is, it is an integer sorting algorithm. It operates by counting the number of objects that possess distinct key values, and applying prefix sum on those counts to determine the positions of each key value in the output sequence. Its running time is linear in the number of items and the difference between the maximum key value and the minimum key value, so it is only suitable for direct use in situations where the variation in keys is not significantly greater than the number of items. It is often used as a subroutine in radix sort, another sorting algorithm, which can handle larger keys more efficiently. (en) Countingsort (von englisch count „zählen“) ist ein stabiles Sortierverfahren, das eine gegebene Folge von Elementen mit linearem Zeitaufwand (Problemkomplexität ) sortiert, wenn deren Sortierschlüssel natürliche Zahlen aus einem beschränkten Intervall mit möglichen Werten sind (oder sich darauf abbilden lassen). Der Algorithmus arbeitet nicht vergleichsbasiert, sondern zählt die Vorkommnisse der Schlüsselwerte – er arbeitet dann adressbasiert. Im Vergleich zum vergleichenden Sortieren mit der bestmöglichen Komplexität ergibt sich ein Vorteil, wenn die Intervalllänge sehr klein gegenüber der Anzahl der zu sortierenden Elemente ist. (de) El ordenamiento por cuentas (counting sort en inglés) es un algoritmo de ordenamiento en el que se cuenta el número de elementos de cada clase para luego ordenarlos. Solo puede ser utilizado por tanto para ordenar elementos que sean contables (como los números enteros en un determinado intervalo, pero no los números reales, por ejemplo). (es) Counting sort é um algoritmo de ordenação estável cuja complexidade é O(n). As chaves podem tomar valores entre 0 e M-1. Se existirem k0 chaves com valor 0, então ocupam as primeiras k0 posições do vetor final: de 0 a k0-1. (pt) Сортировка подсчётом (англ. counting sort; сортировка посредством подсчёта англ. sorting by counting) — алгоритм сортировки, в котором используется диапазон чисел сортируемого массива (списка) для подсчёта совпадающих элементов. Применение сортировки подсчётом целесообразно лишь тогда, когда сортируемые числа имеют (или их можно отобразить в) диапазон возможных значений, который достаточно мал по сравнению с сортируемым множеством, например, миллион натуральных чисел меньших 1000. (ru) |
| rdfs:label | Counting sort (cs) Countingsort (de) Counting sort (en) Ordenamiento por cuentas (es) Counting sort (it) Tri comptage (fr) 계수 정렬 (ko) Sortowanie przez zliczanie (pl) Counting sort (nl) Counting sort (pt) Сортировка подсчётом (ru) Сортування підрахунком (uk) 计数排序 (zh) |
| owl:sameAs | dbpedia-ru:Counting sort freebase:Counting sort yago-res:Counting sort wikidata:Counting sort dbpedia-bg:Counting sort dbpedia-cs:Counting sort dbpedia-de:Counting sort dbpedia-es:Counting sort dbpedia-fa:Counting sort dbpedia-fi:Counting sort dbpedia-fr:Counting sort dbpedia-he:Counting sort http://hy.dbpedia.org/resource/Հաշվողական_տեսակավորում dbpedia-it:Counting sort dbpedia-ka:Counting sort dbpedia-ko:Counting sort http://ml.dbpedia.org/resource/കൗണ്ടിങ്ങ്_സോർട്ട് dbpedia-nl:Counting sort dbpedia-pl:Counting sort dbpedia-pt:Counting sort dbpedia-sk:Counting sort dbpedia-sr:Counting sort dbpedia-tr:Counting sort dbpedia-uk:Counting sort dbpedia-vi:Counting sort dbpedia-zh:Counting sort https://global.dbpedia.org/id/B9MQ |
| prov:wasDerivedFrom | wikipedia-en:Counting_sort?oldid=1116038200&ns=0 |
| foaf:isPrimaryTopicOf | wikipedia-en:Counting_sort |
| is dbo:knownFor of | dbr:Harold_H._Seward |
| is dbo:wikiPageRedirects of | dbr:Tally_sort dbr:Set_sort dbr:Count_sort dbr:Math_sort dbr:Bit_sort dbr:Ultrasort |
| is dbo:wikiPageWikiLink of | dbr:List_of_algorithms dbr:Bead_sort dbr:Retrieval_Data_Structure dbr:Anatree dbr:Comparison_sort dbr:Kruskal's_algorithm dbr:Pigeonhole_sort dbr:Prefix_sum dbr:Tally_sort dbr:Minimum_spanning_tree-based_segmentation dbr:Harold_H._Seward dbr:Sorting_algorithm dbr:Integer_sorting dbr:Bucket_sort dbr:Radix_sort dbr:Selection_sort dbr:Selection_algorithm dbr:List_of_terms_relating_to_algorithms_and_data_structures dbr:Sorted_array dbr:Set_sort dbr:Count_sort dbr:Math_sort dbr:Bit_sort dbr:Ultrasort |
| is foaf:primaryTopic of | wikipedia-en:Counting_sort |