635
правок
Изменения
→Улучшенная быстрая сортировка
quicksort(a, l, r)
insertion(a, l, r)
===Быстрая сортировка с разделением на три части===
'''void''' quicksort(a: '''int'''[n], '''int''' l, '''int''' r):
'''int''' k
'''int''' v = a[r]
'''if''' (r <= l)
'''return'''
'''int''' i = l
'''int''' j = r - 1
'''int''' p = l - 1
'''int''' q = r
'''while''' true
'''while''' (a[i] < v)
i++
'''while''' (a[j] > v)
j--
'''if''' (i == j)
'''break'''
'''if''' (i >= j)
'''break'''
swap(a[i], a[j])
'''if''' (a[i] == v)
p++
swap(a[p], a[i])
'''if''' (a[j] == v)
q--
swap(a[q], a[j])
swap(a[i], a[r])
j = i - 1
i++
'''for''' (k = 1 ; k <= p; k++, j--)
swap(a[k],a[j])
'''for''' (k = r-1; k >= q; k—, i++)
swap(a[k],a[i])
quicksort(a, 1, j)
quicksort(a, i, r)
==Улучшения==
