Sortering og søking i Python

Hvis du fikk et papir med en liste med 1000 navn, og du ble bedt om å finne noe navn, men denne listen var ikke i noen rekkefølge (f.eks. Alfabetisk rekkefølge), ville det være veldig frustrerende, ikke sant? Å sette den listen i rekkefølge, selv om det tar lang tid, gjør det enklere å finne navnet. Å ha ting i orden er dermed et naturlig ønske vi mennesker har, og å søke på denne listen vil tydeligvis ta mindre innsats enn å søke en uordnet liste.

La oss flytte til datamaskinverdenen, hvor lister man måtte kreves for å søke, er veldig store, og hvor ytelsen kan bli påvirket, selv med raske datamaskiner. I dette tilfellet har en egnet sortering og søking algoritmen ville være en løsning på et slikt problem. Samtidig som sortering handler om å sette en liste over verdier i rekkefølge, søker er prosessen med å finne posisjonen til en verdi i en liste.

For å gjøre det klart hvor kritisk dette problemet kan være, la meg vise deg hva Donald Knuth, en amerikansk datavitenskapsmann, matematiker og professor emeritus ved Stanford University nevnt i Art of Computer Programming, vol.3, Sortering og søking, side 3:

Datamaskinprodusenter på 1960-tallet anslått at mer enn 25 prosent av driftstiden på datamaskinene ble brukt på sortering, da alle sine kunder ble tatt i betraktning. Faktisk var det mange installasjoner der sorteringen var ansvarlig for mer enn halvparten av beregningstiden. Fra disse statistikkene kan vi konkludere med at enten (i) det er mange viktige søknadsanordninger, eller (ii) mange sorterer når de ikke burde, eller (iii) ineffektive sorteringsalgoritmer har vært fellesbruk.

I denne opplæringen vil jeg spesifikt beskrive Valg Sorter algoritme (sortering) og Lineær søk algoritme (søker).

Valg Sorter Algoritme

De Valg Sorter algoritmen er basert på suksessivt utvalg av minima eller maxima verdier. Anta at vi har en liste som vi vil sortere i stigende rekkefølge (fra mindre til større verdier). Det minste elementet vil være i begynnelsen av listen, og det største elementet vil være på slutten av listen. 

La oss si at den opprinnelige listen ser ut som følger:

| 7 | 5 | 3,5 | 4 | 3.1 |

Det første vi gjør er å finne minimum verdi i listen, som er i vårt tilfelle 3.1. 

Etter å ha funnet minimumsverdien, bytte den minste verdien med det første elementet i listen. Det er bytte 3.1 med 7. Listen vil nå se ut som følger:

| 3.1 | 5 | 3,5 | 4 | 7 |

Nå som vi er sikre på at det første elementet befinner seg i riktig posisjon i listen, gjentar vi trinnene ovenfor (finne minimumsverdien) som starter fra sekund element i listen. Vi finner at minimumsverdien i listen (fra det andre elementet) er 3,5. Vi bytter nå nå 3,5 med 5. Listen blir nå som følger:

| 3.1 | 3,5 | 5 | 4 | 7 |

På dette punktet er vi sikre på at det første elementet og det andre elementet er i deres riktige posisjoner.

Nå sjekker vi minimumsverdien i resten av listen, som starter fra det tredje elementet 5. Minste verdien i resten av listen er 4, og vi bytter det nå med 5. Listen blir således som følger:

| 3.1 | 3,5 | 4 | 5 | 7 |

Så vi er nå sikre på at den første tre elementene er i riktig posisjon, og prosessen fortsetter på den måten. 

La oss se hvordan utvalgsalgoritmen er implementert i Python (basert på Isai Damier):

def selectionSort (aList): for jeg i rekkevidde (len (aList)): minst = i for k i rekkevidde (i + 1, len (aList)): hvis 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

La oss teste algoritmen ved å legge til følgende setninger på slutten av det ovennevnte skriptet:

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 (my_list) skriv ut min_list

I dette tilfellet bør du få følgende utgang:

[4,6, 4,7, 5,76, 7,3, 7,6, 25,3, 32,4, 43,5, 52,3, 55,3, 86,7]

Linjær søkalgoritme

De Lineær Søk algoritmen er en enkel algoritme, hvor hvert element i listen (fra det første elementet) undersøkes til det nødvendige elementet er funnet, eller slutten av listen er nådd. 

Linear Search algoritmen implementeres i Python som følger (basert på Python School):

def linearSearch (element, my_list): found = False posisjon = 0 mens posisjon < len(my_list) and not found: if my_list[position] == item: found = True position = position + 1 return found

La oss teste koden. Skriv inn følgende setning på slutten av Python-skriptet ovenfor:

bag = ['bok', 'blyant', 'pen', 'notatbok', 'skjermer', 'gummi'] item = input ('Hvilket element vil du se etter i posen?') itemFound = linearSearch (vare, bag) hvis itemFound: print 'Ja, varen er i posen' ellers: print 'Ups, ditt produkt synes ikke å være i posen'

Når du går inn i inngang, sørg for at det er mellom enkle eller doble anførselstegn (dvs.. 'blyant'). Hvis du skriver inn 'blyant', for eksempel, bør du få følgende utgang:

Ja, varen er i posen

Mens du skriver inn 'Hersker' Som input vil du få følgende utgang:

Ups, ditt produkt synes ikke å være i posen

Som vi kan se, viser Python seg selv igjen for å være et programmeringsspråk som gjør det enkelt å programmere algoritmiske konsepter som vi gjorde her, håndtere sortering og søker algoritmer.

Det er viktig å merke seg at det finnes andre typer sorterings- og søkealgoritmer. Hvis du vil dykke dypere inn i slike algoritmer ved hjelp av Python, kan du se på denne siden.