An warware: quicksort

Quicksort yana ɗaya daga cikin ingantattun algorithms rarrabuwa, yana alfahari da matsakaicin matsakaicin lokaci na O(n log n). Dangane da tsarin raba-da-ci, yana baje kolin ayyuka masu ban sha'awa yayin rarrabuwar manyan bayanan bayanai. Masanin kimiyyar kwamfuta na Burtaniya Tony Hoare ne ya ƙirƙira a cikin 1959 kuma aka buga shi a 1961, quicksort ya zama babban ɓangaren kimiyyar kwamfuta da shirye-shirye..

Quicksort's shahararsa kuma saboda sauƙin aiwatarwa a cikin harsunan shirye-shirye daban-daban. A cikin wannan labarin, za mu bincika yadda za a iya aiwatar da sauri ta hanyar amfani da yaren shirye-shiryen Haskell, harshen shirye-shiryen da aka rubuta a kididdigar da aka sani da tsafta, taƙaitacciya, da ƙayatarwa.

Ta yaya Quicksort ke aiki?

Quicksort yana aiki ta zaɓar 'pivot' daga saitin bayanai da kuma rarraba sauran abubuwa zuwa rukuni biyu - waɗanda ba su kai pivot ba da waɗanda suka fi pivot girma. Wannan mataki, wanda aka sani da 'bangare', ana aiwatar da shi akai-akai har sai an jera jeri.

quicksort :: Ord a => [a] -> [a]
quicksort [] = []
quicksort (p:xs) = (quicksort lesser) ++ [p] ++ (quicksort greater)
    where
        lesser  = filter (<  p) xs
        greater = filter (>= p) xs

Lambar Haskell da ke sama tana farawa ta hanyar ayyana harka ta tushe don jerin fanko, wanda ke dawo da lissafin fanko. Don lissafin da ba fanko ba, yana zaɓar pivot (a cikin wannan yanayin, kashi na farko na jerin), sannan ta tace sauran jerin zuwa jerin abubuwa biyu - ɗaya tare da abubuwan ƙasa da pivot, ɗayan kuma tare da abubuwan da suka fi ko girma. daidai da pivot.

Fahimtar aiwatar da Haskell

A cikin aiwatar da Haskell ɗin mu, muna yin amfani da ƙarfin fahimtar lissafin harshe da ayyuka masu girma.

Layin lambar `(ƙananan sauri) ++ [p] ++ (mai sauri mafi girma)` a taƙaice yana ɗaukar ainihin ma'anar quicksort - yana sake tsarawa duka 'ƙananan' da 'mafi girma' jerin sunayen 'ƙananan' da 'mafi girma', sa'an nan kuma ya haɗa waɗannan abubuwan da aka jera tare da pivot. a tsakiya. Wannan ita ce dabarar raba da cin nasara a aikace.

Duk da sauƙin sa, wannan aiwatarwa na iya zama mara inganci don manyan jeri, yayin da yake tace kowane jerin sunayen sau biyu. Duk da haka, yana aiki azaman babban mafari don fahimtar yadda quicksort ke aiki a Haskell.

Haskell Programming and Quicksort

Kyawawan ladabi da sauƙi na quicksort a cikin Haskell suna ƙarfafa ƙarfin shirye-shiryen aiki. Takaitaccen lambar kuma yana nuna ƙarfin jerin ayyukan Haskell.

Buga a tsaye na Haskell yana hana yawancin yuwuwar kwari a lokacin tattara-lokaci, yayin da tsarkinta (babu sakamako mai lahani) da ƙarancin ƙima (ba a aiwatar da lissafin sai an buƙata) yana sauƙaƙe tunani game da haɓaka lambar.

Daga qarshe, quicksort ba kawai ingantaccen rarrabuwar algorithm bane amma shaida ne ga ƙarfin shirye-shiryen aiki da ƙarfin Haskell a matsayin harshe.