Ալգորիթմներ և Տվյալների Կառուցվածքներ

Ընտրությամբ տեսակավորում (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)
Յուրաքանչյուր քայլին մենք վերցնում ենք մնացած մասից նվազագույն արժեքը և տեղերով փոխում այն ընթացիկ էլեմենտի հետ, օգտագործելով դրանց ինդեքսները։ Եթե ընթացիկ էլեմենտն արդեն նվազագույնն է, ապա պարզապես ինքն իր հետ տեղերով փոխելիս ոչինչ չի փոխվում զանգվածում։
 
Ընտրությամբ տեսակավորման ալգորիթմը յուրաքանչյուր փուլում գտնում է զանգվածի նվազագույն արժեքը և տեղերով փոխում այն ընթացիկ ինդեքսի արժեքի հետ։ Սա նշանակում է, որ ամեն քայլին մենք անցնում ենք ամբողջ մնացած ենթազանգվածի վրայով՝ նվազագույն արժեքը գտնելու համար: Արդյունքում ալգորիթմի ընդհանուր բարդությունը ստացվում է n կրկնություն, որից յուրաքանչյուրն իրականացնում է մոտավորապես n գործողություն ⇒ ։
Եկեք փորձենք ալգորիթմը մի քանի օրինակի վրա.
[4, 1, -1, 0, 2, 8]
  1. i = 0 ⇒ val = -1 ⇒ idx = 2 ⇒ տեղերով փոխել ⇒ [-1, 1, 4, 0, 2, 8]
  1. i = 1 ⇒ val = 0 ⇒ idx = 3 ⇒ տեղերով փոխել ⇒ [-1, 0, 4, 1, 2, 8]
  1. i = 2 ⇒ val = 1 ⇒ idx = 3 ⇒ տեղերով փոխել ⇒ [-1, 0, 1, 4, 2, 8]
  1. i = 3 ⇒ val = 2 ⇒ idx = 4 ⇒ տեղերով փոխել ⇒ [-1, 0, 1, 2, 4, 8]
  1. i = 4 ⇒ val = 4 ⇒ idx = 4 ⇒ տեղերով փոխել ⇒ [-1, 0, 1, 2, 4, 8]
  1. i = 5 ⇒ val = 8 ⇒ idx = 5 ⇒ տեղերով փոխել ⇒ [-1, 0, 1, 2, 4, 8]
[10, 5, 1, -1, -2, -7]
  1. i = 0 ⇒ val = -7 ⇒ idx = 5 ⇒ տեղերով փոխել ⇒ [-7, 5, 1, -1, -2, 10]
  1. i = 1 ⇒ val = -2 ⇒ idx = 4 ⇒ տեղերով փոխել ⇒ [-7, -2, 1, -1, 5, 10]
  1. i = 2 ⇒ val = -1 ⇒ idx = 3 ⇒ տեղերով փոխել ⇒ [-7, -2, -1, 1, 5, 10]
  1. i = 3 ⇒ val = 1 ⇒ idx = 3 ⇒ տեղերով փոխել ⇒ [-7, -2, -1, 1, 5, 10]
  1. i = 4 ⇒ val = 5 ⇒ idx = 4 ⇒ տեղերով փոխել ⇒ [-7, -2, -1, 1, 5, 10]
  1. i = 5 ⇒ val = 10 ⇒ idx = 5 ⇒ տեղերով փոխել ⇒ [-7, -2, -1, 1, 5, 10]
[1, 2, 3, 4, 5]
  1. i = 0 ⇒ val = 1 ⇒ idx = 0 ⇒ տեղերով փոխել ⇒ [1, 2, 3, 4, 5]
  1. i = 1 ⇒ val = 2 ⇒ idx = 1 ⇒ տեղերով փոխել ⇒ [1, 2, 3, 4, 5]
  1. i = 2 ⇒ val = 3 ⇒ idx = 2 ⇒ տեղերով փոխել ⇒ [1, 2, 3, 4, 5]
  1. i = 3 ⇒ val = 4 ⇒ idx = 3 ⇒ տեղերով փոխել ⇒ [1, 2, 3, 4, 5]
  1. i = 4 ⇒ val = 5 ⇒ idx = 4 ⇒ տեղերով փոխել ⇒ [1, 2, 3, 4, 5]

Առաջադրանք

Ունենալով n ամբողջ թվեր, ձեզ խնդրում են տեսակավորել դրանք աճման կարգով։

Մուտք

Մուտքի առաջին տողում տրված է մեկ ամբողջ թիվ n (1 ≤ n ≤ 1000) — զանգվածի էլեմենտների քանակը:
Հաջորդ տողում տրված են n բացատով բաժանված ամբողջ թվեր ( ≤ ≤ ):

Ելք

Ծրագիրը պետք է տպի մուտքում տրված զանգվածը տեսակավորված աճման կարգով:

Օրինակներ

Մուտք
Ելք
5 5 5 3 2 3
2 3 3 5 5

Constraints

Time limit: 2 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in
Sign in to continue