Сортиране чрез броене

В информатиката сортирането чрез броене е алгоритъм за сортиране на съвкупност от обекти спрямо техните ключове, които са малки цели числа. Алгоритъмът брои обектите с различни стойности на ключа, след което разполага в изходния масив съответен брой обекти от всяка стойност на ключа последователно – от най-малкия до най-големия ключ. Времето за изпълнение е линейно спрямо броя на елементите и спрямо разликата между максималната и минималната ключова стойност, затова е подходящ само в случаите, когато разликата в ключовете не е много по-голяма от броя на елементите. Въпреки това често се използва като подпрограма в други алгоритми за сортиране, например в метода на бройните системи, който по-добре се справя с големи ключове.

Тъй като сортирането чрез броене използва ключови стойности като индекси в масив, то не сортира чрез сравняване и долната граница Ω(n log n) не се отнася за него. Bucket сортирането може да бъде използвано за много подобни случаи, в които се използва и сортирането чрез броене. Въпреки това, сравнено със сортирането чрез броене, bucket сортирането изисква свързани списъци, динамични масиви или голямо количество заделена памет, където да съхранява групите от елементи, разпределени в bucket-и, докато сортирането чрез броене пази едно-единствено число (броя елементи) за всеки bucket.

Предположения за входните и изходните данни

В най-общия случай, входните данни за сортирането чрез броене, съдържат набор от n елементи, всеки от които има за ключ неотрицателно цяло число с максимална стойност k. В някои описания на сортирането чрез броене входните данни, които трябва да бъдат сортирани, за по-лесно се приемат като поредица от цели числа. Това опростяване обаче не е съвместимо с много приложения на сортирането чрез броене. Например, когато се използва като подпрограма в Radix сортирането, ключовете за всяко извикване на сортирането чрез броене са отделните цифри на елементи с по-големи ключове; не би било достатъчно да се върне само подреден списък с цифри на ключовете, отделени от елементите.

В приложения като Radix сортирането границата на максималния ключ ще бъде известна предварително и може да се счита като част от входните данни на алгоритъма. Въпреки това, ако стойността на k е все още неизвестна, може да бъде изчислена с допълнителен цикъл върху данните, за да се определи максималната стойност на ключа, който всъщност се проявява в рамките на данните.

Изходните данни представляват масив от елементи, подредени по стойността на техните ключове. Заради прилагането на Radix сортиране, е важно сортирането чрез броене да бъде надеждно: ако два елемента имат една и съща стойност на ключа, те трябва да имат същата изходна позиция, каквато са имали и във входящите данни.

Алгоритъм

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

Това може да бъде изразено със следния псевдокод:

''' изчислява се хистограмата: '''
# allocate an array Count[0..k]; THEN
# initialize each array cell to zero; THEN
for each input item x:
 increment Count[key(x)]

''' изчислява се началния индекс за всеки ключ: '''
total = 0
for i = 0, 1, ... k:
 oldCount = Count[i]
 Count[i] = total
 total = total + oldCount

''' входните данни се копират подредени в изходния масив: '''
# allocate an output array Output[0..n-1]; THEN
for each input item x:
 Output[Count[key(x)]] = x
 increment Count[key(x)]
return Output

След първия цикъл Count[i] съхранява броя елементи с ключ, равен на i. След второто обхождане той вече съхранява броя елементи с ключ, по-малък от i, който е същият като първия индекс, на който елемент с ключ i трябва да бъде запазен в изходния масив. По време на третия цикъл Count[i] винаги запазва следващата позиция в изходния масив, където трябва да бъде съхранен елемент с ключ i, така че всеки елемент е преместен на вярната позиция в изходния масив. Относителният ред на елементи с еднакви ключове се съхранява тук, т.е. това е едно стабилно сортиране.

Анализ

Тъй като алгоритъмът използва само for цикли без рекурсия или извикване на подпрограма, той е лесен за анализиране. Инициализацията на масива Count и вторият цикъл, който пресмята префикс сумата на масива Count – всяко едно от тези действия обхожда най-много k + 1 пъти и затова отнема O(k) време. Другите два for цикъла и инициялизацията на изходния масив – всяко изисква O(n) време. Затова времето за изпълнение на този алгоритъм е сумата на времената, необходими за изпълнението на тези стъпки, O(n + k).

Тъй като се използват масиви с дължина k + 1 и n, общата памет, използвана от алгоритъма, също е O(n + k). За проблемните случаи, в които максималната ключова стойност е значително по-малка, от броя на елементите, сортирането чрез броене може да бъде високо ефективно, тъй като единствената памет, която използва, освен входните данни и изходния масив, е масивът Count, който използва O(k) място.

Варианти на алгоритъма

Ако всеки елемент, който трябва да се сортира, е цяло число и се използва и за ключ, тогава вторият и третият цикъл на сортирането чрез броене могат да бъдат обединени; вместо във втория масив да се пресмята позицията в изходния масив, където трябва да бъде поставен елемент с ключ i, към изходния масив може просто да бъдат прикачени Count[i] копия на числото i.

