[Logo] Mendo Judge Discussion Board - Forums
  [Search] Search   [Recent Topics] Recent Topics   [Hottest Topics] Hottest Topics   [Members]  Member Listing   [Groups] Back to home page 
Radix Sort  XML
Forum Index » Општа дискусија
Author Message
filip_bujaroski


[Avatar]

Joined: 13/09/2010 21:58:57
Messages: 150
Location: Skopje
Offline

Dali moze nekoj da mi objasni kako funkcionira ova?
I dali funkcionira za site vrednosti ili samo za mali brojki?

Live to play, die for fun.
[Email] [MSN]
hristijan



Joined: 24/01/2010 09:42:46
Messages: 49
Offline

http://en.wikipedia.org/wiki/Radix_sort
filip_bujaroski


[Avatar]

Joined: 13/09/2010 21:58:57
Messages: 150
Location: Skopje
Offline

Go imam chitano toa
Problemot beshe shto ne go razbrav

Live to play, die for fun.
[Email] [MSN]
hristijan



Joined: 24/01/2010 09:42:46
Messages: 49
Offline

filip_bujaroski wrote:Go imam chitano toa
Problemot beshe shto ne go razbrav


Original, unsorted list:
170, 45, 75, 90, 802, 24, 2, 66

Sorting by least significant digit (1st place) gives:
170, 90, 802, 2, 24, 45, 75, 66

Notice that we keep 802 before 2, because 802 occurred before 2 in the original list, and similarly for pairs 170 & 90 and 45 & 75. Sorting by next digit (10s place) gives:
802, 2, 24, 45, 66, 170, 75, 90

Notice that 802 again comes before 2 as 802 comes before 2 in the previous list. Sorting by most significant digit (100s place) gives:
2, 24, 45, 66, 75, 90, 170, 802

It is important to realize that each of the above steps requires just a single pass over the data, since each item can be placed in its correct bucket without having to be compared with other items.


Ова ти е само битно. Почнуваш од последната цифра (и одиш кон првата, одиш единици, десетки, стотки...) и ги сортираш според неа броевите (на wikipedia се underlined, можеш таму да го гледаш овој дел). Откако ќе ги сортираш според неа, одиш на претходната и ги сортираш броевите според неа. Ако наидеш на две исти цифри, тогаш ништо не правиш, ги оставаш броевите во редоследот во кој што си се. Ако во некој број не постои цифра на позиција на која треба да проверуваш, зимаш дека имаш 0 таму.

За да се забраза ова мозеш да користиш buckets (види bucket sort прво ако не знаеш). Се на се, имаш 10 различни цифри значи толку buckets ти требаат. Кога ќе наидеш на број кој има цифра х на местото на кое проверуваш, тогаш го ставаш тој број во bucket х. Откако сите броеви ти се ставени во buckets, ги вадиш броевите почнувајќи од првиот bucket (тој во кој ги имаш ставено тие што имале 0 за таа цифра за која проверуваш). Од тој bucket ги вадиш броевите во редоследот во кој си ги ставил. Откако ќе ги извадиш сите броеви од еден bucket, одиш на следниот. Ако го разгледаш добро примереот, би требало да ти биде јасно зошто ова секогаш работи точно. Ако има нешто нејасно, прашувај.

This message was edited 1 time. Last update was at 30/03/2012 14:08:18

obi1kenobi



Joined: 18/02/2010 20:01:33
Messages: 168
Offline

Уште нешто -- radix sort е линеарен, ама забележи дека има скриен константен логаритамски фактор, така да не мора да значи дека е побрз од quicksort или другите сортови. На пример, за случајов (1,10000000000,10000000001) radix sort ќе биде трагичен избор, а insertion sort или некоја варијанта би требало да помине најбрзо од сите.
 
Forum Index » Општа дискусија
Go to:   
Powered by JForum 2.1.8 © JForum Team