• Input: a list of values
  • Operation: sort the list
  • Output: a sorted list of values

In [7]:
from numpy import random as rd

def sort_list(test_list):
    if not isinstance(test_list, list): # Not a list error
        raise NameError('Error: arg shouls be a list.')
    if len(test_list) < 1: # empty list
        return test_list
    new_list = []
    new_list.append(test_list[0])
    for i in test_list[1:]:
        if i > new_list[-1]: # if biggest number, append it -- better to optimize it!
            new_list.append(i)
            continue

        for j in range(0, len(new_list)):
            if i <= new_list[j]: # if smaller or equal than element at index j, insert before j
                new_list.insert(j, i)
                break
    return new_list
    

sample_lists = []
ranges = [10, 100, 1000]

for r in ranges:
    sample_lists.append((rd.rand(1, r)*100)[0].tolist())
    
for sample in sample_lists:
    print("\nRunning test with a list of", len(sample), "items.")
    print(sort_list(sample))


Running test with a list of 10 items.
[5.865056134328428, 10.434743250353373, 17.6431078764289, 27.0184673258997, 41.85653620097606, 50.175842297467874, 70.53334846730223, 87.18522086254956, 89.22968820918715, 97.06958060978798]

Running test with a list of 100 items.
[1.3028099409638227, 1.5793960967068976, 1.7673327717634524, 3.3987270773045752, 4.061886588102981, 4.282424683735108, 4.732888784187505, 4.937619804692817, 6.994602134078098, 7.378511181729852, 7.59605356355152, 7.686426992271944, 8.172302271802279, 8.930277201957749, 10.743231678415555, 11.15499397178814, 11.518462788191485, 11.526695198346438, 12.590637379376524, 14.78273723767205, 16.211330247825185, 18.577008689764295, 18.625140473116474, 19.27473490521894, 19.537131471618373, 19.89647051261234, 20.007742581544207, 20.00823576995674, 20.927848432873354, 23.84681648732624, 24.63244580215035, 25.024458961319883, 25.810917284880077, 26.05544378223127, 27.014445693500853, 27.49455333489237, 27.824758821013074, 28.541075326256614, 29.999181009132325, 30.082352956969537, 30.333781949639295, 33.3461084687944, 34.35709020989197, 34.84282722837475, 36.001371862050846, 36.97495991018221, 38.565400336751686, 38.64881435631947, 39.57257879548508, 40.070529862989225, 41.194210772991326, 42.819831531063755, 45.13175281263214, 45.87324256150974, 48.7746252781752, 49.09235946400946, 49.128242040427224, 49.14114307434127, 54.00210782721378, 54.34784510363871, 54.514917441350455, 56.53138104189942, 57.04065526490949, 57.25068946727511, 57.642890730704366, 60.97902629481155, 62.404673421515334, 63.108872230630055, 64.77517462821598, 65.37417210258734, 67.36159436128537, 69.26697587188903, 71.08022940081206, 71.08094583571607, 71.34834758518929, 71.42818193694086, 73.3665545470205, 73.62456942505145, 75.27772174338804, 80.01123568006335, 80.52103584712795, 83.09694237344047, 83.32906567341085, 84.1663246424201, 85.20118419425545, 87.34864306287253, 88.42087119229711, 90.07302797140052, 90.2581407903057, 90.5078951773745, 90.52523375447963, 91.27824421213005, 91.48996932690297, 93.0841040572537, 95.24465298930834, 97.80528507975018, 98.0435271758958, 98.34716636663087, 99.37705553370402, 99.49052076071297]

