Տեսակավորման (sorting) ամենահայտնի ալգորիթմներից մեկը QuickSort-ն է։ Սա «բաժանիր և տիրիր» (divide-and-conquer) սկզբունքով աշխատող ալգորիթմ է, որը յուրաքանչյուր քայլում զանգվածից ընտրում է pivot անունով տարր, այնուհետև զանգվածը բաժանում է pivot-ից փոքր, pivot-ին հավասար և pivot-ից մեծ տարրերի, հետո նույն գործընթացը շարունակում է յուրաքանչյուր մասի վրա, մինչև ամբողջ զանգվածը տեսակավորված լինի։
Այսինքն, յուրաքանչյուր իտերացիայի ընթացքում․
Զանգվածից ընտրում ենք pivot տարրը
pivot-ից փոքր տարրերը տեղափոխում ենք ձախ մաս
pivot-ից մեծ տարրերը տեղափոխում ենք աջ մաս
pivot-ին հավասար բոլոր տարրերը հավաքում ենք մեջտեղում
Ստացված ձախ և աջ մասերի վրա կրկնում ենք նույն գործընթացը
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 ընտրելու համար․
Առաջին տարրը: a[start] (ինչպես երևում է երկրորդ իրականացման մեջ)
Վերջին տարրը: a[end]
Միջին տարրը: a[(start + end + 1) // 2]
Պատահական տարրը: կարելի է վերցնել a[start ... end] միջակայքից ցանկացած էլեմենտ
Միջին (median) տարրը: ընտրել ընթացիկ հատվածի միջինը (ինչը հավասարակշռված բաժանում է ապահովում), սակայն պահանջում է ավելի բարդ իրականացում
Եկեք ցուցադրական օրինակներով տեսնենք, թե ինչպես է ալգորիթմը գործում մի քանի զանգվածների վրա.
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-ի համար անհրաժեշտ է տպել տեղափոխությունից հետո ստացվող զանգվածը։ Եթե գոյություն ունեն մի քանի հնարավոր պատասխաններ, կարելի է տպել դրանցից որևէ մեկը։