[Powered by Google Translate] [Cumaisc Sórtáil] [Rob Bowden - Ollscoil Harvard] Is é [seo CS50. - CS50.TV] Ligean ar labhairt faoi sort chumaiscthe. Go dtí seo tá tú ag feiceáil saghas mboilgeog, a shórtáil isteach, agus sórtáil roghnú. Cé Feicfidh mé cineál toinne mo lámh ar cad is ciall agam le níos fearr, merge sórtáil fheidhmíonn i gcoitinne níos fearr ná aon cheann de na 3 cineál. 

Ach sula ag caint faoi saghas merge, a ligean ar labhairt faoi chumasc 2 liosta sórtáilte. Beidh muid glaoch ar an bpróiseas a ghlacadh 2 liosta sórtáilte, mar seo, agus ag déanamh liosta amháin in eagar le amach acu - chumasc na liostaí. Conas is féidir linn seo a dhéanamh? Bhuel, ar cheann smaoineamh a bata díreach liosta amháin isteach ar an deireadh an liosta eile agus sórtáil ansin ar an liosta thoradh air sin. 

Cé go n-oibríonn seo, tá sé a lán oibre gan ghá. Is féidir linn é a dhéanamh níos tapúla ná díreach a shórtáil. Fógra go bhfuil ceann smaoineamh mícheart a ghlacadh ach cupáin alternating ó gach liosta. Cé gur féidir go bhfuil cuma mhaith go n-oibríonn ar dtús, a dhéanamh go bhfuil muid ag deireadh suas le 4, 8, 15, 23, 16 - Fógra go bhfuil 16 agus 23 as áit. Tá sé seo toisc 2 gnéithe ba chóir a feiceáil i ndiaidh a chéile ar an liosta cumaiscthe Tá an liosta céanna tosaigh. An dá 15 agus 16 atá ar an liosta ar chlé. Is é an trick leas a bhaint as an bhfíric go bhfuil an dá liostaí atá curtha in eagar cheana féin. Ciallaíonn sé seo má táimid ach breathnú ar na gnéithe chéad dá liostaí - anseo, 4 agus 8 - ní mór ceann amháin acu a bheith chomh maith an chéad ghné den liosta cumaiscthe. Bhuel, cén fáth é sin? Tá an dá de na liostaí seo atá curtha in eagar cheana féin, agus mar sin ní mór a bheith 4 nó 8 an ghné is lú nuair a chéile muid an 2 liosta. Sa chás seo, is é is lú 4, ionas gur féidir linn a thógáil amach 4 agus é a dhéanamh an chéad ghné den ár liosta cumaiscthe. Anois táimid ag leanúint ar aghaidh tríd an 3 atá fágtha gnéithe den chéad liosta agus 4 eilimintí an dara liosta. 

Arís eile, is gá dúinn ach chun breathnú ar an chéad eilimint de dá liostaí. Ní mór don lú den 2 an dara gné d'ár liosta cumaiscthe. An uair seo, idir 8 agus 15 is lú 8, agus mar sin againn isteach go mar an dara gné den ár liosta in eagar. Is féidir linn leanúint ar aghaidh i gcomparáid leis an chéad chuid de dhá liostaí agus a bhaint de na lú ar an 2. Comparáid 15 agus 23, 15 níos lú agus mar sin go s ár tríú gné. Anois i gcomparáid 16 agus 23, 16 níos lú. Mar sin, go bhfuil an ghné ceathrú. 

Fógra a tháinig 2 gnéithe ón liosta céanna i ndiaidh a chéile. Sin é an fáth nach féidir an liosta cumaiscthe díreach gnéithe malartach ó na liostaí 2. Comparáid 50 agus 23, 23 níos lú, mar sin roghnaigh muid go. Idir 50 agus 42, is é 42 níos lú. Idir 50 agus 108, is é 50 níos lú. Agus, ar deireadh, ní mór dúinn ach 108, mar sin caithfidh sé dul ar an deireadh ar ár liosta. Fógra gur féidir linn an deas, liosta in eagar. Gach uair i gcomparáid muid an chéad 2 gnéithe den 2 liosta bhí muid in ann chun a chinneadh an chéad bhall eile ón liosta cumaiscthe. Ciallaíonn sé seo go bhfuil má tá an liosta deiridh uimhreacha n, áit a bhfuil n anseo 8, ansin is gá dúinn ar an chuid is mó comparáidí n a fháil ar gach ceann de na huimhreacha ar an áit ceart. Tá a leithéid de algartam sin a reáchtáil i am líneach, ach ná bíodh imní ort faoi sin anseo. 