Running test with a list of 1000 items.
[0.1910952360880347, 0.26822241316259987, 0.32017921396881865, 0.4287540524995359, 0.48934445406245697, 0.6412620645041112, 0.6883109269866461, 0.6906344525979047, 0.7187798316828253, 0.7303465412300314, 0.7510483644996624, 0.8002474420038208, 0.8101466069754037, 0.8671250010050202, 0.8872336339044495, 1.0901631776934595, 1.2002304319463475, 1.3043745806177953, 1.3271696422300416, 1.5324416866838164, 1.645376267136478, 1.646945838696523, 1.6748589460356622, 1.7949150285698101, 1.9206716552382708, 1.9746025685127955, 2.097163118052614, 2.1985191949063676, 2.2612548872458227, 2.462612623320537, 2.6026368388268106, 2.6182003151686284, 2.6343112508473876, 2.6821272928386097, 2.7306616526075023, 2.7788646209263246, 2.8261029362585344, 2.9273518415530386, 3.0024530811482264, 3.0157287768575625, 3.087609897725019, 3.222352731013056, 3.428294981697544, 3.5001283489873414, 3.5907080531675906, 3.767511186643191, 3.876005963150897, 3.8997296023859374, 4.198137252571799, 4.199484382197383, 4.214604457163906, 4.3192282455066895, 4.627233044516621, 4.632000671936276, 4.711068139488672, 4.741504137745767, 5.008867593437727, 5.009733965842223, 5.084017885214498, 5.102003106138076, 5.134925463164331, 5.182347007624088, 5.188359516796481, 5.244588308232013, 5.28339427125003, 5.495493690292019, 5.530919754973274, 5.588283242684533, 5.6896996477854955, 5.697835383383431, 5.719346592196017, 5.767743480634902, 5.935927436442379, 6.0599341201386885, 6.095681823941723, 6.1111681208392055, 6.123704304240373, 6.180192488057578, 6.406865007683605, 6.437045388516993, 6.756775174515239, 6.843235600439856, 7.082029813573443, 7.173276352765368, 7.3917064795795735, 7.393858655966657, 7.416324949135822, 7.461513423857302, 7.6246482265514555, 7.7687342990566455, 7.8112634240316225, 7.86059271330698, 7.864745266315321, 7.973181692978681, 8.098318175110265, 8.117390534895186, 8.11890091920363, 8.17000756537981, 8.311468285386848, 8.358462174616365, 8.402984418109305, 8.451675228909906, 8.687427875902587, 8.74447879745266, 8.788105696473336, 8.858074804929238, 8.88615203425579, 8.940009874854605, 8.954779573682181, 9.0908765836201, 9.170663007605784, 9.267657548705788, 9.334723645280906, 9.3391619652461, 9.486812644198594, 9.496901322362305, 9.558891993788599, 9.646581409890286, 9.714544694019288, 10.208944718896529, 10.208972726966048, 10.20929641152163, 10.229007535258628, 10.310694187906734, 10.348858283095497, 10.446856982271358, 10.763016792265356, 10.880837326905556, 10.99284600439846, 11.148668821779161, 11.149492689196094, 11.245134168436287, 11.434828321639333, 11.504835435871453, 11.563932271306953, 11.837421824295868, 11.877151043785227, 12.046989923730644, 12.135207233433743, 12.140939779062032, 12.70355351398772, 12.88717092951287, 12.987590067055443, 13.031787025360053, 13.040302254171475, 13.102900928815009, 13.469313695307738, 13.917474021821885, 13.996408133530714, 14.20097825169785, 14.21892011817878, 14.3994068127682, 14.464752352581577, 14.483607419291921, 14.822450722260205, 15.022768338907166, 15.148460614517688, 15.18034652582967, 15.276474429918341, 15.298600265520346, 15.394730105613375, 15.492969769031395, 15.543009467924618, 15.620399984032385, 15.634146244998027, 15.849905304005896, 15.978041723327197, 16.340049306956274, 16.35740262182518, 16.447537357511866, 16.656706288664147, 16.677875638092654, 17.025447258030702, 17.26299483461986, 17.38611696422846, 17.617650096049687, 17.642891292024853, 17.665496852979643, 17.669722294625277, 17.7269995357201, 17.76346507461567, 17.865371395549246, 18.07087123368538, 18.095966387476693, 18.13371933892074, 18.138560878236355, 18.214916639672275, 18.222745880970592, 18.237373021595737, 18.259604019462195, 18.283150057788554, 18.289109325455932, 18.34737909199795, 18.393974675027557, 18.45756489945075, 18.458195053462678, 18.58574502426653, 18.652290756418644, 18.853997466066975, 18.874305565657256, 18.966239942993756, 19.367412483937052, 19.446355075857525, 19.60089125726755, 19.71649329869014, 19.7637257894712, 19.76816783132611, 19.995949868457007, 20.136332739249706, 20.34562642232841, 20.464800091095682, 20.86768758987134, 21.15061380131956, 21.17963526667419, 21.232591488985253, 21.422633671133784, 21.46236020296447, 21.487296431830604, 21.58044291294855, 21.627194924663794, 21.680073872805792, 21.8077755959579, 21.88598864628971, 21.938200495535597, 22.004707794018064, 22.07123804311959, 22.34175880444036, 22.381676648881978, 22.38194257672713, 22.757938256080855, 22.764844435501697, 22.817947447620345, 22.903735613324848, 22.941820622163977, 22.985874760990388, 23.289863216013718, 23.29133641222588, 23.314234758452745, 23.35932253150116, 23.39149537622215, 23.823565769326482, 23.870157828530946, 24.04570449679716, 24.23693671330136, 24.239342244708805, 24.49453832612497, 24.500631427044905, 24.502138191303878, 24.526426590280217, 24.592890577776306, 24.735064189105326, 24.80992601198747, 24.838193729390834, 24.978453257627244, 25.05703740741343, 25.060010998772864, 25.131105208155113, 25.158332677296148, 25.24073296154109, 25.527495067451188, 25.549789460098392, 25.734918959233035, 25.887789151902783, 25.99200280495696, 26.053951597714153, 26.056744630343587, 26.112148562502348, 26.117428657349407, 26.157181370356277, 26.218701685056722, 26.351528107497877, 26.42978894441813, 26.49756623330537, 26.498586435769944, 26.567437554358108, 26.570214307511065, 26.77398111059611, 26.789490315484564, 26.79434866269648, 26.915739489150848, 27.013839436324037, 27.083812623209724, 27.18865975999183, 27.260771239421356, 27.27100921543387, 27.564988214709707, 27.649994182675186, 27.74488693586614, 28.177711503654145, 28.250948469589897, 28.314549418099975, 28.41651686680806, 28.609251201087805, 28.61241037413186, 28.663710014743582, 28.727377766223704, 28.870562270731494, 28.97125692308751, 29.113233944932137, 29.286074260596962, 29.53458357442268, 29.79267677226033, 30.128851342919972, 30.16235349544536, 30.2056651373085, 30.260803900801292, 30.302372994268502, 30.395175624734183, 30.404208711250746, 30.50983474245935, 30.628048734012214, 30.81087326102582, 30.890262922033575, 31.110875900121794, 31.384724620777217, 31.509041569341466, 31.620626173124535, 31.632143703075922, 31.687231059171495, 31.71411944955551, 31.715506711648377, 31.815191591823687, 31.989851402764323, 32.1042426949772, 32.27954065768108, 32.36572012309203, 32.422687864346486, 32.43037685221356, 32.5008687451758, 32.65246221341831, 32.65400596788769, 32.67238086284513, 32.77670939525776, 32.94119100086398, 33.13912279080869, 33.19423893756507, 33.203723882620714, 33.241512720440625, 33.314330785850984, 33.370549679702364, 33.38320124573707, 33.50107283639575, 33.5356503158725, 33.56103090284084, 33.608510559189455, 33.743181588091666, 33.8282246907858, 33.87424499194093, 33.93843310039893, 33.94015176119978, 34.05303302803973, 34.07632698115094, 34.20165245062338, 34.47182613504363, 34.48328463155653, 34.48549914134757, 34.49374582374467, 34.49532298460336, 34.52224365432958, 34.53331511291091, 34.534808084665535, 34.60241361162007, 34.61098037664645, 34.823780739338915, 35.17477019296306, 35.25629879219381, 35.25759051132972, 35.34780641606458, 35.40909855259326, 35.44248658083361, 35.48138440951062, 35.49261338560371, 35.61590109898485, 35.831735517410245, 36.12181369848617, 36.204145223348036, 36.384770542277025, 36.680847315069485, 36.70839024349372, 36.72243413809528, 36.73557536872798, 36.87309332002059, 37.11180060659277, 37.18066633950503, 37.36575463161764, 37.46212286739643, 37.51280832569842, 37.58508466997505, 37.59257494531716, 37.69514851690956, 37.79338094836701, 37.91762401799114, 38.144106986343665, 38.22344270580027, 38.73065451227038, 38.75019828882734, 38.75496989897803, 38.87572172272398, 39.10375883645707, 39.12309430392621, 39.32939462978759, 39.47672554954435, 39.493955554386275, 39.49938773036234, 39.733900525052675, 39.97804981509224, 40.32794408318807, 40.398566826078444, 40.58006485971064, 40.58329488266315, 40.67145886683037, 40.75971687881951, 40.81354645961748, 40.83125144232691, 40.833303338870394, 40.89532197445372, 40.9279826544436, 40.94115842844058, 40.98637702429437, 41.103209048913115, 41.14157531057053, 41.15023360640885, 41.16657613200291, 41.23736519562093, 41.28144579022983, 41.33702397279766, 41.379007908497975, 41.49999783476175, 41.54743219227272, 41.65128622890406, 41.72811075932673, 41.88036547047991, 41.885173680772425, 41.89203618216815, 41.98892721427704, 42.009164978777434, 42.28481741920116, 42.28661198420725, 42.31241892034699, 42.39203488427164, 42.40208639611204, 42.480909784636964, 42.48244914483635, 42.5272592097507, 42.55086173477797, 42.586370719708114, 42.59191275524253, 43.09759967257698, 43.137946373949745, 43.15709636562539, 43.242193231074566, 43.78195002467454, 43.804350367505705, 43.80558322622497, 43.896752847869344, 44.03243179137601, 44.13000877727223, 44.13563821626918, 44.14402234335041, 44.29354322655957, 44.418287541727054, 44.443471132712354, 44.478299609473005, 44.502409411993305, 44.788842956180076, 44.844510631557014, 44.88425979821107, 44.910107282381354, 45.0211751096817, 45.24017336129648, 45.32968696835143, 45.36157680491093, 45.528903345109825, 45.63686921523653, 45.994684572342095, 46.012013733267075, 46.21056318860658, 46.280188770772014, 46.4633472277144, 46.50013778787703, 46.78690366540438, 46.80446934334254, 46.86741999597448, 46.898305165914444, 46.99461018423909, 47.03813645987977, 47.09870452484982, 47.15721282575217, 47.16345025664377, 47.42105665675926, 47.43132714841201, 47.934001497936784, 48.12346543344871, 48.17177649757048, 48.18922465296151, 48.42070981984317, 48.599460895341686, 48.6138659600699, 48.64847787393437, 48.675385017536996, 48.8513922281696, 48.85347071109014, 48.91153962318492, 48.92855706352669, 48.93334898933618, 49.03291896117506, 49.12989027786484, 49.148974322304284, 49.272537572066845, 49.343706361911146, 49.37581286186903, 49.46693772116644, 49.596758494814395, 49.7495388166041, 49.8065861158623, 49.84914091297554, 49.863858160663575, 49.88819405723166, 49.896861062876106, 49.97099257437895, 50.06756371639197, 50.20706072552168, 50.234202928883306, 50.283396909666536, 50.362478451622785, 50.448066328252786, 50.46620118926409, 50.58608193710275, 50.72034469039877, 51.01268488695022, 51.01613885252233, 51.09800936432467, 51.13061124418717, 51.133167015095935, 51.13637941819792, 51.15407870389465, 51.305971259300264, 51.32706823142416, 51.53999248134902, 51.70506108192411, 51.8392110558201, 51.90635783718564, 51.95497766547431, 52.25494947989983, 52.33854196519593, 52.41202962221798, 52.4202109052754, 52.508407745393704, 53.063206949118225, 53.26165669762204, 53.44579215092609, 53.498558395019145, 53.5492429905719, 53.61674916737195, 53.743988819269816, 53.85021121685683, 53.90232693141027, 53.91390281351863, 54.32334243859024, 54.33368060605241, 54.33370470501626, 54.41950579180772, 54.53143349956802, 54.560238446131116, 54.57186185754128, 54.59877022036963, 54.69253190737504, 54.859624885295275, 54.90054062700808, 54.97115277431218, 55.047424695913584, 55.16211022220981, 55.25311639467342, 55.44680657353804, 55.544399075601646, 55.55933816292281, 55.60316649520497, 56.1352424568837, 56.179145728713124, 56.51552203161363, 56.58468420277442, 56.61419883965865, 56.63571596556505, 57.03589062068577, 57.10668760664214, 57.13255093048273, 57.30913868338169, 57.34044446729312, 57.37152432851401, 57.531620155153384, 57.54144078710577, 57.62007880258432, 57.62580489113379, 57.728399267577835, 57.92013469865107, 58.024819270832786, 58.089607956296184, 58.09617993534503, 58.139183290154385, 58.18975359087565, 58.2410162218706, 58.34782212775498, 58.70167811486955, 58.713574386632075, 59.12745197699737, 59.239656056105375, 59.27400202792843, 59.28127785624593, 59.51555304413847, 59.54921235691965, 59.569928844151974, 59.588857037284434, 59.68466823844456, 59.952563308503684, 60.27706891229955, 60.323602187780054, 60.49324375069074, 60.52066267400868, 60.541049312207754, 60.66296908561799, 60.77056996990683, 60.97994216006665, 60.985687266634535, 60.98803138118755, 61.022588947503586, 61.184937973811316, 61.32163000630578, 61.48517873441691, 61.528312534505226, 61.57385820123756, 61.732057523460924, 61.83197800779776, 61.84307247987779, 61.85297206291088, 62.03545196445154, 62.08386825361995, 62.17864232337731, 62.38942292237171, 62.40040002572529, 62.5102019319179, 62.52400450247409, 62.56134297710687, 62.651226910737144, 62.685079942744245, 62.73714482594528, 62.86067127037164, 62.90012184024597, 63.00237198255314, 63.02697184351486, 63.070781015196495, 63.106291277532236, 63.16983206626146, 63.21436201794123, 63.21991202133946, 63.3996404681049, 63.46016678375659, 63.531964284265285, 63.63486997605309, 63.734446634681696, 63.767225092113186, 63.823196088783085, 63.84289088467532, 63.94910248294771, 64.20185157942939, 64.20642033514795, 64.20983667996335, 64.34500575591807, 64.36779561355938, 64.41040779013923, 64.44420366905466, 64.48708939080645, 64.5413122416777, 64.57206470321812, 64.65811743793785, 64.6783980202351, 64.73317501783907, 64.81463478054724, 64.82042662626264, 64.84989153986768, 64.8714847310152, 65.168908763449, 65.18742286607552, 65.19858067535928, 65.20332685946029, 65.22785401864788, 65.24017964400953, 65.45976035063195, 65.52388736822756, 65.59215399411012, 65.62104811527115, 65.80366711967399, 66.00821365541465, 66.12604865870094, 66.13915487038872, 66.34026945473947, 66.36458039472538, 66.49188202386041, 66.51662755072346, 66.54724821013588, 66.5523949441054, 66.74809031074925, 66.84721048417502, 66.94385639468219, 66.9966705505651, 67.14761980087111, 67.4213327561908, 67.74153757994443, 67.76567720876048, 68.13710431727274, 68.14601145174744, 68.21573500064865, 68.27990993186259, 68.2962653951281, 68.45959790070938, 68.66167897861214, 68.71968906373505, 68.76330746126544, 69.00803182666144, 69.05448409140165, 69.12435920134102, 69.13505989788601, 69.21900161304973, 69.58170896833872, 69.72166390633767, 69.79765837204863, 70.04350271715461, 70.05453623044122, 70.10603967499257, 70.13640140293398, 70.288524796711, 70.54015296984014, 70.5904617362304, 70.85961882658752, 70.88761197441077, 71.03575863490816, 71.1518357587566, 71.27514568904965, 71.3374227930175, 71.35764795124595, 71.408192561595, 71.54970948792696, 71.73683397693608, 71.76279651878504, 71.84172265181232, 72.22405491356663, 72.23303019711884, 72.31310845770234, 72.59220888240053, 72.60074169341327, 72.62604028085379, 72.74573937960982, 72.78809902748425, 72.91815657647665, 72.93294706743714, 73.1462544132604, 73.45617764126727, 73.61581497332882, 73.7272687115714, 73.83012397890522, 73.96022246991261, 73.97956850820196, 73.98269762754627, 74.00561823652382, 74.08809939364242, 74.28625973992169, 74.33540848903093, 74.53276599806298, 74.92059384339017, 74.92917095471697, 75.07919591458358, 75.39030335507675, 75.41478766302266, 75.46203636350216, 75.67425258691921, 75.71337787871568, 75.87917368316157, 76.18547504417205, 76.20269941678862, 76.31678031565731, 76.37263726076081, 76.38669851737903, 76.63345286860542, 76.7047017403122, 76.71392831196482, 76.75897573159932, 76.82689961088252, 76.84983113242363, 76.86686252308525, 76.90247275687419, 76.97991702293857, 77.20913742032654, 77.22527805870405, 77.3389663611432, 77.36849715969876, 77.45302716111502, 77.46349744870469, 77.71011262829524, 77.74519442629109, 77.86737629677982, 77.91026116378485, 78.09825853148624, 78.23132546596877, 78.3126871081881, 78.42350589378732, 78.62823845153216, 78.69090649830746, 78.78513522952395, 78.91868969175269, 78.94703921579739, 79.09820655452498, 79.16239088586109, 79.17117081336161, 79.25828607766992, 79.43520776834981, 79.49077196673477, 79.4923919187434, 79.52032919200057, 79.73260832670069, 79.777250278796, 79.881309245009, 80.09231235385646, 80.271869863547, 80.38340539745369, 80.681191314563, 80.72149119480734, 80.74171491036124, 80.84299282007476, 81.06546664227602, 81.18692999118923, 81.19241809415338, 81.31068745569972, 81.34688658162472, 81.71265759677905, 81.9058732526488, 81.95787279004205, 82.02950978518537, 82.08896816845035, 82.10406482970778, 82.50417052548156, 82.59614450030953, 82.69165519786233, 82.89148252919314, 82.94364572534244, 83.01408145337173, 83.06861387365564, 83.1607630786176, 83.30409783527067, 83.47962040838487, 83.55410358687985, 83.6268471096534, 83.62689837236324, 83.71642599176197, 83.86104778730038, 83.97673346191748, 84.13660296507999, 84.18237419027712, 84.18792024489518, 84.31322318454649, 84.35783623447894, 84.48635870407401, 84.56223408002724, 84.65097001414154, 84.75663799993721, 84.76102916883845, 84.78507992953863, 85.17986431426304, 85.7060213320756, 85.8020179236283, 85.8436025721799, 85.88813746740254, 85.88946608988275, 85.95913088564124, 86.01788674997223, 86.22927583245925, 86.25508393574954, 86.31706069266252, 86.59994907815805, 86.61630326454886, 86.78924481997413, 87.06320047643442, 87.42444259645093, 87.45004154131489, 87.62749141106798, 87.64413043482018, 87.71812031046065, 87.72965482513827, 87.80612811163819, 87.88469222005043, 88.05474432271484, 88.13188184356893, 88.14672199943195, 88.20366270038087, 88.21674831807881, 88.34864020123243, 88.63453714446011, 88.66513984195022, 88.90683358627953, 89.0098648452757, 89.15082950756407, 89.48797125198925, 89.64786246323243, 89.73654757072548, 89.83021351779784, 89.90867698527825, 90.02433766262556, 90.06922568961778, 90.29638258834312, 90.32452310093329, 90.42305075905507, 90.49368381260778, 90.53458625780331, 90.66692289581502, 90.80829486911746, 90.9340919941036, 91.02663130280764, 91.09690180315752, 91.23217908288377, 91.23695711494973, 91.32030761557462, 91.42238384909577, 91.445596881936, 91.58528474005382, 91.72935055980922, 91.79893950569421, 92.08547198091117, 92.48590776777709, 92.70777558118652, 92.86894586318785, 92.98461477378775, 93.09077696599137, 93.10420112550938, 93.18555879496235, 93.2321863891335, 93.28955523124091, 93.32967087792791, 93.36021842550612, 93.51020225014467, 93.65413891122041, 93.87958978408322, 94.0672675644975, 94.1926260129088, 94.23527177906091, 94.38054452037431, 94.5130168491212, 94.54832544948022, 94.64400846759372, 94.65514854120909, 94.68732051495287, 94.75833221261202, 94.82430254441259, 94.9340011280907, 95.22574990180249, 95.26241946371535, 95.38944148605, 95.41153703303969, 95.45731438486486, 95.46514126144518, 95.46552445039451, 95.49629409844874, 95.50851855961464, 95.57072317550671, 95.580669001449, 95.628982452518, 95.68952144136452, 95.69635401752781, 95.71322776697703, 95.84099930389442, 95.92712816002755, 95.98065905572479, 96.08719982937635, 96.14001832139294, 96.24377290280111, 96.37665858142745, 96.44329254632864, 96.68010655137664, 96.76351026810534, 97.00203282274404, 97.0601554545917, 97.19511047589315, 97.35975608698962, 97.43852467934848, 97.65246427218493, 97.72496625181442, 98.05170777339002, 98.2012238087199, 98.2745942375447, 98.32546393883995, 98.44500425677279, 98.46054648275013, 98.46173009364233, 98.58911377297774, 98.61980403208776, 98.7015411949898, 98.73740590003327, 98.74045855726527, 98.83771042908405, 99.24680820101905, 99.45556140588819, 99.50248969487802, 99.96343550290389]
  • Input: a sorted list and a search term
  • Operation: find the element in the list
  • Output: the location of the item in the list or indicate if it's not there

