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

Խաղաքարտերը դասավորելու բազում ձևեր կան։ Ահա մի պարզ օրինակ, որը կոչվում է ընտրական տեսակավորում, որը նման է քո դասավորածին․

Այս ալգորիթմը կոչվում է ընտրական տեսակավորում, քանի որ այն շարունակաբար ընտրում է հաջորդ ամենափոքր տարրը և դնում է համապատասխան տեղում։

Ստորև կարող ես տեսնել ալգորիթմը։

Ալգորիթմն ինքդ տեսնելուց հետո ի՞նչ ես մտածում դրա մասին։ Ո՞ր մասերի վրա է երկար ժամանակ ծախսվում։ Ի՞նչ ես կարծում՝ ինչպե՞ս այն կաշխատի մեծ զանգվածների համար։ Այս հարցերը մտքումդ ունեցիր ալգորիթմն օգտագործելիս։

Ընտրական տեսակավորման քայլերից մեկը հաջորդ ամենափոքրը գտնելն ու այն ճիշտ տեղում դնելն է։ Օրինակ, եթե զանգվածի տարրերը [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-ի կողմից։