[Powered by Google Translate] [Sórtáil isteach] [Tommy MacWilliam] [Ollscoil Harvard] [Tá sé seo CS50.TV] A ligean ar ghlacadh le breathnú ar saghas leanas a chur isteach, algartaim as liosta d'uimhreacha agus sórtáil leo. Tá algartam, cuimhnigh, ach nós imeachta céim-ar-chéim do accomplishing tasc. An smaoineamh taobh thiar de bhun saghas isteach, is é a roinnt ár liosta ina dhá chuid, cuid curtha in eagar agus cuid neamhshórtáilte. 

Ag gach céim den algartam, tá roinnt ar athraíodh a ionad as an chuid neamhshórtáilte leis an gcuid in eagar go dtí deireadh an liosta ar fad curtha in eagar. Seo liosta de na sé uimhir neamhshórtáilte - 23, 42, 4, 16, 8, agus 15. Ós rud é nach bhfuil na huimhreacha seo ar fad in ord ardaitheach, tá siad ag neamhshórtáilte. Ós rud é nach mór dúinn tús a shórtáil go fóill, beidh orainn a mheas na sé ghné dár gcuid neamhshórtáilte. 

Nuair a thosaíonn muid ag sórtáil, beidh muid ag na huimhreacha seo in eagar a chur ar an taobh clé de na. Mar sin, a ligean ar tús a chur le 23, an chéad eilimint i ár liosta. Ní thugaimid aon ghnéithe inár chuid curtha in eagar go fóill, mar sin a ligean ar a mheas ach 23 a bheith ar an tús agus deireadh ár gcuid curtha in eagar. Anois, tá ár sciar curtha in eagar aon uimhir amháin, 23, agus tá ár sciar neamhshórtáilte na cúig uimhreacha. Lig isteach anois an chéad uimhir eile sa chuid neamhshórtáilte, 42, isteach sa chuid eagar. 

Chun sin a dhéanamh, beidh orainn an 42 i gcomparáid leis an 23 - an ghné amháin i ár gcuid curtha in eagar go dtí seo. Daichead a dó is mó ná 23, ionas gur féidir linn gceangal ach 42 go dtí deireadh na coda curtha in eagar ar an liosta. Great! Anois, tá ár sciar curtha in eagar dhá ghné, agus tá ár sciar neamhshórtáilte ceithre ghné. Mar sin, a ligean ar bogadh anois leis an 4, an ghné eile sa chuid neamhshórtáilte. Mar sin, ba chóir nuair is é seo a chur sa chuid curtha in eagar? 

Cuimhnigh, ba mhaith linn chun an uimhir seo in ord sórtáilte mar sin i gcónaí ar ár gcuid sórtáilte mar is ceart curtha in eagar i gcónaí. Má tá ar siúl againn ar an 4 do cheart na 42, ansin beidh ár liosta a bheith as ord. Mar sin, a ligean ar aghaidh ag bogadh ceart-go-chlé i ár gcuid saghas. Agus muid ag bogadh, a ligean ar athrú gach uimhir síos in áit seomra a dhéanamh ar an líon nua. Maith go leor, is é 4 níos lú ná 23, mar sin ní féidir linn é a chur anseo ach an oiread. A ligean ar bogadh an 23 ceart áit amháin. 

Ciallaíonn sin ba mhaith linn chun an 4 isteach sa sliotán den chéad uair sa chuid eagar. Fógra conas a bhí an spás seo ar an liosta cheana folamh, mar tá muid ag bogadh eilimintí eagar síos mar a bhíonn againn orthu. Gach ceart. Mar sin, tá muid leathbhealach ann. A ligean ar leanúint ar aghaidh lenár algartam tríd an 16 isteach sa chuid eagar. Sé cinn déag de níos lú ná 42, mar sin a ligean ar an 42 a aistriú chuig an ceart. Sé cinn déag freisin níos lú ná 23, mar sin a ligean aistriú freisin an eilimint. 

Anois, tá 16 níos mó ná 4. Mar sin, tá sé cosúil mhaith linn a chur isteach ar an 16 idir an 4 agus an 23. Cé ag gluaiseacht tríd an chuid curtha in eagar ar an liosta ó ceart ar chlé, Is é 4 an chéad uimhir againn le feiceáil go bhfuil níos lú ná an líon táimid ag iarraidh a chur isteach. Mar sin, anois is féidir linn a chur isteach ar an 16 isteach sa sliotán folamh, a bhfuil, cuimhnigh, tá muid cruthaithe ag gnéithe gluaiseacht sa chuid saghas thar mar a againn a bhíonn orthu. 

Gach ceart. Anois, ní mór dúinn ceithre ghné curtha in eagar agus dhá eilimint neamhshórtáilte. Mar sin, a ligean ar bogadh an 8 isteach sa chuid eagar. Tá ocht níos lú ná 42. Tá ocht níos lú ná 23. Agus is é 8 lú ná 16. Ach tá níos mó ná 8 4. Mar sin, ba mhaith linn a chur isteach ar an 8 idir an 4 agus an 16. Agus anois tá ach gné amháin níos mó a d'fhág a shórtáil - an 15. Tá cúig cinn déag de níos lú ná 42, Tá cúig cinn déag de níos lú ná 23. Agus is é 15 níos lú ná 16. Ach tá 15 níos mó ná 8. 

