Rekursiv Merge Sorter i Python
Sortering er tradisjonelt en vanskelig oppgave i informatikk. Å velge en sorterings algoritme som er effektiv og rask kan være vanskelig. Ofte innebærer effektiv algoritme valg kunnskap om data blir sortert, og spesialiserte sorterer vanligvis fungerer mye bedre enn gener sortering algoritmer. Men visse former, slik som "flettesortering," kan fungere på en generell situasjoner ved å bryte ned sett og sortering mindre biter rekursivt.
Listen
En merge sort er en "splitt og hersk" algoritme, ved at den tar deler av listene og kontinuerlig bryter dem i halvdeler inntil nå enkeltelementer av listen, som deretter slått sammen i rekkefølge. For eksempel begynne med en numerisk liste som
5 6 2 4 1 9 8 3 7
Sortere en liste som dette med en flettesortering vil kreve halvere listelengden ganger til hver enkel nummeret eksisterer alene. Deretter kan sortere sammenligne tallene og sette dem sammen i riktig rekkefølge (lavest til høyest, i dette tilfellet).
Flett Method
Flettingen Metoden er enkel:
def flette (første, andre)
Ta to lister, vil metoden slå dem sammen ved å begynne ved begynnelsen av hver liste. Det føyer deretter neste minst mulig hver liste inn i en ny liste. Resultatet er en sortert liste. (Husk å skikkelig sette fanen hvit mellomrom etter "mens" og "hvis / else" utsagn.):
mens jeg <len (først) og j <len (andre):
hvis første [i] <= andre [j]:
new_list.append (første [i])
i = i + 1
ellers:
new_list.append (andre [j])
j = j + 1}
Endelig, etter en liste slutter, blir de gjenværende verdiene plassert i den nye listen:
new_list + = første [i:]
new_list + = andre [j:]
tilbake end_list
Flett Sorter betingelser
Selve flettesortering driver hovedsorteringsalgoritmen. Det er to funksjonelle hoveddeler: betinget aspekt som stopper rekursjon når listene er inndelt og selve rekursjon som halverer listene. Den stoppet opp tilstanden kommer først:
def mergeSort (liste):
hvis Len (liste) == 1:
retur-listen
Dette sikrer at når en sub liste når bare ett element, er dette elementet returneres i for at den skal bli slått sammen med de andre tallene.
Flett Sorter Rekursjon
Den andre halvdelen av den typen er rekursjon. Etter "hvis" statement / betinget, som følger:
ellers:
midten = len (liste) / 2
start = mergeSort (liste [midten:])
end = mergeSort (liste [: midten])
avkastning merge (start, slutt)
På grunn av rekursjon, etter at listene er delt inn i enkeltelementer, algoritmen tilbake sporer opp til den siste henrettet metoden. Så, etter den tid utsagnet "return merge (start, slutt)" utføres, returnerer algoritmen et fusjonert, sortert liste over to tidligere slått sammen, sortert lister over mindre størrelse.