-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathRadixSort.py
61 lines (46 loc) · 15.1 KB
/
RadixSort.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
# Python program for implementation of Radix Sort
# A function to do counting sort of arr[] according to
# the digit represented by exp.
def countingSort(arr, exp1):
n = len(arr)
# The output array elements that will have sorted arr
output = [0] * (n)
# initialize count array as 0
count = [0] * (10)
# Store count of occurrences in count[]
for i in range(0, n):
index = (arr[i]/exp1)
count[ (index)%10 ] += 1
# Change count[i] so that count[i] now contains actual
# position of this digit in output array
for i in range(1,10):
count[i] += count[i-1]
# Build the output array
i = n-1
while i>=0:
index = (arr[i]/exp1)
output[ count[ (index)%10 ] - 1] = arr[i]
count[ (index)%10 ] -= 1
i -= 1
# Copying the output array to arr[],
# so that arr now contains sorted numbers
i = 0
for i in range(0,len(arr)):
arr[i] = output[i]
# Method to do Radix Sort
def radixSort(arr):
# Find the maximum number to know number of digits
max1 = max(arr)
# Do counting sort for every digit. Note that instead
# of passing digit number, exp is passed. exp is 10^i
# where i is current digit number
exp = 1
while max1/exp > 0:
countingSort(arr,exp)
exp *= 10
# Driver code to test above
arr = [11298605, 5604664, 6606181, 7606244, 89878, 17330273, 14494424, 1921010, 10749888, 1758055, 942667, 12347817, 8753694, 16204, 6784340, 4726582, 10700592, 1123840, 15479230, 5359393, 12059222, 5067668, 937954, 9593104, 17428846, 8618981, 13727950, 9498940, 14916330, 7459630, 9329417, 15676433, 249836, 9141680, 15880202, 15132581, 283123, 7509631, 17302590, 11720604, 7233192, 8962869, 1330895, 4145506, 9537569, 17712354, 1049045, 3900830, 1666498, 2784113, 3606956, 13318534, 4650357, 17636900, 13148647, 1627898, 118499, 5817010, 10268659, 8124369, 4389038, 11462642, 5754426, 10974319, 11195006, 18152266, 18255352, 10919806, 9784723, 15849901, 815355, 12034393, 3886031, 15247594, 1342283, 8488852, 9084486, 850551, 15984642, 5404585, 4139343, 15662509, 8987665, 17978406, 6965170, 14114885, 13497297, 4658685, 13674444, 724337, 15828405, 1293441, 1857991, 6107656, 7003122, 15484048, 19836606, 13869257, 7664535, 6878405, 18189763, 19784866, 632697, 2615811, 1533860, 5789815, 15690305, 9223654, 19474706, 14771104, 148774, 7064267, 14054365, 13622664, 11610451, 5431612, 11799600, 4608765, 4256952, 6131256, 9630679, 6019595, 4832029, 2431071, 1284160, 6778530, 16714979, 16498249, 14789743, 12552388, 5289521, 4769130, 16393249, 3931418, 12482032, 3241199, 11643734, 9868596, 15979407, 5813647, 13613579, 8198530, 11269948, 8220255, 8422213, 463995, 4160290, 5504342, 18295621, 10892339, 8257401, 14013218, 16106441, 14691859, 15966477, 4112259, 19030940, 4939937, 5470537, 7944206, 12350392, 12489362, 2376527, 19655914, 3685652, 1356445, 2029481, 14316659, 15135576, 11920925, 17111964, 8341881, 1501935, 11135021, 13874461, 12212311, 6048511, 19036006, 1727562, 13070190, 13077366, 753307, 3052001, 17350695, 14445604, 9082326, 8314673, 8945627, 15375723, 1211015, 170765, 709916, 5543641, 16528976, 15504781, 12761442, 11914910, 2836090, 2994717, 432107, 9516662, 15119867, 4391514, 414918, 17169607, 2111138, 10391091, 8998084, 18543672, 4759080, 16442436, 16199477, 13671948, 17003097, 1797507, 3982954, 6521775, 2998438, 103205, 11220279, 13519379, 1282220, 317621, 566304, 19704421, 18665244, 12107079, 11838188, 4731568, 589005, 12778705, 12119062, 173613, 13914734, 19988825, 19660030, 14122923, 13569791, 19946947, 18487645, 16488360, 16441553, 16088679, 8533577, 16197016, 2123943, 18305390, 14624770, 5450654, 13074907, 11654868, 19507802, 16448986, 3412660, 14295771, 5290311, 7195051, 7590245, 16144359, 11676707, 4109685, 19253769, 5293180, 6732141, 14598883, 18986834, 17129436, 8963595, 956500, 2872219, 19976292, 12918096, 5620063, 14120786, 10973143, 10652913, 12355519, 1370516, 2654888, 14225947, 460882, 1971153, 18373074, 8924448, 11555771, 7173195, 4758594, 19883986, 5536700, 19619312, 14833228, 19126458, 10725768, 13750808, 9121665, 4978318, 15224384, 15649436, 12989299, 7942440, 17262961, 2405903, 4322473, 2591818, 14532391, 1641069, 2921731, 6405318, 14813579, 8470310, 2694808, 6220752, 11209433, 15200281, 14741201, 3651285, 1483213, 16952099, 15187169, 10081044, 19061066, 3284405, 6137086, 8415847, 17809619, 5521103, 14376927, 18805910, 10695786, 10816051, 14409161, 11690362, 5362981, 14236499, 14643196, 7554284, 10046091, 14539890, 11071586, 17476026, 15477108, 13758192, 12576519, 8799186, 5642035, 10381374, 17340922, 8354766, 5147797, 15670228, 8263550, 14345411, 7284470, 9507654, 18964548, 3086145, 11650414, 4032564, 19300584, 8589963, 11047711, 10611592, 18050514, 15851071, 18274805, 16148098, 8209204, 11159333, 2233075, 5451255, 19013952, 18316595, 5735389, 16767337, 885860, 7369349, 15310872, 14803226, 10619602, 16799446, 15702396, 7219624, 4059191, 2104018, 8765770, 7805245, 12305026, 4774909, 16212903, 19986714, 6391612, 16485222, 7376165, 10954259, 824712, 5011380, 17416604, 4323949, 18896916, 2278618, 7419022, 8345807, 19594995, 19867137, 14528664, 3643601, 14525427, 16526570, 8679243, 16865806, 16346687, 11295519, 18523772, 8521133, 18844115, 5208434, 3842893, 12211525, 4949677, 2564024, 10596002, 8959997, 6194068, 1086377, 16983132, 13341171, 18965191, 4122815, 15446628, 5324950, 12560672, 4536532, 13348282, 6107163, 7477552, 13071334, 3742018, 7084370, 17358552, 5520843, 14996765, 14568261, 940057, 4307367, 17496662, 2905049, 13267197, 14964126, 15658251, 14325904, 2547405, 4840737, 894048, 14047811, 3597899, 16227155, 11733881, 14628083, 5405981, 6997932, 15111439, 1396192, 1946751, 8687762, 11274775, 5590579, 19513692, 16534747, 3897282, 16505257, 12877549, 10204440, 10516177, 17197096, 1080029, 5329080, 1719618, 6366006, 17546667, 9154646, 9430525, 11931966, 4965946, 7139604, 4161303, 8751820, 2444324, 11665777, 10021573, 12686175, 526937, 18927201, 4765528, 14336666, 6164211, 6238941, 15254372, 3051663, 15915184, 423885, 2800959, 12259623, 15509602, 10885591, 2703989, 8045736, 17822920, 2517492, 19673765, 9200128, 2973286, 8128316, 15892677, 12726484, 7838060, 14350717, 18488551, 305000, 15766712, 15052412, 4223989, 17640627, 5486134, 6804333, 11188974, 19672604, 10987650, 5279539, 10342240, 15640491, 14626050, 3131590, 8026817, 15133141, 9397343, 3234982, 1697560, 14923477, 334654, 7709459, 18308356, 17111261, 11882921, 11710747, 6443754, 15748959, 5368925, 17522109, 4131781, 19161101, 15449600, 17881839, 14777631, 12737596, 17209672, 6902676, 10628871, 3940636, 19705958, 10721390, 5897878, 8102700, 3296080, 2179711, 18120696, 18171750, 16248246, 11067274, 1624636, 9647281, 7276449, 13959838, 196492, 6491645, 3483415, 7789797, 13760720, 12090344, 19119687, 19553651, 7643056, 17222798, 11872225, 12201067, 16460278, 13947855, 17376512, 10820397, 6476138, 3866113, 16081108, 18133723, 17837709, 4764892, 8086320, 13598996, 1721570, 9903114, 18047836, 14221752, 8538998, 4149428, 6246166, 15959939, 4391787, 35189, 10534031, 14926067, 8810534, 5613411, 16420914, 18324195, 1646316, 17887744, 7458547, 11604608, 15854284, 2166998, 3690657, 5461231, 4206483, 19876090, 7041733, 6565095, 19122752, 13433460, 3133620, 4523176, 16644492, 11316474, 9359215, 10399830, 4602199, 14693258, 6128484, 8455858, 3107525, 16419992, 16152605, 12677634, 10123690, 5481628, 13739354, 19346779, 5932012, 17636071, 4913120, 10851916, 2637139, 311003, 18626625, 6557157, 2858724, 3324997, 1860575, 10380132, 13041193, 12210170, 12000844, 217362, 17821617, 17247816, 171834, 7389245, 15878697, 2632232, 17308155, 5984937, 6888764, 13089565, 14418438, 14210931, 3402794, 1958261, 12734317, 19655317, 17006918, 16613369, 10207815, 4499646, 9097381, 1700004, 4392841, 9913519, 19932073, 7972898, 9460146, 12011767, 19271622, 9537559, 8377235, 12247816, 2303451, 11312696, 11838651, 2025087, 18293059, 11654294, 15383061, 14762348, 13910970, 4921155, 783446, 17043203, 5431446, 15030725, 14209694, 18554820, 18967304, 7935274, 12062360, 10727319, 18039884, 19377911, 1939942, 4962661, 5944653, 14142243, 3288445, 18384107, 8937640, 10124303, 15034855, 16699, 15445777, 10680359, 2291697, 8464225, 12130871, 6980112, 14637786, 14375033, 8638974, 365773, 8618560, 14798131, 1455373, 7158658, 13418765, 9795252, 2576805, 9176181, 12283162, 1670327, 15745611, 18638997, 3494293, 1840864, 6643805, 8007141, 4988787, 9053778, 9724007, 12933804, 10792159, 15227373, 10451125, 3562781, 5836200, 12333620, 19074026, 16683082, 16844525, 13132351, 13689939, 11712279, 1589543, 4519070, 6932493, 1263879, 10422070, 4525916, 9493390, 19458789, 12536861, 19392945, 10070677, 19625101, 7541294, 10502664, 7927698, 17745900, 14342733, 3104093, 7400338, 14824725, 10525968, 8583201, 17566324, 19791657, 1874913, 3026648, 601599, 14847369, 6109912, 14928425, 16882, 19513560, 10137050, 19854392, 6907586, 4073176, 215937, 6187029, 5915980, 7211341, 14047706, 613454, 2343741, 3674354, 10298218, 16641898, 4503404, 9099982, 12227422, 7874176, 7652629, 4765108, 1319663, 5464638, 8642218, 13232826, 14554825, 5093223, 11575918, 16403272, 99705, 17173461, 16584489, 17301678, 11875892, 14920900, 10848496, 14744979, 6657594, 18389606, 15276053, 11210101, 5588388, 18524546, 8507798, 135806, 10883257, 15313865, 18134114, 17241670, 16199380, 11672599, 3222992, 9174541, 10740087, 2949889, 17921788, 18775970, 6611397, 13063190, 18417507, 13894957, 13233817, 12524422, 15057881, 17865410, 4830251, 11881578, 5030181, 8990239, 2280758, 15835426, 19625874, 17998196, 12344579, 3504265, 9344539, 9624386, 18418010, 13774769, 568942, 10470238, 17186975, 17814063, 7318014, 18374816, 2890997, 19510193, 14180180, 5849923, 5065834, 4365172, 8183500, 61427, 14103488, 1668284, 3402666, 4878481, 17672154, 4754742, 11757863, 13842010, 13410315, 14050638, 3155761, 19263172, 15793041, 18735661, 10723306, 10195570, 6773691, 1136869, 5477128, 1470131, 5374607, 13925661, 1429548, 2757846, 6861987, 17726414, 18631309, 8300396, 6448164, 3922423, 16382026, 4374282, 19098879, 6692664, 18058193, 5106074, 10842479, 1571014, 8422910, 19394906, 8161869, 15210747, 10617560, 8293150, 8228713, 4698047, 3695658, 3332712, 9838202, 899410, 17226069, 3582173, 10911997, 8285683, 2335831, 16520039, 12332849, 16965784, 19707153, 7191508, 15007534, 13518978, 4321862, 9871663, 9702732, 7659832, 16951062, 11955661, 3666488, 15779854, 5013150, 19888024, 2279267, 9293699, 1222454, 4700447, 3743797, 12020126, 2344113, 14910662, 17309844, 3316513, 16027207, 13687598, 11493022, 1401592, 18279371, 19288499, 2693345, 395606, 4230035, 1092690, 19284277, 12647178, 2649600, 10455757, 4851786, 4935039, 3932211, 19271074, 1737951, 10462072, 1086041, 18344252, 12139728, 13411674, 18157798, 13393211, 7862139, 15930237, 8643893, 4952897, 6729241, 4247508, 10820099, 1505433, 10796224, 16563093, 15602573, 13416899, 6226136, 9801982, 8617117, 19493222, 7723773, 7222732, 18117192, 4940614, 7218296, 17747699, 12526022, 19096227, 9091771, 8328986, 18656192, 18934565, 8629229, 19930916, 18784270, 307390, 6118470, 19151672, 16984743, 6672786, 14570016, 11385203, 15732477, 5363637, 16644565, 7956246, 6331299, 5883538, 10195783, 9994944, 11827432, 3247522, 11604877, 5381114, 11803146, 9848402, 2463004, 4987317, 9121817, 11096189, 10025165, 17026071, 14452618, 10304720, 19221019, 19695753, 17363218, 12316617, 10912198, 7211203, 14465052, 3975945, 12841625, 11521593, 18625418, 19831911, 8093361, 4058974, 9613595, 15450697, 7933957, 9094116, 8659085, 4577362, 12276728, 3507182, 11491156, 16010284, 7114880, 13885097, 11934399, 5565771, 8928951, 17962778, 2341637, 8431144, 18239962, 2943904, 6850071, 12904027, 12369621, 13447312, 10407619, 8983507, 6025118, 1258308, 18249905, 12921478, 11429887, 56617, 127651, 18891070, 3440423, 17218433, 9666734, 1073540, 9343963, 10105685, 16867266, 6674249, 17302437, 1376083, 6912193, 6546191, 5907331, 8871522, 12635393, 15549366, 8954755, 849125, 11962086, 7507032, 12339556, 18573850, 5247389, 2421214, 11031870, 11480636, 6016599, 3766913, 2801088, 7598964, 18405731, 10045011, 11893089, 7996581, 9385467, 13520284, 4161506, 243646, 12182419, 7500700, 2689988, 7081194, 1277521, 9936991, 1794016, 11389663, 783060, 4034777, 3360124, 18457117, 7912407, 14596202, 15596936, 4448624, 2463597, 16882636, 11187172, 2974964, 15889042, 16439360, 9095690, 7344564, 9939649, 1225733, 19455944, 5192701, 7179291, 16598274, 9418099, 18565747, 8272561, 16506535, 19871652, 17316624, 12379677, 638341, 4006571, 3700556, 15006452, 3935055, 9212340, 2279003, 1022247, 8961627, 11378423, 15338869, 198806, 19226038, 2352780, 2746746, 11391991, 16171268, 11781470, 13227951, 15529722, 12618324, 17052368, 9732217, 5169868, 7440943, 11221709, 15501436, 15406990, 3554235, 7015171, 3991691, 12700813, 15748895, 14753592, 15101707, 12918598, 11579138, 13531513, 9109772, 14431441, 15408363, 2744859, 6133263, 14763220, 9488802, 14046678, 12472175, 8703964, 13858057, 5432317, 3336675, 6256349, 14534510, 5652282, 14301933, 8660855, 1107998, 15495196, 10863410, 13323765, 11783549, 14733581, 5707757, 16448699, 3713237, 9585446, 9147646, 15628930, 18628120, 15651983, 1263524, 2237618, 7942555, 13638150, 3594495, 4062400, 5484469, 16460213, 13318935, 7186633, 12480410, 17866859, 15686118, 12641917, 9634837, 8264422, 6763181, 11450675, 10747746, 19457663, 18711312, 17694704, 5515609, 4974154, 5277220, 12498028, 7944009, 1471139, 14793541, 4744113, 10142088, 15679253, 17673731, 2745186, 18939120, 17402315, 17661109, 15708587, 11012551, 3436750, 583780, 9365250, 18811838, 13502482, 12990617, 17359380, 5950482, 18627394, 16751135, 6051099, 3476667, 17936334, 14183443, 19787462, 9920471, 260720, 4347029, 5973230, 15342429, 15157691, 14038164, 2391052, 4593378, 11250111, 17313127, 3425003, 18276457, 14431838, 4267993, 12866903, 638932, 17808012, 9879844, 18261645, 17047166, 8064927, 14227675, 1240791, 2765441, 9302030, 19255900, 11876403, 4588085, 15738535, 6294331, 11535445, 1194627, 3256166, 17825175, 2370042, 11886589, 3361195, 5280191, 3165402, 8037163, 7466613, 18709871, 1144278, 12864198, 16142344, 19973018, 13997093, 12870627, 5854090, 18883189, 15889377, 18399759, 7333642, 13806444, 9632746, 14350106, 13548511, 10925677, 6871389, 11721076, 3271759, 18163216, 7439827, 19902642, 10636464, 6127998, 7641360, 1393048, 2403700, 14080709, 13034242, 9914020, 8208209, 1594368, 17939190, 5905248, 9015114, 5824882, 12798385, 529241, 17035420, 2418221, 12891183, 7995127, 2185882, 2892861, 16801152, 11393339, 11349503, 4952017, 10267274, 2631003, 2848060, 19110579, 5373610, 8917428, 2082705, 16777363, 17758754, 15198093, 5910214, 5248947, 2613730, 10568766, 9124350, 2621484, 17097351, 10010462, 3746334, 7889551, 4283612, 16662002, 16148798, 3496829, 17690161, 4072567, 7988458, 9967201, 18195083, 15820187, 16786097, 15375472, 9401016, 8835998, 15329947, 10924539, 685651, 2040549, 15407231, 12658041, 18633841, 9696028, 5404853, 589694, 7587115, 7357151, 18575768, 9053190, 2446033, 10010502, 18007757, 14533668, 9602846, 10847817, 6238075, 1150753, 8457600, 16627749, 6579155, 4251158, 18047736, 12080290, 18715165, 389737, 6986485, 9879042, 18799343, 4863285, 14297720, 1554459, 11112986, 16714158, 17935735, 10140501, 11409716, 12747332, 390134, 11643259, 8350150, 5193650, 13035491, 1029628, 15192338, 13546307, 17707071, 12543675, 8795037, 231099, 877173, 13779168, 2310545, 1378117, 622888, 11481491, 8965394, 18370267, 9386778, 6267427, 53379, 4316439, 12626728, 13353436, 11512507, 16461144]
radixSort(arr)
for i in range(len(arr)):
print(arr[i]),
# This code is contributed by Mohit Kumra