QuickSort (Արագ տեսակավորում)

Տեսակավորման (sorting) ամենահայտնի ալգորիթմներից մեկը QuickSort-ն է։ Սա «բաժանիր և տիրիր» (divide-and-conquer) սկզբունքով աշխատող ալգորիթմ է, որը յուրաքանչյուր քայլում զանգվածից ընտրում է pivot անունով տարր, այնուհետև զանգվածը բաժանում է pivot-ից փոքր, pivot-ին հավասար և pivot-ից մեծ տարրերի, հետո նույն գործընթացը շարունակում է յուրաքանչյուր մասի վրա, մինչև ամբողջ զանգվածը տեսակավորված լինի։
Այսինքն, յուրաքանչյուր իտերացիայի ընթացքում․
  1. Զանգվածից ընտրում ենք pivot տարրը
  1. pivot-ից փոքր տարրերը տեղափոխում ենք ձախ մաս
  1. pivot-ից մեծ տարրերը տեղափոխում ենք աջ մաս
  1. pivot-ին հավասար բոլոր տարրերը հավաքում ենք մեջտեղում
  1. Ստացված ձախ և աջ մասերի վրա կրկնում ենք նույն գործընթացը
def quicksort(a):
    if len(a) <= 1:
        return a
    pivot = a[len(a) // 2]
    left = [x for x in a if x < pivot]
    middle = [x for x in a if x == pivot]
    right = [x for x in a if x > pivot]
    return quicksort(left) + middle + quicksort(right)
Վերոնշյալ QuickSort-ի իրականացումն օգտագործում է լրացուցիչ զանգվածներ left, middle և right: այն կարելի է դարձնել տեղում (in-place)՝ աշխատելով ինդեքսների միջոցով և տարրերն ուղղակիորեն փոխարկել ίδιο զանգվածում.
def quicksort(a, start, end):
    if start >= end:                    # Չկան տեսակավորելու տարրեր
        return

    pivot = a[start]                    # Ընտրում ենք pivot-ը
    l, r = start + 1, end               # տեսակավորում ենք a[start+1 ... end]
    while l <= r:                       # Քանի դեռ l ≤ r
        if a[l] < pivot:                # եթե a[l] < pivot => թողնում ենք a[l]-ը տեղում
            l += 1
        else:                           # այլապես a[l]-ը տեղափոխում ենք վերջ
            a[l], a[r] = a[r], a[l]
            r -= 1

    a[start], a[r] = a[r], a[start]     # Փոխանակում ենք pivot-ը և a[r]-ը
    quicksort(a, start, r - 1)          # տեսակավորում ենք a[start ... r-1]
    quicksort(a, r + 1, end)            # տեսակավորում ենք a[r+1 ... end]
Երևի նկատեցիք, որ pivot-ի ընտրությունը տարբեր էր այս երկու տարբերակում։ Իրականում, QuickSort ալգորիթմը խիստ կանոն չունի pivot-ի ընտրության հարցում։ Ահա մի քանի տարբերակ pivot ընտրելու համար․
  1. Առաջին տարրը: a[start] (ինչպես երևում է երկրորդ իրականացման մեջ)
  1. Վերջին տարրը: a[end]
  1. Միջին տարրը: a[(start + end + 1) // 2]
  1. Պատահական տարրը: կարելի է վերցնել a[start ... end] միջակայքից ցանկացած էլեմենտ
  1. Միջին (median) տարրը: ընտրել ընթացիկ հատվածի միջինը (ինչը հավասարակշռված բաժանում է ապահովում), սակայն պահանջում է ավելի բարդ իրականացում

Եկեք ցուցադրական օրինակներով տեսնենք, թե ինչպես է ալգորիթմը գործում մի քանի զանգվածների վրա.
[4, 1, -1, 0, 2, 8]
  1. quicksort(a, 0, 5) → pivot = 4 [4, 1, -1, 0, 2, 8]
    1. l=1, r=5a[l] = 1 < pivot ⇒ l += 1
    2. l=2, r=5a[l] = -1 < pivot ⇒ l += 1
    3. l=3, r=5a[l] = 0 < pivot ⇒ l += 1
    4. l=4, r=5a[l] = 2 < pivot ⇒ l += 1
    5. l=5, r=5a[l] = 8 ≥ pivot ⇒ swap a[l] and a[r], r -= 1
    6. swap a[start] and a[r][2, 1, -1, 0, 4, 8]
    7. quicksort(a, 0, 3) and quicksort(a, 5, 5)
  1. quicksort(a, 0, 3) → pivot = 2 [2, 1, -1, 0, 4, 8]
    1. l=1, r=3a[l] = 1 < pivot ⇒ l += 1
    2. l=2, r=3a[l] = -1 < pivot ⇒ l += 1
    3. l=3, r=3a[l] = 0 < pivot ⇒ l += 1
    4. swap a[start] and a[r][0, 1, -1, 2, 4, 8]
    5. quicksort(a, 0, 2) and quicksort(a, 3, 3)
  1. quicksort(a, 0, 2) → pivot = 0 [0, 1, -1, 2, 4, 8]
    1. l=1, r=2a[l] = 1 ≥ pivot ⇒ swap a[l] and a[r], r -= 1 [0, -1, 1, 2, 4, 8]
    2. l=1, r=1a[l] = -1 < pivot ⇒ l += 1
    3. swap a[start] and a[r][-1, 0, 1, 2, 4, 8]
    4. quicksort(a, 0, 0) and quicksort(a, 2, 2)
  1. [-1, 0, 1, 2, 4, 8]
[4, 5, 3, 4, 4, 8, 4, 1, 2, 9, 7, 4, -1]
  1. quicksort(a, 0, 12) → pivot = 4 [4, 5, 3, 4, 4, 8, 4, 1, 2, 9, 7, 4, -1]
    1. l=1, r=12a[l] = 5 ≥ pivot ⇒ swap a[l] and a[r], r -= 1 [4, 5, 3, 4, 4, 8, 4, 1, 2, 9, 7, 4, -1]
    2. l=1, r=11a[l] = -1 < pivot ⇒ l += 1
    3. l=2, r=11a[l] = 3 < pivot ⇒ l += 1
    4. l=3, r=11a[l] = 4 ≥ pivot ⇒ swap a[l] and a[r], r -= 1 [4, -1, 3, 4, 4, 8, 4, 1, 2, 9, 7, 4, 5]
    5. l=3, r=10a[l] = 4 ≥ pivot ⇒ swap a[l] and a[r], r -= 1 [4, -1, 3, 4, 4, 8, 4, 1, 2, 9, 7, 4, 5]
    6. l=3, r=9a[l] = 7 ≥ pivot ⇒ swap a[l] and a[r], r -= 1 [4, -1, 3, 7, 4, 8, 4, 1, 2, 9, 4, 4, 5]
    7. l=3, r=8a[l] = 9 ≥ pivot ⇒ swap a[l] and a[r], r -= 1 [4, -1, 3, 9, 4, 8, 4, 1, 2, 7, 4, 4, 5]
    8. l=3, r=7a[l] = 2 < pivot ⇒ l += 1
    9. l=4, r=7a[l] = 4 ≥ pivot ⇒ swap a[l] and a[r], r -= 1 [4, -1, 3, 2, 4, 8, 4, 1, 9, 7, 4, 4, 5]
    10. l=4, r=6a[l] = 1 < pivot ⇒ l += 1
    11. l=5, r=6a[l] = 8 ≥ pivot ⇒ swap a[l] and a[r], r -= 1 [4, -1, 3, 2, 1, 8, 4, 4, 9, 7, 4, 4, 5]
    12. l=5, r=5a[l] = 4 ≥ pivot ⇒ swap a[l] and a[r], r -= 1 [4, -1, 3, 2, 1, 4, 8, 4, 9, 7, 4, 4, 5]
    13. swap a[start] and a[r][1, -1, 3, 2, 4, 4, 8, 4, 9, 7, 4, 4, 5]
    14. quicksort(a, 0, 3) and quicksort(a, 5, 12)
  1. quicksort(a, 0, 3) → pivot = 1 [1, -1, 3, 2, 4, 4, 8, 4, 9, 7, 4, 4, 5]
    1. l=1, r=3a[l] = -1 < pivot ⇒ l += 1
    2. l=2, r=3a[l] = 3 ≥ pivot ⇒ swap a[l] and a[r], r -= 1 [1, -1, 3, 2, 4, 4, 8, 4, 9, 7, 4, 4, 5]
    3. l=2, r=2a[l] = 2 ≥ pivot ⇒ swap a[l] and a[r], r -= 1 [1, -1, 2, 3, 4, 4, 8, 4, 9, 7, 4, 4, 5]
    4. swap a[start] and a[r][-1, 1, 2, 3, 4, 4, 8, 4, 9, 7, 4, 4, 5]
    5. quicksort(a, 0, 0) and quicksort(a, 2, 3)
  1. quicksort(a, 2, 3) → pivot = 2 [-1, 1, 2, 3, 4, 4, 8, 4, 9, 7, 4, 4, 5]
    1. l=3, r=3a[l] = 3 ≥ pivot ⇒ swap a[l] and a[r], r -= 1 [-1, 1, 2, 3, 4, 4, 8, 4, 9, 7, 4, 4, 5]
    2. swap a[start] and a[r][-1, 1, 2, 3, 4, 4, 8, 4, 9, 7, 4, 4, 5]
    3. quicksort(a, 2, 1) and quicksort(a, 3, 3)
  1. quicksort(a, 5, 12) → pivot = 4 [-1, 1, 2, 3, 4, 4, 8, 4, 9, 7, 4, 4, 5]
    1. l=6, r=12a[l] = 8 ≥ pivot ⇒ swap a[l] and a[r], r -= 1 [-1, 1, 2, 3, 4, 4, 8, 4, 9, 7, 4, 4, 5]
    2. l=6, r=11a[l] = 5 ≥ pivot ⇒ swap a[l] and a[r], r -= 1 [-1, 1, 2, 3, 4, 4, 5, 4, 9, 7, 4, 4, 8]
    3. l=6, r=10a[l] = 4 ≥ pivot ⇒ swap a[l] and a[r], r -= 1 [-1, 1, 2, 3, 4, 4, 4, 4, 9, 7, 4, 5, 8]
    4. l=6, r=9a[l] = 4 ≥ pivot ⇒ swap a[l] and a[r], r -= 1 [-1, 1, 2, 3, 4, 4, 4, 4, 9, 7, 4, 5, 8]
    5. l=6, r=8a[l] = 7 ≥ pivot ⇒ swap a[l] and a[r], r -= 1 [-1, 1, 2, 3, 4, 4, 7, 4, 9, 4, 4, 5, 8]
    6. l=6, r=7a[l] = 9 ≥ pivot ⇒ swap a[l] and a[r], r -= 1 [-1, 1, 2, 3, 4, 4, 9, 4, 7, 4, 4, 5, 8]
    7. l=6, r=6a[l] = 4 ≥ pivot ⇒ swap a[l] and a[r], r -= 1 [-1, 1, 2, 3, 4, 4, 4, 9, 7, 4, 4, 5, 8]
    8. swap a[start] and a[r][-1, 1, 2, 3, 4, 4, 4, 9, 7, 4, 4, 5, 8]
    9. quicksort(a, 5, 4) and quicksort(a, 6, 12)
  1. quicksort(a, 6, 12) → pivot = 4 [-1, 1, 2, 3, 4, 4, 4, 9, 7, 4, 4, 5, 8]
    1. l=7, r=12a[l] = 9 ≥ pivot ⇒ swap a[l] and a[r], r -= 1 [-1, 1, 2, 3, 4, 4, 4, 9, 7, 4, 4, 5, 8]
    2. l=7, r=11a[l] = 8 ≥ pivot ⇒ swap a[l] and a[r], r -= 1 [-1, 1, 2, 3, 4, 4, 4, 8, 7, 4, 4, 5, 9]
    3. l=7, r=10a[l] = 5 ≥ pivot ⇒ swap a[l] and a[r], r -= 1 [-1, 1, 2, 3, 4, 4, 4, 5, 7, 4, 4, 8, 9]
    4. l=7, r=9a[l] = 4 ≥ pivot ⇒ swap a[l] and a[r], r -= 1 [-1, 1, 2, 3, 4, 4, 4, 4, 7, 4, 5, 8, 9]
    5. l=7, r=8a[l] = 4 ≥ pivot ⇒ swap a[l] and a[r], r -= 1 [-1, 1, 2, 3, 4, 4, 4, 4, 7, 4, 5, 8, 9]
    6. l=7, r=7a[l] = 7 ≥ pivot ⇒ swap a[l] and a[r], r -= 1 [-1, 1, 2, 3, 4, 4, 4, 7, 4, 4, 5, 8, 9]
    7. swap a[start] and a[r][-1, 1, 2, 3, 4, 4, 4, 7, 4, 4, 5, 8, 9]
    8. quicksort(a, 6, 5) and quicksort(a, 7, 12)
  1. quicksort(a, 7, 12) → pivot = 7 [-1, 1, 2, 3, 4, 4, 4, 7, 4, 4, 5, 8, 9]
    1. l=8, r=12a[l] = 4 < pivot ⇒ l += 1
    2. l=9, r=12a[l] = 4 < pivot ⇒ l += 1
    3. l=10, r=12a[l] = 5 < pivot ⇒ l += 1
    4. l=11, r=12a[l] = 8 ≥ pivot ⇒ swap a[l] and a[r], r -= 1 [-1, 1, 2, 3, 4, 4, 4, 7, 4, 4, 5, 8, 9]
    5. l=11, r=11a[l] = 9 ≥ pivot ⇒ swap a[l] and a[r], r -= 1 [-1, 1, 2, 3, 4, 4, 4, 7, 4, 4, 5, 9, 8]
    6. swap a[start] and a[r][-1, 1, 2, 3, 4, 4, 4, 5, 4, 4, 7, 9, 8]
    7. quicksort(a, 7, 9) and quicksort(a, 11, 12)
  1. quicksort(a, 7, 9) → pivot = 5 [-1, 1, 2, 3, 4, 4, 4, 5, 4, 4, 7, 9, 8]
    1. l=8, r=9a[l] = 4 < pivot ⇒ l += 1
    2. l=9, r=9a[l] = 4 < pivot ⇒ l += 1
    3. swap a[start] and a[r][-1, 1, 2, 3, 4, 4, 4, 4, 4, 5, 7, 9, 8]
    4. quicksort(a, 7, 8) and quicksort(a, 10, 9)
  1. quicksort(a, 7, 8) → pivot = 4 [-1, 1, 2, 3, 4, 4, 4, 4, 4, 5, 7, 9, 8]
    1. l=8, r=8a[l] = 4 ≥ pivot ⇒ swap a[l] and a[r], r -= 1 [-1, 1, 2, 3, 4, 4, 4, 4, 4, 5, 7, 9, 8]
    2. swap a[start] and a[r][-1, 1, 2, 3, 4, 4, 4, 4, 4, 5, 7, 9, 8]
    3. quicksort(a, 7, 6) and quicksort(a, 8, 8)
  1. quicksort(a, 11, 12) → pivot = 9 [-1, 1, 2, 3, 4, 4, 4, 4, 4, 5, 7, 9, 8]
    1. l=12, r=12a[l] = 8 < pivot ⇒ l += 1
    2. swap a[start] and a[r][-1, 1, 2, 3, 4, 4, 4, 4, 4, 5, 7, 8, 9]
    3. quicksort(a, 11, 11) and quicksort(a, 13, 12)
  1. [-1, 1, 2, 3, 4, 4, 4, 4, 4, 5, 7, 8, 9]
QuickSort ալգորիթմի միջին աշխատաժամանակը է, սակայն pivot-ի ոչ պատշաճ ընտրությունըWorst-case-ում կարող է բերել քառակուսային աշխատանքի։
🤔 Կարո՞ղ եք նշել մի օրինակ, երբ միշտ start-ը որպես pivot ընտրելով՝ ալգորիթմը կաշխատի բարդությամբ:

Առաջադրանք

Տրված է n ամբողջ թվերից կազմված մի ցանկ և q հատ pivot։ Պահանջվում է այնպես փոխադրել (rearrange) ամբողջ ցանկը, որ pivot-ից փոքր բոլոր տարրերը լինեն ձախում, pivot-ից մեծերը՝ աջում, իսկ pivot-ին հավասարները լինեն իրար կողքի՝ փոքրերի ու մեծերի միջև։

Մուտք

Մուտքի առաջին տողում տրված է մեկ ամբողջ թիվ n (1 ≤ n ≤ 100 000):
Հաջորդ տողում տրված է n ամբողջ թվերի ցանկ (), որոնք բաժանված են բացատներով։
Երրորդ տողում տրված է մեկ ամբողջ թիվ q (1 ≤ q ≤ 10):
Հաջորդ տողում տրված է q ամբողջ թվերի ցանկ (1 ≤ ≤ n), որոնք համապատասխանում են pivot տարրի ինդեքսին:

Ելք

Յուրաքանչյուր pivot-ի համար անհրաժեշտ է տպել տեղափոխությունից հետո ստացվող զանգվածը։ Եթե գոյություն ունեն մի քանի հնարավոր պատասխաններ, կարելի է տպել դրանցից որևէ մեկը։

Օրինակներ

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

Constraints

Time limit: 2 seconds

Memory limit: 512 MB

Output limit: 10 MB

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