Ընտրության տեսակավորում (Selection sort)
Ընտրության տեսակավորման ալգորիթմը (Selection sort) համարվում է տեսակավորման ամենահասկանալի մեթոդներից մեկը։ Այն բազմիցս գտնում է զանգվածի նվազագույն տարրը և բերում այն զանգվածի սկզբին։ Այնուհետև շարունակում է նույն գործողությունը մնացած մասի համար, մինչև հասնում է զանգվածի ամենավերջին էլեմենտին։
a = [...]
for i in range(len(a)): # Պետք է a[i:] տիրույթից հայտնաբերված նվազագույն տարրը տեղադրենք a[i]-ում
min_idx = i # Նվազագույն տարրի ինդեքսը
for j in range(i + 1, len(a)): # Գտնում ենք նվազագույն տարրի ինդեքսը
if a[j] < a[min_idx]: # Եթե գտնում ենք ավելի փոքր տարր
min_idx = j # Թարմացնում ենք նվազագույն տարրի ինդեքսը
a[i], a[min_idx] = a[min_idx], a[i] # Փոխանակում ենք a[i]-ն և a[min_idx]-ը
print(a)Յուրաքանչյուր կրկնության փուլում, մենք վերցնում ենք մնացած մասից նվազագույն արժեքը և փոխանակում այն ընթացիկ էլեմենտի հետ, օգտագործելով դրանց ինդեքսները։ Եթե ընթացիկ էլեմենտն արդեն նվազագույնն է, ապա պարզապես ինքն իր հետ փոխանակվելը ոչինչ չի փոխում զանգվածում։
Ընտրության տեսակավորման ալգորիթմը յուրաքանչյուր փուլում գտնում է զանգվածի նվազագույն արժեքը և փոխանակում այն ընթացիկ ինդեքսի արժեքի հետ։ Սա նշանակում է, որ ամեն քայլի մենք մեկ անգամ անցնում ենք ամբողջ մնացած ենթազանգվածի վրայով՝ նվազագույն արժեքը détectելու համար (և դա ինքնին ներառում է քայլ առ քայլ թերթում): Արդյունքում ալգորիթմի ընդհանուր բարդությունը ստացվում է
n կրկնություն, որից յուրաքանչյուրն իրականացնում է մոտավորապես n գործողություն ⇒ ։Եկեք մոդելավորենք ալգորիթմը մի քանի զանգվածների վրա.
[4, 1, -1, 0, 2, 8]
i = 0⇒val = -1⇒idx = 2⇒ փոխանակում ⇒[-1, 1, 4, 0, 2, 8]
i = 1⇒val = 0⇒idx = 3⇒ փոխանակում ⇒[-1, 0, 4, 1, 2, 8]
i = 2⇒val = 1⇒idx = 3⇒ փոխանակում ⇒[-1, 0, 1, 4, 2, 8]
i = 3⇒val = 2⇒idx = 4⇒ փոխանակում ⇒[-1, 0, 1, 2, 4, 8]
i = 4⇒val = 4⇒idx = 4⇒ փոխանակում ⇒[-1, 0, 1, 2, 4, 8]
i = 5⇒val = 8⇒idx = 5⇒ փոխանակում ⇒[-1, 0, 1, 2, 4, 8]
[10, 5, 1, -1, -2, -7]
i = 0⇒val = -7⇒idx = 5⇒ փոխանակում ⇒[-7, 5, 1, -1, -2, 10]
i = 1⇒val = -2⇒idx = 4⇒ փոխանակում ⇒[-7, -2, 1, -1, 5, 10]
i = 2⇒val = -1⇒idx = 3⇒ փոխանակում ⇒[-7, -2, -1, 1, 5, 10]
i = 3⇒val = 1⇒idx = 3⇒ փոխանակում ⇒[-7, -2, -1, 1, 5, 10]
i = 4⇒val = 5⇒idx = 4⇒ փոխանակում ⇒[-7, -2, -1, 1, 5, 10]
i = 5⇒val = 10⇒idx = 5⇒ փոխանակում ⇒[-7, -2, -1, 1, 5, 10]
[1, 2, 3, 4, 5]
i = 0⇒val = 1⇒idx = 0⇒ փոխանակում ⇒[1, 2, 3, 4, 5]
i = 1⇒val = 2⇒idx = 1⇒ փոխանակում ⇒[1, 2, 3, 4, 5]
i = 2⇒val = 3⇒idx = 2⇒ փոխանակում ⇒[1, 2, 3, 4, 5]
i = 3⇒val = 4⇒idx = 3⇒ փոխանակում ⇒[1, 2, 3, 4, 5]
i = 4⇒val = 5⇒idx = 4⇒ փոխանակում ⇒[1, 2, 3, 4, 5]
Առաջադրանք
Given
n integers, sort them in increasing order using selection sort.Մուտք
Մուտքի առաջին տողում տրված է մեկ ամբողջ թիվ
n (1 ≤ n ≤ 1000) — զանգվածի էլեմենտների քանակը:Հաջորդ տողում տրված են
n բացատներով բաժանված ամբողջ թվեր (−10^9 ≤ ≤ 10^9):Ելք
Ծրագիրը պետք է տպի մուտքում տրված զանգվածը տեսակավորված աճման կարգով:
Օրինակներ
Մուտք | Ելք |
5
5 5 3 2 3 | 2 3 3 5 5 |
Constraints
Time limit: 1 seconds
Memory limit: 512 MB
Output limit: 1 MB