Mar sin, tá anseo áit ar mhaith linn a dhéanamh ar ár leanas a chur isteach deiridh. Agus muid ag déanamh. Tá aon eilimintí níos mó sa chuid neamhshórtáilte, agus is é ár sciar curtha in eagar san ord ceart. Na huimhreacha ordú ó lú go dtí mó. Mar sin, a ligean ar ghlacadh le breathnú ar roinnt pseudocode a chuireann síos ar na céimeanna a dhéantar againn ach. 

Ar líne 1, is féidir linn a fheiceáil go beidh orainn a iterate thar gach gné ar an liosta ach amháin an gcéad dul síos, beidh ós rud é an chéad eilimint sa chuid neamhshórtáilte a bheith simplí an chéad eilimint sa chuid eagar. Ar línte 2 agus 3, tá muid ag súil a choinneáil ar ár n-áit chónaithe reatha sa chuid neamhshórtáilte. Eilimint Is ionann an líon táimid ag bogadh faoi láthair isteach sa chuid curtha in eagar, agus is ionann j ár innéacs isteach sa chuid neamhshórtáilte. 

Ar líne 4, tá muid ag iterating tríd an chuid eagar ó ceart chun chlé. Ba mhaith linn a stopadh iterating uair an eilimint an taobh clé den ár suíomh reatha níos lú ná an eilimint táimid ag iarraidh a chur isteach. Ar líne 5, tá muid ag aistriú gach eilimint muid ar cheann spás a bhíonn ar dheis. Sa chaoi sin, beidh orainn spás soiléir a chur isteach i nuair a fhaigheann muid an chéad eilimint níos lú ná an eilimint táimid ag gluaiseacht. Ar líne 6, tá muid ag cothrom le dáta ár gcuntar chun leanúint ar aghaidh chun bogadh ar chlé tríd an chuid eagar. Ar deireadh, líne 7, táimid tríd an eilimint isteach sa chuid curtha in eagar ar an liosta. 

Tá a fhios againn go bhfuil sé ceart go leor a chur isteach i j seasamh, mar tá muid ar athraíodh a ionad cheana féin ar an eilimint a úsáidtear a bheith ann spás amháin leis an gceart. Cuimhnigh, tá muid ag bogadh tríd an chuid eagar ó ceart ar chlé, ach táimid ag gluaiseacht tríd an chuid neamhshórtáilte ó chlé go deas. Gach ceart. A ligean ar a ghlacadh anois le breathnú ar cé chomh fada ag rith a tharla algartam. Beidh muid a iarraidh ar dtús leis an cheist cé chomh fada a thógann sé ar an algartam a reáchtáil sa chás is measa. Glaoch ar ais go ionadaíocht againn an uair seo ag rith le nodaireacht O Big. D'fhonn a shórtáil ar ár liosta, bhí againn a iterate ar na gnéithe seo sa chuid neamhshórtáilte, agus do gach ceann de na gnéithe sin, d'fhéadfadh a bheith os cionn gach eilimint sa chuid eagar. Intuitively, fuaimeanna seo cosúil le oibríocht (n ^ 2) O. 

Ag Breathnú ar an pseudocode, ní mór dúinn a lúb neadaithe taobh istigh eile lúb, a bhfuil, go deimhin, fuaimeanna, cosúil le feidhmiú le (n ^ 2) O. Mar sin féin, ní raibh an chuid curtha in eagar de liosta an liosta iomlán go dtí deireadh an-. Fós, d'fhéadfadh muid a chur isteach d'fhéadfadh a bheith ina ghné nua ag tús an-an chuid eagar ar gach atriall an algartam, rud a chiallaíonn gur mhaith linn a bheith chun breathnú ar gach gné faoi láthair sa chuid eagar. Mar sin, ciallaíonn sé go bhféadfadh muid a dhéanamh d'fhéadfadh a bheith ar cheann i gcomparáid le haghaidh an dara gné, dhá comparáidí le haghaidh an tríú gné, agus mar sin de. Mar sin, tá an líon iomlán na céimeanna suim na slánuimhreacha ó 1 go fad an liosta lúide 1. Is féidir linn seo a léiriú le go léir a shuimiú. 

Ní féidir linn dul i summations anseo, ach anois sé amach go bhfuil an tsuimithe cothrom le n (n - 1) os cionn 2, a bhfuil n comhionann ^ 2/2 - n / 2. Nuair a labhairt faoi runtime asymptotic, tá sé seo ^ n 2 téarma ag dul a tionchar an-mhór an téarma n. Mar sin, tá saghas isteach Big O (n ^ 2). Cad a tharlaíonn má bhí ar siúl againn saghas isteach ar an liosta sórtáilte cheana. Sa chás sin, ba mhaith linn a thógáil ach suas an chuid eagar ó chlé go deas. Mar sin, beidh orainn gá ach ar an ord céimeanna n. 

Ciallaíonn sé sin go bhfuil saghas isteach ar fheidhmíocht is fearr ar chás na n, a dhéanann ionadaíocht againn le Ω (n). Agus sin é do saghas leanas a chur isteach, ach ceann amháin de na halgartaim is féidir linn a úsáid a shórtáil liosta. Is é mo ainm Tommy, agus tá sé seo CS50. [CS50.TV] Ó, tá tú nach féidir stop a chur díreach go uair a thosaíonn sé. Ó, rinne muid go - Boom >>!