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

Պղպջակային տեսակավորում (Bubble Sort)

Տրված է n ամբողջ թվերից կազմված զանգված, որը ցանկանում ենք տեսակավորել աճման կարգով։ Bubble Sort (Պղպջակային տեսակավորում) ալգորիթմը ամենատարածված տարբերակներից մեկն է այդ խնդիրը լուծելու համար (պետք է նշել, որ այն բավականին դանդաղ է, ուստի իրական ծրագրերում հիմնականում նախընտրում են ավելի արդյունավետ տեսակավորման մեթոդներ)։
Video preview
Պղպջակային տեսակավորման հիմնական գաղափարը հետևյալն է․ զանգվածի վրայով մի քանի անգամ անցնում ենք և հարևան այն էլեմենտները, որոնք աճման կարգով չեն դասավորված, տեղերով փոխում ենք։ Այսինքն, եթե , ապա այդ երկու տարրերը տեղերով փոխում ենք՝ զանգվածը քայլ առ քայլ տանելով ավելի ճիշտ դասավորվածության։
Օրինակ եթե a նախնական զանգվածը [4, 1, -1, 0, 2, 8] է, մենք նախ դիտարկում ենք առաջին երկու էլեմենտները։ Եթե դրանք ճիշտ չեն դասավորված, ապա փոխում ենք տեղերով (մեր օրինակում [1, 4, -1, 0, 2, 8])։ Այնուհետև նույնն անում ենք հաջորդ զույգի համար։ Եթե կարիք կա, կրկին փոխում ենք դրանք տեղերով (մեր օրինակում [1, -1, 4, 0, 2, 8])։ Այսպես շարունակում ենք մինչև հասնենք զանգվածի վերջին, ինչի արդյունքում [1, -1, 4, 0, 2, 8] → [1, -1, 0, 4, 2, 8] → [1, -1, 0, 2, 4, 8] → այլևս փոփոխություն չկա → այս անցումն ավարտվում է։
Հաջորդ քայլին, այս ամենը կրկին սկսում ենք զանգվածի սկզբից։ Նորից զույգ առ զույգ ստուգում ենք էլեմենտները և, եթե դրանք աճման կարգով չեն, տեղերով փոխում ենք։ Մեր օրինակում կստացվի՝ [1, -1, 0, 2, 4, 8] → [-1, 1, 0, 2, 4, 8] → [-1, 0, 1, 2, 4, 8] → ուրիշ փոփոխություն չկա։
Այս քայլերն կրկնվում են, մինչև ամբողջ զանգվածը տեսակավորվի.
a = [...]
while True:                                 # այնքան, որ զանգվածը տեսակավորվի
    is_sorted = True                        # եթե ինչ-որ բան փոխենք, դնում ենք այն False
    for i in range(len(a) - 1):             # շարժվենք սկսած 0-ից մինչև n-2
        if a[i] > a[i + 1]:                 # եթե որևէ բան իր տեղում չէ
            is_sorted = False               # => զանգվածը տեսակավորված չէր
            a[i], a[i + 1] = a[i + 1], a[i] # տեղերով փոխել a[i]-ն և a[i + 1]-ը
    
    if is_sorted:                           # դադարեցնել ալգորիթմը, եթե a-ն տեսակավորված է
        break
print(a)
Կարելի է կատարել մեկ պարզ օպտիմիզացիա, որպեսզի ավելորդ քայլեր չարենք․
  • Յուրաքանչյուր ցիկլի քայլիս հետո ամենամեծ էլեմենտները տեղակայվում են զանգվածի վերջում։ Ուստի, եթե կատարել ենք արդեն k անցում, ապա զանգվածի վերջին k տարրերը հաստատ ճիշտ դասավորված են (և դրանք ամենամեծ տարրերն են)։ Դա թույլ է տալիս ներքին ցիկլում բաց թողնել զանգվածի այդ մասը.
a = [...]
for u in range(len(a) - 1, 0, -1):          # u = ներքին ցիկլի վերին սահմանը
    is_sorted = True                        # եթե ինչ-որ բան փոխենք, այն դնում ենք False
    for i in range(u):                      # գնում ենք 0-ից մինչև u-1
        if a[i] > a[i + 1]:                 # եթե որևէ բան իր տեղում չէ
            is_sorted = False               # => զանգվածը տեսակավորված չէր
            a[i], a[i + 1] = a[i + 1], a[i] # տեղերով փոխում ենք a[i]-ն և a[i + 1]-ը
    
    if is_sorted:                           # դադարեցնել ալգորիթմը, եթե a-ն տեսակավորված է
        break
print(a)
Պղպջակային տեսակավորման ամենավատ դեպքը այն է, երբ թվերը լրիվ հակառակ կարգով են շարված (այսինքն՝ նվազման կարգով), և այդ դեպքում ալգորիթմը կատարում է գործողություն։ Դա բավականին դանդաղ է, եթե համեմատենք ավելի արագ տեսակավորման ալգորիթմների հետ, որոնք կքննարկենք հետագա դասերում։
Եկեք դիտարկենք, թե ինչպես է ալգորիթմը աշխատում մի քանի տարբեր զանգվածների վրա՝
[4, 1, -1, 0, 2, 8]
  1. u = 5
    1. i = 0 ⇒ swap ⇒ [1, 4, -1, 0, 2, 8]
    2. i = 1 ⇒ swap ⇒ [1, -1, 4, 0, 2, 8]
    3. i = 2 ⇒ swap ⇒ [1, -1, 0, 4, 2, 8]
    4. i = 3 ⇒ swap ⇒ [1, -1, 0, 2, 4, 8]
    5. i = 4 ⇒ do nothing
  1. i = 0 ⇒ swap ⇒ [1, 4, -1, 0, 2, 8]
    1. i = 0 ⇒ swap ⇒ [-1, 1, 0, 2, 4, 8]
    2. i = 1 ⇒ swap ⇒ [-1, 0, 1, 2, 4, 8]
    3. i = 2 ⇒ do nothing
    4. i = 3 ⇒ do nothing
  1. i = 1 ⇒ swap ⇒ [1, -1, 4, 0, 2, 8]
    1. i = 0 ⇒ do nothing
    2. i = 1 ⇒ do nothing
    3. i = 2 ⇒ do nothing
    4. is_sorted is True ⇒ break
  1. i = 2 ⇒ swap ⇒ [1, -1, 0, 4, 2, 8]
