If you're seeing this message, it means we're having trouble loading external resources on our website.

Եթե գտնվում ես վեբ զտիչի հետևում, խնդրում ենք համոզվել, որ *.kastatic.org և *.kasandbox.org տիրույթները հանված են արգելափակումից։

Հիմնական նյութ

Ընտրական տեսակավորման կեղծ կոդը

Խաղաքարտերը դասավորելու բազում ձևեր կան։ Ահա մի պարզ օրինակ, որը կոչվում է ընտրական տեսակավորում, որը նման է քո դասավորածին․
  1. Գտիր ամենափոքր խաղաքարտը։ Առաջին խաղաքարտի հետ տեղերով փոխիր։
  2. Գտիր երկրորդ ամենափոքր խաղաքարտը։ Երկրորդ խաղաքարտի հետ տեղերով փոխիր։
  3. Գտիր երրորդ ամենափոքր խաղաքարտը։ Երրորդ խաղաքարտի հետ տեղերով փոխիր։
  4. Այդպես շարունակիր այնքան, մինչև ամբողջ զանգվածը կտեսակավորվի։
Այս ալգորիթմը կոչվում է ընտրական տեսակավորում, քանի որ այն շարունակաբար ընտրում է հաջորդ ամենափոքր տարրը և դնում է համապատասխան տեղում։
Ստորև կարող ես տեսնել ալգորիթմը։
Ալգորիթմն ինքդ տեսնելուց հետո ի՞նչ ես մտածում դրա մասին։ Ո՞ր մասերի վրա է երկար ժամանակ ծախսվում։ Ի՞նչ ես կարծում՝ ինչպե՞ս այն կաշխատի մեծ զանգվածների համար։ Այս հարցերը մտքումդ ունեցիր ալգորիթմն օգտագործելիս։

Գտնել ենթազանգվածի ամենափոքր տարրի ցուցիչը

Ընտրական տեսակավորման քայլերից մեկը հաջորդ ամենափոքրը գտնելն ու այն ճիշտ տեղում դնելն է։ Օրինակ, եթե զանգվածի տարրերը [13, 19, 18, 4, 10]-ն են, պետք է սկզբում գտնենք զանգվածի փոքրագույն արժեքի ցուցիչը։ Քանի որ 4-ն է փոքրագույն արժեքը, հետևաբար փոքրագույն արժեքի ցուցիչը 3-ն է։
Ընտրական տեսակավորումը 3 ցուցիչով և 0 ցուցիչով տարրերի տեղերը կփոխի՝ ստանալով [4, 19, 18, 13, 10]։ Հիմա պետք է գտնենք երկրորդ ամենափոքր արժեքի ցուցիչը, որ այն 1\ ցուցչով տարրի հետ տեղերով փոխենք։
Կարող է մի փոքր դժվար լինել երկրորդ ամենափոքր տարրի ցուցիչը գտնող կոդ գրելը։ Մենք վստահ ենք, որ դու կարող ես, բայց ավելի լավ տարբերակ էլ կա։ Ուշադրություն դարձրու, որ ամենափոքր արժեքն արդեն 0 ցուցիչով տեղում է, ուստի մենք իրականում ուզում ենք գտնենք 1\ ցուցչից սկսվող զանգվածի փոքրագույն արժեքը։ Զանգվածի այդ հատվածն անվանում ենք ենթազանգված, հետևաբար այս դեպքում մենք ուզում ենք գտնել 1\ ցուցիչով սկսվող ենթազանգվածի փոքրագույն արժեքը։ Օրինակ, եթե մեր ամբողջ զանգվածը [4, 19, 18, 13, 10]-ն է, ուրեմն 1 ցուցիչով սկսող ենթազանգվածի փոքրագույն արժեքը 10-ն է, և դրա ցուցիչն ամբողջական զանգվածում 4-ն է։ Հետևաբար, զանգվածի երկրորդ ամենափոքր տարրի ցուցիչը 4-ն է։
Փորձիր այս ռազմավարությունը հաջորդ մարտահրավերում և հետո կունենաս այն ամենը, ինչ պետք է՝ ընտրական տեսակավորում ալգորիթմն օգտագործելու համար։

Նյութը ստեղծվել է Դարթմութի համակարգչային գիտությունների դասախոսներ Թոմաս Քորմենի և Դեվին Բալկքոմի, ինչպես նաև «Քան» ակադեմիայի ծրագրավորման թիմի կողմից։ Նյութը լիցենզավորվել է CC-BY-NC-SA-ի կողմից։

Ուզո՞ւմ ես միանալ խոսակցությանը։

Առայժմ հրապարակումներ չկան։
Անգլերեն հասկանո՞ւմ ես: Սեղմիր այստեղ և ավելի շատ քննարկումներ կգտնես «Քան» ակադեմիայի անգլերեն կայքում: