[MUZIKO Ludante] DOUG LLOYD: Selektado speco estas algoritmo kiu, kiel vi eble atendus, ordigas aron de elementoj. Kaj algoritmo revokon Estas paŝo-de-paŝo aro de instrukcioj por kompletigado de tasko. 

En selektado ordigi la baza ideo estas jena: trovi la plej malgranda elemento kaj unsorted aldoni ĝin al la fino de la ordo listo. Efike kio ĉi faras estas muntaĵo a ordo listo, unu elementon je fojo. Rompanta ĝin malsupren al _pseudocode_ ni povis konstati tiun algoritmon jene, ripeti ĉi ĝis neniu unsorted elementoj restas. Serĉu tra la unsorted datumoj por trovi la plej malgranda valoro, tiam interŝanĝi la plej malgranda valoro kun la unua elemento de la unsorted parto. 

Eble helpos bildigi tion, do ni rigardu tiun. Do ĉi, mi disputi, estas unsorted tabelo kaj mi havas indikis ĝin indikante ke ĉiuj de la elementoj estas koloritaj ruĝaj, Ili ankoraŭ ne ordigita. Tiu estas la tuta unsorted parto de la tabelo. 

Do ni iru tra la paŝoj de selektado speco ordigi ĉi tabelo. Do denove, ni estas gonna ripeto ĝis neniu unsorted elementoj restas. Ni estas gonna serĉo tra la datumoj por trovi la plej malgranda valoro, kaj tiam interŝanĝi tiun valoron kun la unua elemento de la unsorted parto. 

Ĝuste nun, denove, la tuta tabelo estas la unsorted parto. Ĉiuj de la ruĝaj elementoj estas unsorted. Do ni serĉu tra kaj ni trovos la plej malgranda valoro. Ni starti je la komenco, ni iru al la fino, ni trovos la plej malgranda valoro estas, unu. Do jen parto unu. Kaj poste parto du, interŝanĝu tiun valoron kun la unua elemento de la unsorted parto, aŭ la unua ruĝa elemento. 

En ĉi tiu kazo kiu estus kvin, do ni interŝanĝu unu kaj kvin. Kiam ni fari tion ĉi, ni povas vide vidi ke ni kopiis la malgranda valora elemento de la tabelo, por la tre komenco. Efike ordigado tiu elemento. 

Kaj tiel ni povas ja konfirmas kaj stato ke oni, estas ordo. Kaj do ni indikos la ordo parto de nia tabelo, per coloreando bluajn. 

Nun ni nur ripeti la procezon denove. Ni traserĉu la unsorted parto de la tabelo por trovi la plej malgranda ero. En tiu kazo, ĝi estas du. 

Ni interŝanĝu ke kun la unua elemento de la unsorted parto. En tiu kazo du ankaŭ hazarde estas la unua elemento de la unsorted parto. Do ni interŝanĝu du kun sin, kiuj vere nur lasas du kie estas, kaj ĝi estas ordo. Daŭrigante sur, ni serĉu pere por trovi la plej malgranda ero. Estas tri. Ni interŝanĝu ĝin kun la unua elemento, kiu estas kvin. Kaj nun tri estas ordo. 

Ni serĉu pere denove, kaj ni trovi la plej malgranda elemento estas kvar. Ni interŝanĝu ĝin kun la unua elemento de la unsorted parton, kaj nun kvar estas ordo. 

Ni trovas ke kvin estas la plej malgranda ero. Ni interŝanĝu ĝin kun la unua elemento de la unsorted parto. Kaj nun kvin estas ordo. 

Kaj poste persiste, nia unsorted parto konsistas de nur unu elemento, do ni serĉu pere kaj ni trovas ke ses estas la malgranda, kaj fakte, nur elemento. Kaj tiam ni povas aserti ke ĝi estas ordo. Kaj nun ni ŝanĝis nia tabelo de estanta tute unsorted en ruĝa, al tute ordigitaj en blua, uzante selektado varon. 

Do kio estas la plej malbona kazo scenaron ĉi tie? Nu en la absoluta plej malbona kazo, ni devas rigardi super ĉiuj de la elementoj de la tabelo trovi la plej malgranda unsorted elemento, kaj ni devas ripeti tiun procezon n fojojn. Unufoje por ĉiu elemento de la tabelo ĉar ni nur, en ĉi tiu algoritmo, ia unu elementon je fojo. 

Kio estas la plej bona kazo scenaro? Nu ĝi estas precize la sama, ĉu ne? Ni fakte devos ankoraŭ paŝi tra ĉiu unuopa elemento de la tabelo por konfirmi, ke ĝi estas, fakte, la plej malgranda ero. 

Do la plej malbona kazo tempo de ekzekuto, ni devi ripeti procezon n fojojn, unufoje por ĉiu el n elementoj. Kaj en la plej bona kazo scenaro, ni devas fari la saman. 

Do pensante reen al nia komputa komplekseca toolbox, kion vi pensas estas la plej malbona kazo tempo de ekzekuto por selektado speco? Kion vi pensas estas la plej bona kazo tempo de ekzekuto por selektado speco? 

Ĉu vi divenas Big O de n kvadratoj, kaj Big Omega de n kvadratoj? Vi estus prava. Tiuj estas, fakte, la plej malbona kazo kaj bona kazo run tempoj, por selektado speco. 

Mi Doug Lloyd. Jen CS50.