[10, 5, 1, -1, -2, -7]
  1. u = 5
    1. i = 0 ⇒ swap ⇒ [5, 10, 1, -1, -2, -7]
    2. i = 1 ⇒ swap ⇒ [5, 1, 10, -1, -2, -7]
    3. i = 2 ⇒ swap ⇒ [5, 1, -1, 10, -2, -7]
    4. i = 3 ⇒ swap ⇒ [5, 1, -1, -2, 10, -7]
    5. i = 4 ⇒ swap ⇒ [5, 1, -1, -2, -7, 10]
  1. i = 0 ⇒ swap ⇒ [5, 10, 1, -1, -2, -7]
    1. i = 0 ⇒ swap ⇒ [1, 5, -1, -2, -7, 10]
    2. i = 1 ⇒ swap ⇒ [1, -1, 5, -2, -7, 10]
    3. i = 2 ⇒ swap ⇒ [1, -1, -2, 5, -7, 10]
    4. i = 3 ⇒ swap ⇒ [1, -1, -2, -7, 5, 10]
  1. i = 1 ⇒ swap ⇒ [5, 1, 10, -1, -2, -7]
    1. i = 0 ⇒ swap ⇒ [-1, 1, -2, -7, 5, 10]
    2. i = 1 ⇒ swap ⇒ [-1, -2, 1, -7, 5, 10]
    3. i = 2 ⇒ swap ⇒ [-1, -2, -7, 1, 5, 10]
  1. i = 2 ⇒ swap ⇒ [5, 1, -1, 10, -2, -7]
    1. i = 0 ⇒ swap ⇒ [-2, -1, -7, 1, 5, 10]
    2. i = 1 ⇒ swap ⇒ [-2, -7, -1, 1, 5, 10]
  1. i = 3 ⇒ swap ⇒ [5, 1, -1, -2, 10, -7]
    1. i = 0 ⇒ swap ⇒ [-7, -2, -1, 1, 5, 10]
  1. i = 4 ⇒ swap ⇒ [5, 1, -1, -2, -7, 10]
[1, 2, 3, 4, 5]
  1. u = 5
    1. i = 0 ⇒ do nothing
    2. i = 1 ⇒ do nothing
    3. i = 2 ⇒ do nothing
    4. i = 3 ⇒ do nothing
    5. i = 4 ⇒ do nothing
    6. is_sorted is True ⇒ break
  1. i = 0 ⇒ do nothing
Հհետաքրքիր տեսանյութ
YouTube-ում կա Lines That Connect ալիքի կողմից ստեղծված մի հրաշալի տեսանյութ, որտեղ ավելի խորությամբ ներկայացվում է Bubble Sort (Պղպջակային տեսակավորման) ալգորիթմը և բացատրվում է այն գրաֆիկի տրամաբանությունը, որը ձևավորվում է ալգորիթմի աշխատանքի ընթացքում։
Video preview
Տեսանյութ՝ Lines That Connect ալիքի կողմից - The Bubble Sort Curve:

Առաջադրանք

n անձինք մասնակցում են մրցույթի։ Անհրաժեշտ է նրանց շարք կանգնեցնել ըստ հասակի՝ աճման կարգով։ Յուրաքանչյուր քայլի թույլատրվում է միայն երկու հարևան մասնակցի տեղերով փոխել։ Ժամանակը սուղ է, և դուք ցանկանում եք հնարավորինս քիչ քայլերով անել այս ամենը։
Դուք որոշել եք գրել ծրագիր, որը պետք է տպի այն զույգ ինդեքսները, որոնցում գտնվող մասնակիցները պետք է տեղերով փոխվեն։ Ինդեքսավորումը սկսվում է 0-ից։

Մուտք

Մուտքի առաջին տողում տրված է n (1 ≤ n ≤ 1000) ամբողջ թիվը։
Հաջորդ տողում տրված են n ամբողջ թվեր ( ≤ ≤ ) — մասնակիցների հասակները։

Ելք

Ծրագիրը պետք է տպի այն զույգ ինդեքսները, որոնցում գտնվող մասնակիցները պետք է տեղերով փոխվեն։ Յուրաքանչյուր զույգ պետք է տպվի առանձին տողում։ Թույլատրելի են բազմաթիվ ճիշտ պատասխաններ, ուստի եթե կա մի քանի տարբերակ, կարելի է տպել դրանցից ցանկացածը։

Օրինակներ

Մուտք
Ելք
5 1 4 8 2 -1
2 3 3 4 1 2 2 3 1 2 0 1

Պարզաբանում

  1. 2 ↔ 3 ⇒ 1 4 2 8 -1
  1. 3 ↔ 4 ⇒ 1 4 2 -1 8
  1. 1 ↔ 2 ⇒ 1 2 4 -1 8
  1. 2 ↔ 3 ⇒ 1 2 -1 4 8
  1. 1 ↔ 2 ⇒ 1 -1 2 4 8
  1. 0 ↔ 1 ⇒ -1 1 2 4 8
 

Constraints

Time limit: 1.98 seconds

Memory limit: 512 MB

Output limit: 10 MB

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