Този алгоритъм може също да бъде използван за предотвратяване на дублиращи се ключове, като масивът Count бъде заменен с побитов масив (линк), който съхранява one за ключ, който е наличен във входните данни, и zero за такъв, който не е. Допълнително, ако елементите са самите целочислени ключове, и вторият, и третият цикъл могат да бъдат изцяло пропуснати и побитовият масив ще служи като изход, представляващ стойностите като офсет на ненулеви записи, добавени към най-малката стойност на обхвата. По този начин ключовете са подредени и дублирането им е предотвратено единствено чрез поставянето им в побитов масив. Това е и начинът, по който работи Решето на Ератостен.

За данните, при които максималният ключ е значително по-малък от броя на елементите, сортирането чрез броене може да бъде паралелизирано чрез разделяне на входа на подмасиви с приблизително еднакъв размер, обработвайки всеки подмасив паралелно, за да генерира отделен масив Count, и след това тези масиви да бъдат съединени. Когато се използва като част от паралелен Radix алгоритъм, големината на ключа трябва да бъде избрана така, че да съответства на големината на подмасивите. Опростеността на алгоритъма за сортиране чрез броене го прави също така подходящ за по-фини паралелни алгоритми.

Както беше описано, сортирането чрез броене не се нуждае от заделяне на допълнителна памет; дори пренебрегвайки масива Count, той се нуждае от отделни входни и изходни масиви. Възможно е алгоритъмът да бъде променен така, че той да поставя елементите в правилен ред в същия масив, който ни е даден като входни данни, използвайки единствено масива Count за помощно съхранение; въпреки това, модифицираната версия на сортирането чрез броене, не е стабилна.

История

Въпреки че самият Radix алгоритъм датира от много по-дълго, сортирането чрез броене и неговото приложение в Radix алгоритъма били измислени от Харолд Х. Стюард през 1954.

Източници

1. ^ a b c d e f g h i Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001), „8.2 Counting Sort“, Introduction to Algorithms (2nd ed.), MIT Press and McGraw-Hill, pp. 168 – 170, ISBN 0-262-03293-7 . See also the historical notes on page 181.
2. ^ a b c d e Edmonds, Jeff (2008), „5.2 Counting Sort (a Stable Sort)“, How to Think about Algorithms, Cambridge University Press, pp. 72 – 75, ISBN 978-0-521-84931-9 .
3. ^ a b c d e Sedgewick, Robert (2003), „6.10 Key-Indexed Counting“, Algorithms in Java, Parts 1 – 4: Fundamentals, Data Structures, Sorting, and Searching (3rd ed.), Addison-Wesley, pp. 312 – 314 .
4. ^ a b Knuth, D. E. (1998), The Art of Computer Programming, Volume 3: Sorting and Searching (2nd ed.), Addison-Wesley, ISBN 0-201-89685-0 . Section 5.2, Sorting by counting, pp. 75 – 80, and historical notes, p. 170.
5. ^ Burris, David S.; Schember, Kurt (1980), „Sorting sequential files with limited auxiliary storage“, Proceedings of the 18th annual Southeast Regional Conference, New York, NY, USA: ACM, pp. 23 – 31, doi:10.1145/503838.503855 .
6. ^ Zagha, Marco; Blelloch, Guy E. (1991), „Radix sort for vector multiprocessors“, Proceedings of Supercomputing '91, November 18 – 22, 1991, Albuquerque, NM, USA, IEEE Computer Society / ACM, pp. 712 – 721, doi:10.1145/125826.126164 .
7. ^ Reif, John H. (1985), „An optimal parallel algorithm for integer sorting“, Proc. 26th Annual Symposium on Foundations of Computer Science (FOCS 1985), pp. 496 – 504, doi:10.1109/SFCS.1985.9 .
8. ^ Seward, H. H. (1954), „2.4.6 Internal Sorting by Floating Digital Sort“, Information sorting in the application of electronic digital computers to business operations, Master's thesis, Report R-232, [[Massachusetts Institute of Technology, Digital Computer Laboratory, pp. 25–28.

Външни препратки

• Counting Sort html5 visualization
• Demonstration applet from Cardiff University
• Kagel, Art S. (2 юни 2006), "counting sort", in Black, Paul E., Dictionary of Algorithms and Data Structures, U.S. National Institute of Standards and Technology, Посетен на 21 април 2011.
• A simple Counting Sort implementation.

Тази страница частично или изцяло представлява превод на страницата Counting sort в Уикипедия на английски. Оригиналният текст, както и този превод, са защитени от Лиценза „Криейтив Комънс – Признание – Споделяне на споделеното“, а за съдържание, създадено преди юни 2009 година – от Лиценза за свободна документация на ГНУ. Прегледайте историята на редакциите на оригиналната страница, както и на преводната страница, за да видите списъка на съавторите. ​ ВАЖНО: Този шаблон се отнася единствено до авторските права върху съдържанието на статията. Добавянето му не отменя изискването да се посочват конкретни източници на твърденията, които да бъдат благонадеждни.​