Thursday, May 23, 2019

Go: Quick Sort-ի ևս մի ներկայացում

Կարգավորման ալգորիթմներից գեղեցկագույնի՝ 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 ֆունկցիան։