Ағылшыншамен салыстырыңыз: абзацты басыңыз — түпнұсқа терезеде ашылады. Абзац астындағы EN түймесі оны мәтін ішінде көрсетеді.
Кіріспе
Сорталау алгоритмі
Sorting algorithm
Компьютерлік ғылымда санау сұрыптау – кіші оң бүтін сандар түріндегі кілттеріне сәйкес объектілер жиынын сұрыптауға арналған алгоритм; яғни, ол бүтін санды сұрыптау алгоритмі. Ол әртүрлі кілт мәндеріне ие объектілердің санын санау арқылы жұмыс істейді және осы сандарға префикс қосындысын қолданып, шығыс тізбегінде әрбір кілт мәнінің орнын анықтайды. Оның орындалу уақыты элементтер санына және ең жоғары кілт мәні мен ең төменгі кілт мәні арасындағы айырмаға сызықтық түрде байланысты, сондықтан кілттердің өзгеру диапазоны элементтер санынан айтарлықтай көп болмаған жағдайларда ғана тікелей қолдануға қолайлы. Ол көбінесе радикс сұрыптаудың ішкі алгоритмі ретінде қолданылады, бұл басқа сұрыптау алгоритмі, ол ірі кілттерді тиімдірек өңдей алады. Санау сұрыптау – салыстыру сұрыптау емес; ол кілт мәндерін массивке индекс ретінде пайдаланады, сондықтан салыстыру сұрыптауға арналған ең төменгі шек [[Big O notation#Family of Bachmann–Landau notations lower bound for comparison sorting]] оған қолданылмайды.
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 [[Big O notation#Family of Bachmann–Landau notations lower bound for comparison sorting will not apply.
Вариант алгоритмдер
Егер реттелiп отыратын әрбiр элемент өзi бүтiн сан болса, онда екіншi және үшiншi циклдердi бiрiктiруге болады; екiншi циклде i нөмiрi бар элементтердiң шығарылымға орналасуы керек орынды есептеу орнына, i санының Count[i] көшiрмесiн шығаруға қосады. Бұл алгоритм қайталанған кілттерді жою үшiн де қолданылуы мүмкiн, Count массивін бiт векторымен алмастыру арқылы, кiрiсте бар кiлттер үшiн бiрлiк, ал жоқ кiлттер үшiн нөл сақталады. Егер элементтер толық сандық кілттер болса, екінші және үшінші циклдерді толығымен жоюға болады, ал бiт векторы өзі шығыс ретiнде қызмет етедi, мәндердi нөлден басқа жазбалардың ығысуы ретiнде көрсетедi, диапазонның ең төменгi мәнiне қосылады. Осылайша, кілттер сұрыпталады және дубликаттар осы нұсқада бiт массивіне орналасу арқылы жойылады. Параллель радикс сұрыптау алгоритмiнде пайдаланғанда, кілт өлшемi (радикс өкiлiнiң негiзi) бөлiнген кiшi массивтердiң өлшемiне сәйкес таңдалуы керек. Санау сұрыптау алгоритмінің қарапайымдылығы және оның оңай параллельдеуге болатын префикс сомасының мүмкiндiгi оны ұсақ бөлiмделген параллель алгоритмдерде қолдануға мүмкiндiк бередi. Сипатталғандай, санау сұрыптау орнында атқарылатын алгоритм емес; тiптi санау массивін ескермеген кезде де, оған жеке кiрiс және шығыс массивтерi қажет. Алгоритмдi өзгертуге болады, осылайша, кiрiс ретiнде берiлген массивтің iшiнде элементтердi сұрыпталған тәртiппен орналастыруға болады, тек санау массивін қосымша сақтау ретiнде пайдалана отырып; алайда, санау сұрыптаудың өзгертiлген нұсқасы тұрақты емес.
If each item to be sorted is itself an integer, and used as key as well, then the second and third loops of counting sort can be combined; in the second loop, instead of computing the position where items with key i should be placed in the output, simply append Count[i] copies of the number i to the output. This algorithm may also be used to eliminate duplicate keys, by replacing the Count array with a bit vector that stores a one for a key that is present in the input and a zero for a key that is not present. If additionally the items are the integer keys themselves, both second and third loops can be omitted entirely and the bit vector will itself serve as output, representing the values as offsets of the non zero entries, added to the range's lowest value. Thus the keys are sorted and the duplicates are eliminated in this variant just by being placed into the bit array. For data in which the maximum key size is significantly smaller than the number of data items, counting sort may be parallelized by splitting the input into subarrays of approximately equal size, processing each subarray in parallel to generate a separate count array for each subarray, and then merging the count arrays. When used as part of a parallel radix sort algorithm, the key size (base of the radix representation) should be chosen to match the size of the split subarrays. The simplicity of the counting sort algorithm and its use of the easily parallelizable prefix sum primitive also make it usable in more fine grained parallel algorithms. As described, counting sort is not an in place algorithm; even disregarding the count array, it needs separate input and output arrays. It is possible to modify the algorithm so that it places the items into sorted order within the same array that was given to it as the input, using only the count array as auxiliary storage; however, the modified in place version of counting sort is not stable.