Share
Als je een stuk papier hebt gekregen met een lijst van 1000 namen, en je werd gevraagd om een naam te vinden, maar deze lijst was niet in een willekeurige volgorde (bijvoorbeeld alfabetische volgorde), zou het erg frustrerend zijn, toch? Het op orde brengen van die lijst, hoewel het lang duurt, maakt het vinden van de naam veel gemakkelijker. Dus het in orde hebben van de dingen is een natuurlijk verlangen dat wij mensen hebben, en het doorzoeken van deze lijst zou duidelijk minder inspanning vergen dan zoeken naar een ongeordende lijst.
Laten we naar de computerwereld gaan, waar de lijsten die je moet doorzoeken erg groot zijn en waar de prestaties zelfs met snelle computers kunnen worden beïnvloed. In dit geval heeft u een geschikte sorteren en zoeken algoritme zou een oplossing voor een dergelijk probleem zijn. Terwijl sorteer- gaat over het op orde brengen van een lijst met waarden, zoeken is het proces van het vinden van de positie van een waarde binnen een lijst.
Om duidelijk te maken hoe kritisch dit probleem kan zijn, wil ik u laten zien wat Donald Knuth, een Amerikaanse computerwetenschapper, wiskundige en emeritus professor aan de Stanford University, genoemd in The Art of Computer Programming, vol.3, Sorteren en zoeken, pagina 3:
Computerfabrikanten van de jaren zestig schatten dat meer dan 25 procent van de tijd op hun computer besteed werd aan sorteren, wanneer al hun klanten in aanmerking werden genomen. In feite waren er veel installaties waarin de taak van sorteren verantwoordelijk was voor meer dan de helft van de rekentijd. Uit deze statistieken kunnen we concluderen dat (i) er veel belangrijke sorteertoepassingen zijn, of (ii) veel mensen sorteren wanneer ze dat niet zouden moeten doen, of (iii) inefficiënte sorteeralgoritmen in gemeenschappelijk gebruik zijn geweest.
In deze tutorial zal ik specifiek de Selectie Sorteren algoritme (sorteren) en de Lineair zoeken algoritme (zoeken).
De Selectie Sorteren algoritme is gebaseerd op opeenvolgende selectie van minima of maxima-waarden. Stel dat we een lijst hebben die we in oplopende volgorde willen sorteren (van kleinere naar grotere waarden). Het kleinste element staat aan het begin van de lijst en het grootste element staat aan het einde van de lijst.
Laten we zeggen dat de oorspronkelijke lijst er als volgt uitziet:
| 7 | 5 | 3.5 | 4 | 3.1 |
Het eerste wat we doen is het vinden van de minimum waarde in de lijst, wat in ons geval is 3.1.
Na het vinden van de minimumwaarde, ruil die minimumwaarde met het eerste element in de lijst. Dat wil zeggen, ruilen 3.1 met 7. De lijst ziet er nu als volgt uit:
| 3.1 | 5 | 3.5 | 4 | 7 |
Nu we zeker weten dat het eerste element in de juiste positie in de lijst staat, herhalen we de bovenstaande stap (het vinden van de minimumwaarde) beginnend bij de tweede element in de lijst. We kunnen vaststellen dat de minimumwaarde in de lijst (uitgaande van het tweede element) is 3.5. We wisselen dus nu 3.5 met 5. De lijst wordt nu als volgt:
| 3.1 | 3.5 | 5 | 4 | 7 |
Op dit punt zijn we er zeker van dat het eerste element en het tweede element in hun juiste posities zijn.
Nu controleren we de minimumwaarde in de rest van de lijst, die begint bij het derde element 5. De minimumwaarde in de rest van de lijst is 4, en we wisselen het nu om 5. De lijst wordt aldus als volgt:
| 3.1 | 3.5 | 4 | 5 | 7 |
Dus we zijn nu zeker dat de eerste drie elementen bevinden zich in de juiste posities en het proces gaat zo verder.
Laten we eens kijken hoe het Selection Sort-algoritme in Python is geïmplementeerd (gebaseerd op Isai Damier):
def selectionSort (aLijst): voor i in bereik (len (aLijst)): least = i voor k binnen bereik (i + 1, len (aLijst)): if aList [k] < aList[least]: least = k swap(aList, least, i) def swap(A, x, y): temp = A[x] A[x] = A[y] A[y] = temp
Laten we het algoritme testen door de volgende uitspraken aan het einde van het bovenstaande script toe te voegen:
my_list = [5.76,4.7,25.3,4.6,32.4,55.3,52.3,7.6,7.3,86.7,43.5] selectionSort (mijn_lijst) print mijn_lijst
In dit geval zou u de volgende uitvoer moeten krijgen:
[4,6, 4,7, 5,76, 7,3, 7,6, 25,3, 32,4, 43,5, 52,3, 55,3, 86,7]
De Lineair zoeken algoritme is een eenvoudig algoritme, waarbij elk item in de lijst (beginnend bij het eerste item) wordt onderzocht totdat het vereiste item is gevonden of het einde van de lijst is bereikt.
Het lineaire zoekalgoritme is als volgt in Python geïmplementeerd (gebaseerd op Python School):
def linearSearch (item, mijn_lijst): gevonden = False position = 0 while position < len(my_list) and not found: if my_list[position] == item: found = True position = position + 1 return found
Laten we de code testen. Voer de volgende verklaring aan het einde van het bovenstaande Python-script in:
Accentsconagua
tas = ['boek', 'potlood', 'pen', 'notitieboek', 'puntenslijper', 'rubber'] item = invoer ('Welk item wilt u controleren in de zak?') itemFound = linearSearch (item, tas) als itemgevonden: print 'Ja, het artikel zit in de tas' anders: print 'Oeps, je item lijkt niet in de tas te zitten'Wanneer u de invoer, zorg ervoor dat het tussen enkele of dubbele aanhalingstekens (d.w.z.. 'potlood'). Als je invoert 'potlood', bijvoorbeeld, zou u de volgende output moeten krijgen:
Ja, het artikel zit in de tas
Terwijl, als je binnenkomt 'heerser' als invoer krijg je de volgende uitvoer:
Oeps, je item lijkt niet in de tas te zitten
Zoals we kunnen zien bewijst Python zichzelf opnieuw als een programmeertaal die het gemakkelijk maakt om algoritmische concepten te programmeren zoals we hier deden, om te gaan met sorteer- en zoeken algoritmen.
Het is belangrijk op te merken dat er andere soorten sorteer- en zoekalgoritmen zijn. Als je met Python dieper in dergelijke algoritmen wilt verdiepen, kun je deze pagina raadplegen.
