Կարգավորման ալգորիթմներից գեղեցկագույնի՝ QuickSort-ի մասին գրված է ծրագրավորման ալգորիթմներին վերաբերող համարյա բոլոր գրքերում։ Բայց արժե առանձնացնել հատկապես Robert Sedgewick, Kevin Wayne, «Algorithms, 4th Edition» գրքի իլյուստրացիան, որից օգտվելով էլ (ինչպես նաև Go լեզվի sort փաթեթի կոդից) կառուցել եմ ստորև բերվող իրականացումը։ Սակայն իմ նպատակը QuickSort-ի վերլուծությունը չէ. ես ուզում եմ դրա օրինակով ներկայացնել, թե ինչպես կարելի է Go լեզվով իրականացնել ընդհանրացված (generic) ալգորիթմ։
Սկսեմ պարզ դեպքից։ Ենթադրենք գրել եմ quick
փաթեթը, որի Sort
ֆունկցիան կարգավորում է ամբողջ թվերի զանգվածը.
package quick // Sort ֆունկցիան կարգավորում է ամբողջ թվերի տրված զանգվածը func Sort(arr []int) { quickSort(arr, 0, len(arr)-1) } func quickSort(arr []int, low, high int) { if low < high { m := partition(arr, low, high) quickSort(arr, low, m-1) quickSort(arr, m+1, high) } } func partition(arr []int, low, high int) int { p := low i, j := low+1, high for { for i != high && arr[i] < arr[p] { i++ } for arr[p] < arr[j] { j-- } if i >= j { break } arr[i], arr[j] = arr[j], arr[i] } arr[p], arr[j] = arr[j], arr[p] return j }
Իմ նպատակն է նույն այս իրականացումն օգտագործել int
-երից բացի այլ տիպերի համար։ Այսինքն՝ Sort
ֆունկցիան պետք է սահմանել այնպիսի պարամետրով, որ հնարավոր լինի այն կիրառել կամայական տիպի տարրերի զանգվածի նկատմամբ։ Ուշադիր նայելով []int
տիպի համար իրականացմանը, տեսնում եմ, որ զանգվածի հետ կատարվում են երեք գործողություններ. ա) ստանալ զանգվածի չափը՝ len(arr)
, բ) համեմատել զանգվածի տարրերը՝ arr[i] < arr[p]
, գ) մեկը մյուսով փոխարինել զանգվածի տարրերը՝ arr[i], arr[j] = arr[j], arr[i]
։ Սահմանեմ (quick
փաթեթում) Sortable
ինտերֆեյսը՝ այս երեք գործողություններտ ներկայացնող մեթոդներով.
package quick // Sortable ինտերֆեյսով որոշվում է «կարգավորելի» զանգվածը type Sortable interface { Size() int // զանգվածի չափը Less(i, j int) bool // a[i] < a[j] համեմատումը Swap(i, j int) // a[i] <-> a[j] փոխատեղումը }
Հիմա արդեն կարող եմ հերթով ձևափոխել Sort
, quickSort
և `partition` ֆունկցիաները։ Առաջինում պետք է փոխել պարամետրի տիպը և len(arr)
-ը փոխարինել arr.Size()
-ով։
// Sort ֆունկցիան կարգավորում է ամբողջ թվերի տրված զանգվածը func Sort(arr Sortable) { quickSort(arr, 0, arr.Size()-1) }
Պարզվում է, որ quickSort
ֆունկցիայում փոխելու բան չկա։
partition
ֆունկցիայում տարրերի համեմատությունները պետք է փոխարինել Less
մեթոդի կիրառությամբ, իսկ տարրերի փոխատեղման վերագրումները՝ Swap
մեթոդի կիրառությամբ։
func partition(arr Sortable, low, high int) int { pv := low i, j := low+1, high for { for i != high && arr.Less(i, pv) { i++ } for arr.Less(pv, j) { j-- } if i >= j { break } arr.Swap(i, j) } arr.Swap(pv, j) return j }
Պատրաստ է։ Հիմա տեսնենք, թե ինչպես է այս նոր իրականացումն օգտագործվելու։ Սկսենք արդեն աշխատող տարբերակից. ենթադրենք ուզում եմ կարգավորել int
-երի զանգված։ Պետք է իրականացնեմ Sortable
ինտերֆեյսը.
type integers []int func (a integers) Size() int { return len(a) } func (a integers) Less(i, j int) bool { return a[i] < a[j] } func (a integers) Swap(i, j) { a[i], a[j] = a[j], a[i] }
Հետո արդեն կարող եմ Sort
ֆունկցիան կիրառել `integers` զանգվածի նկատմամբ։
// ... a0 := integers{4, 1, 9, 2, 3, 8, 5, 6} quick.Sort(a0) fmt.Println(a0) // ...
Հարց։ Եթե մի որևէ ֆունկցիա վերադարձնում է[]int
զանգված, ապա դրա արդյունքի վրա ո՞նց է կիրառվելուSort
ֆունկցիան։