Ag baint úsáide as ár n-algartam le haghaidh a chumasc, is féidir linn a dhéanamh ar algartam saghas tapa chumaiscthe. Mar sin, a ligean ar a athshocrú ár liostaí. Tá 2 céimeanna móra sa phróiseas saghas chumaiscthe. Gcéad dul síos, scoilt leanúnach ar an liosta de na cupáin i leatha go dtí go bhfuil muid a bunch de liostaí le cupán ach 1 i dóibh. Ná bíodh imní ort má tá liosta corruimhir agus ní féidir leat a dhéanamh gearrtha breá glan eatarthu. Just a roghnú treallach a liosta a chur san áireamh an cupán breise isteach Mar sin, a ligean ar roinneadh na liostaí seo. Anois, tá muid 2 liosta. Anois, tá muid 4 liostaí. 

Agus anois ní mór dúinn 8 liostaí le cupán amháin i ngach liosta. Mar sin tá go bhfuil sé do chéim 1. Le haghaidh chéim 2, ní mór dúinn merge arís agus arís eile péirí liostaí baint úsáide as an algartam merge fhoghlaim muid roimh. A chumasc 108 agus 15, deireadh muid suas leis an liosta 15, 108. Cumasc 50 agus 4, deireadh muid suas le 4, 50. A chumasc 8 agus 42, ní mór dúinn deireadh suas le 8, 42. Agus a chumasc 23 agus 16, ní mór dúinn deireadh suas le 16, 23. Anois, tá gach ár liostaí de mhéid 2. Fógra go bhfuil gach ceann de na 4 liostaí curtha in eagar. 

Mar sin, is féidir linn tús a chumasc péirí liostaí arís. Cumasc 15 agus 108 agus 4 agus 50 - an chéad a chur ar an 4, ansin 15, ansin an 50, ansin an 108. A chumasc 8, 42 agus 16, 23, beimid ag tabhairt faoi ar dtús leis an 8, ansin an 16, ansin an 23, ansin an 42. Mar sin, anois ní mór dúinn ach 2 liosta de mhéid 4, tá gach ceann acu curtha in eagar. Mar sin, anois merge againn ar na 2 liosta. An Chéad muid a chur ar an 4. Ansin againn a chur ar an 8. Ansin againn a chur ar an 15 agus 16, ansin 23, ansin 42, ansin 50, ansin 108. Agus muid ag déanamh. Tá muid anois ar liosta in eagar. Mar sin, cé chomh tapa raibh sé seo, go díreach? I dtéarmaí teicniúla, tá merge sórtáil O (n log n), cé go bhfuil gach ceann de saghas mboilgeog, a shórtáil isteach, agus sórtáil roghnú O (n ²). Go deimhin, mar beidh tú ag foghlaim go luath, ní bheidh tú in ann teacht suas le saghas a dhéanann níos fearr ná O (n log n) i gcás go ginearálta. Arís, ná bíodh imní ort faoi seo nodaireacht O mór más rud é nach bhfuil tú ag feiceáil go fóill. 

Just a fhios go ciallaíonn sé seo más rud é go bhíomar ag iarraidh a shórtáil ar liosta mór i ndáiríre D'fhéadfadh saghas mboilgeog, a shórtáil isteach, agus a roghnú saghas a ghlacadh d'fhéadfadh a bheith bhfad níos faide ná mar a chumasadh saghas. Ní chiallaíonn sé go mbeidh merge sórtáil a bheith níos tapúla le haghaidh gach liosta nó fiú ar aon liosta amháin faoi mhéid áirithe. Mar shampla, d'fhéadfadh a bheith saghas isteach an saghas is tapúla le haghaidh gach liosta níos lú ná 5 heilimintí sin. I gcleachtas, merge sórtáil de ghnáth níos tapúla le haghaidh liostaí chomh beag agus is 50 heilimintí sin. 

Ach ní dhéanann an luas breise a thagann gan ar phraghas. Murab ionann agus ár n-cineál eile, a chur ar liosta agus a mhodhnú an liosta atá i bhfeidhm go dtí go bhfaigheann muid liosta curtha in eagar, ní mór merge sórtáil roinnt spás breise a chumasadh 2 liosta le chéile. Ní féidir linn a úsáid láithreach na liostaí atá á chumasc a stóráil ar an liosta cumaiscthe ós rud é a d'fhéadfadh muid a shárú gnéithe mór a chomhall fós a chumasc. Tá an spás le beagán de phraghas, ach tá sé de ghnáth ní míréasúnta. Agus sin é do sort chumaiscthe. 

Is é mo ainm Rob Bowden, agus tá sé seo CS50. [CS50.TV] - Agus roghnú saghas. [Gáirí] Ó, fuair a ghlacadh go amach freisin mar gheall ar athraigh mé conas a bhí i láthair mé é. Liosta ar thaobh na láimhe clé. Ba é sin a typo. [Misspoke] screwed mé suas - [Gáirí] Níl a fhios agam cad -