Sunday 15 March 2015

Quicksort partitions

Зарубился я тут в сортировки. И даже отгреб от этого головную боль.

После того как написал Ламуто стало ясно, что он безбожно медленный. Решил проверить насколько. Вот оригинал:

Видно, что он плохо себя ведет на отсортированном массиве, постоянно вызывает swap на один и тот же индекс. Улучшим:

А теперь сравним с Хоаром:
А теперь глянем на время работы. Первый параметр размер проверяемого массива, второй seed для генератора случайного массива:
Вот так вот. То ли Ламуто - ламото, то ли я ламото  -- криво заимплементил %)

No comments:

Post a Comment