Grundlæggende Programmering (GP) Efterår 2005 Forelæsning 8 Slides ligger på nettet. Du er velkommen til at printe dem nu. Vi begynder 9.15. www.itu.dk/courses/GP/E2005 Martin Lillholm
Søgning
Søgning handler om at finde et givent element i en samling af data
Vi skelner mellem søgning i:
En samling usorterede data
En samling af sorterede data
I vores eksempler vil en samling af data være en tabel
Andre muligheder ?
Lineær søgning – usorterede data
Data gennemsøges fra enden til anden
Tavleeksempel
Hvor meget arbejde kræver lineær søgning?
Arbejde: antal sammeligninger
Antag at vi har en tabel med n elementer
I gennemsnit benyttes n/2 sammenligninger
Vi siger at arbejdet for lineær søgning har lineær kompleksitet eller er proportional med n
Binær søgning – sorterede data
Algoritme for en sorteret (stigende) tabel med n tal
Begynd i midten
Gentag indtil vi finder det korrekte element eller vi kun har et forkert element tilbage
Hvis tallet vi søger er mindre end det nuværende element
Søg i den nederste halvdel med udgangspunkt i det miderste element
Hvis tallet vi søger er større end det nuværende element
Søg i den øverste halvdel med udgangspunkt i det miderste element
Tavlegennemgang
Kompleksitet log2(n) – hvorfor ?
Hvor 2-tals logaritmen siger hvor mange gange vi kan halvere et tal og stadig få et resultat der er større end eller lig 1. log2(n) = log(n)/log(2) hvor log(n) er den naturlige logaritme
Sammenligning af lineær og binær søgning
Lineær og binær søgning – implementation
Peter Sestofts note
Vi vender tilbage til L&L’s implementation, der er polymorf
Sortering
Hvad er sortering ?
Hvorfor overhovedet sortere?
Fordi vi ønsker sorterede data
Gentagne søgninger
Find de ti største/mindste elementer i en liste
Find identiske elementer i en liste
Find identiske elementer i to lister
Der findes mange sorteringsmetoder
Selection sort
Insertion sort
Quick sort
Heap sort
…
Forskellige tids- og pladskompleksitet – velegnet til forskellige opgaver
Selection sort
Givet en liste af tal med n elementer
Find det mindste element og fjern det fra listen. Det delvist sorterede resultat består nu af et element
Find det næstmindste element – altså det mindste af de tilbageværende elementer – og fjern det fra listen. Tilføj det til listen af sorterede elementer
...
Fortsæt indtil den oprindelige liste er tom
I praksis benyttes en og samme tabel til både den sorterede og den usorterede del
Tavlegennemgang
Selection sort
Hvor meget arbejde kræver selection sort?
Vi kan finde det mindste af m elementer ved brug af m-1 sammenligninger
Generelt gælder:
For en n lang liste:
I praksis dominerer ½n2 for store n og vi siger at arbejdet er asymptotisk proportionalt med n2.
I såvel teori som praksis er selection sort langsom!
Comments