Sökning och sortering

Sortering

Att sortera listor och andra uppsättningar data är viktigt inom många användningsområden och det finns ett stort antal algoritmer för detta.

Läs om sorteringsalgoritmer här.

Python har  en inbyggd metod för att sortera listor som är mycket effektiv:
lista.sort()

Sökning i listor

Om listan är oordnad är det enklast att söka från början till slut tills man hittar det man söker. Man behöver då i snitt söka genom hälften av listan innan man finner det sökta värdet.

Är listan sorterad kan sökningen snabbas upp betydligt genom en smart metod.

Binär sökning
I en sorterad lista kan man veta om man är före eller efter det sökta värdet. Man gör därför så att man gissar på det mittersta värdet inom det område man inte uteslutit. Se nedanstående bild som visar sökning efter talet 76:

Efter första gissningen vet man att talet är i den övre halvan.
Efter den andra vet man att talet är i den tredje fjärdedelen.
osv tills man finner det.

Uppgift 2.6
Skriv ett program som:

•  Låter användaren mata in ett valfritt antal tal (Avsluta inmatningen med tex. att användaren skriver N). Talen läggs i en lista.
•  Sorterar listan av tal.
•  Med hjälp av binär sökning letar fram ett tal som användaren matat in. (Förutsatt att det finns i listan. Annars ett meddelande om att det inte finns.)