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

Տեղադրումով տեսակավորում (Insertion sort)

Տեղադրումով տեսակավորում ալգորիթմը շատ նման է selection sort ալգորիթմին։ Այն բավականին ինտուիտիվ է. Ալգորիթմը միշտ պահպանում է զանգվածի ձախ մասի տեսակավորված վիճակը և շարունակաբար շարժվում է դեպի աջ՝ քանի դեռ չի հասել զանգվածի վերջին։
Video preview
Insertion sort ալգորիթմում մենք սկսում ենք զանգվածի ամենաձախ էլեմենտից և քայլ առ քայլ շարժվում դեպի աջ։ Հենց հանդիպում ենք արժեքի, որը փոքր է ձախ կողմում գտնվող էլեմենտներից, հերթով մեկ դիրք աջ ենք հրում այդ էլեմենտները, որպեսզի տեղ ազատենք և նոր արժեքը տեղադրենք համապատասխան դիրքում։ Օրինակ, եթե ունենք [0, 2, 4, 1, 10, 8] զանգվածը և դիտարկում ենք 1 արժեքը, նախ մի քայլով աջ ենք հրում 4-ը, հետո 2-ը և ապա 1-ը տեղադրում ենք 0-ի ու 2-ի միջև՝ ստանալով [0, 1, 2, 4, 10, 8]։ Հաջորդ քայլին դիտարկում ենք 10-ը, բայց ոչինչ չենք անում, քանի որ այն մեծ է ձախ կողմի բոլոր էլեմենտներից։ Այնուհետև վերցնում ենք 8-ը, և մեկ քայլով աջ ենք հրում 10-ը, որպեսզի 8-ը տեղադրենք 4-ի ու 10-ի միջև։
a = [...]
for i in range(1, len(a)):              # սկսում ենք երկրորդ էլեմենտից
    while i > 0 and a[i] < a[i - 1]:    # քանի դեռ ընթացիկ էլեմենտը փոքր է նախորդից
        a[i - 1], a[i] = a[i], a[i - 1] # տեղերով փոխում ենք ընթացիկ էլեմենտը նախորդի հետ
        i -= 1                          # հետևեում ենք ընթացիկ էլեմենտի ինդեքսին
print(a)
Insertion sort ալգորիթմը ամեն հաջորդ էլեմենտը տեղադրում է արդեն սորտավորված մասի ճիշտ դիրքում։ Այդ պատճառով, ամենավատ դեպքում (երբ զանգվածի էլեմենտները նվազման կարգով են դասավորված), յուրաքանչյուր նոր էլեմենտի համար հարկավոր է շարժել մինչ այդ գտնվող բոլոր էլեմենտները, ինչի արդյունքում ընդհանուր գործողությունների քանակը ստացվում է ։
 
Եկեք փորձենք ալգորիթմը մի քանի օրինակի վրա.
[4, 1, -1, 0, 2, 8]
  1. i = 1 ⇒ փոխանակում ⇒ [1, 4, -1, 0, 2, 8]
  1. i = 2 ⇒ փոխանակում ⇒ [1, -1, 4, 0, 2, 8] ⇒ փոխանակում ⇒ [-1, 1, 4, 0, 2, 8]
  1. i = 3 ⇒ ոչինչ չի արվում
  1. i = 4 ⇒ փոխանակում ⇒ [-1, 1, 0, 4, 2, 8] ⇒ փոխանակում ⇒ [-1, 0, 1, 2, 4, 8]
  1. i = 5 ⇒ ոչինչ չի արվում
  1. տպում ⇒ [-1, 0, 1, 2, 4, 8]
[10, 5, 1, -7]
  1. i = 1 ⇒ փոխանակում ⇒ [5, 10, 1, -7]
  1. i = 2 ⇒ փոխանակում ⇒ [5, 1, 10, -7] ⇒ փոխանակում ⇒ [1, 5, 10, -7]
  1. i = 3 ⇒ փոխանակում ⇒ [1, 5, -7, 10] ⇒ փոխանակում ⇒ [1, -7, 5, 10] ⇒ փոխանակում ⇒ [-7, 1, 5, 10]
[1, 2, 3, 4, 5]
  1. i = 1 ⇒ ոչինչ չի արվում
  1. i = 2 ⇒ ոչինչ չի արվում
  1. i = 3 ⇒ ոչինչ չի արվում
  1. i = 4 ⇒ ոչինչ չի արվում

Առաջադրանք

Տրված են n ամբողջ թվեր, որոնք պետք է տեղադրման տեսակավորմամբ դասավորել աճման կարգով։

Մուտք

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

Ելք

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

Օրինակներ

Input
Output
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