In [10]:
def find_value_index(sorted_list, needle):
    found = False
    left_boundary = 0
    right_boundary = len(sorted_list)-1
    count = 0

    while found == False:
        mid = int(left_boundary + (right_boundary - left_boundary) / 2) # quadtree! (sort of)
        if needle > sorted_list[mid]:
            left_boundary = mid
        elif needle == sorted_list[mid]:
            print("Found after", count, "iterations. Index =", mid)
            return mid
            found = True
        else:
            right_boundary = mid
            
        if right_boundary - left_boundary < 2:
            if needle == sorted_list[right_boundary]: # because we never ceil to get the mid
                print("Found after", count, "iterations. Index = ", mid)
                return mid
            else:
                found = False
                if mid - 1 > 0:
                    print("Not found. Closest values:", sorted_list[mid-1], sorted_list[mid])
                else:
                    print("Not found. Closest value:", sorted_list[mid])
                return False
            
        count += 1

        
sample_sorted_lists = []
sample_needles = []

for sample in sample_lists:
    sample_sorted_lists.append(sort_list(sample))

for sample in sample_sorted_lists:
    needle = rd.choice(sample)
    print("\nRunning test with a sorted list of", len(sample), "items. Needle: ", needle)
    
    print(find_value_index(sample, needle))


Running test with a sorted list of 10 items. Needle:  97.0695806098
Found after 3 iterations. Index =  8
8

Running test with a sorted list of 100 items. Needle:  11.5184627882
Found after 5 iterations. Index = 16
16

Running test with a sorted list of 1000 items. Needle:  3.01572877686
Found after 9 iterations. Index = 39
39