Tcl: QuickSort ալգորիթմի մասին

Անկեղ ասած, ես երբեք էլ չեմ հասկացել այս QuickSort կարգավորման ալգորիթմի էությունը։ Մինչև այն պահը, երբ «Learn You a Haskell for Great Good!» գրքում կարդացի այդ ալգորիթմի իրականացումը։ Ահա այն․

quicksort :: (Ord a) => [a] -> [a]  
quicksort [] = []  
quicksort (x:xs) =   
    let smallerSorted = quicksort [a | a <- xs, a <= x]  
        biggerSorted = quicksort [a | a <- xs, a > x]  
    in  smallerSorted ++ [x] ++ biggerSorted  

Մոտավորապես նույն ալգորիթմը կարելի է գրել նաև Tcl լեզվով։ Այստեղ ընտրվում է ցուցակի առաջին տարրը՝ H, ապա foreach ցիկլով ցուցակի մյուս տարրերը տրոհվում են երկու խմբի՝ H-ից մեծ, և H-ից փոքր կամ հավասար։ Այնուհետև ռեկուրսիվ եղանակով կարգավորվում են տրոհված խմբերն ու վերջում միավորվում իրար։

proc quickSort { elems } {
  # եթե ցուցակը դատարկ է, ապա կարգավորելու բան չկա
  if {0 == [llength $elems]} { return {} }
  set L [list]
  set G [list]
  # ընտրել ցուցակի առաջին տարրը
  set H [lindex $elems 0]
  # տրոհել մյուս տարրերը երկու խմբի
  foreach e [lrange $elems 1 end] {
    if {[expr $e < $H]} { lappend L $e } { lappend G $e }
  }
  # կարգավորել երկու խմբերը և միավորել որպես արդյունք
  return [concat [quickSort $L] $H [quickSort $G]]
}