Python

Разработку сортировки я начал с тестирующего кода, чтобы уже имея на руках проверочный код, постепенно добавлять нужную функциональность.

В записи между 3:36 и 5:36 пауза, мне нужно было отойти от комьютера, поэтому там экран статичен.

А ещё заметил, что из-за того, что пишу этот код сразу на двух языках, то немного путаюсь. Например, попытался вставить в питоновском коде else if, вместо elif.

Полный исходник:

#!/usr/bin/env python
# -*- coding: utf-8 -*-


import random


def counting_sort(data, min_number, max_number):
    n = max_number - min_number + 1  # [0, n]
    counters = [0] * n

    for v in data:
        counters[v - min_number] += 1

    result = []
    for v, count in enumerate(counters):
        result.extend([v + min_number] * count)

    return result


def create_test_data(size):
    min_number = random.randint(-10, 10)
    max_number = random.randint(min_number + 1, 15)
    data = [random.randint(min_number, max_number) for _ in range(size)]
    return data, min_number, max_number


def main():
    for size in range(10):
        data, min_number, max_number = create_test_data(size)
        sorted_by_counting_sort = counting_sort(data, min_number, max_number)
        sorted_by_sorted = sorted(data)
        if sorted_by_counting_sort != sorted_by_sorted:
            print('Error!')
            print('Test data:     {}'.format(data))
            print('Counting sort: {}'.format(sorted_by_counting_sort))
            print('Sorted:        {}'.format(sorted_by_sorted))
            break
        elif size < 15:
            print('Ok for size {}'.format(size))
            print('Test data:     {}'.format(data))
            print('Counting sort: {}'.format(sorted_by_counting_sort))
            print()
    else:
        print('Ok!')


if __name__ == '__main__':
    main()

OCaml

Потом была очередь разработки алгоритма на OCaml. Здесь я решил, что не честно ждать от фукнции генерации тестовых данных, чтобы она возвращала минимальный и максимальный элементы. Поэтому поиск этих элементов вынес в саму функцию сортировки подсчётом. Таким образом должно было получиться O(3*n), то есть O(n).

Попытка записать и загрузить процесс разработки закончилась ошибкой:

~ Upload failed: Sorry, your asciicast is too big.
~ Retry later by running: asciinema upload ./tmp9e2k0bwd-asciinema.json

Поэтому просто исходник:

open Core.Std


let counting_sort = function
    | [] -> []
    | data -> (
        let min_elt = match List.min_elt data compare with
        | Some i -> i
        | None -> assert false
        in
        let max_elt = match List.max_elt data compare with
        | Some i -> i
        | None -> assert false
        in
        let n = max_elt - min_elt + 1 in
        let counters = Array.create n 0 in

        let rec count = function
        | [] -> ()
        | h :: tl -> (
            counters.(h - min_elt) <- (counters.(h - min_elt) + 1);
            count tl;
        )
        in

        count data;

        Array.foldi counters ~init:[] ~f:(fun i accum v -> accum @ Array.to_list (Array.create v (i + min_elt)))
    )


let rec create_test_data = function
    | 0 -> []
    | size -> (Random.int 10) - 5 :: create_test_data (size - 1)


let () =
    for i = 0 to 10 do
        let data = create_test_data i in
        let sorted_by_count = counting_sort data in
        let sorted_by_std = List.sort data ~cmp:compare in
        if sorted_by_count <> sorted_by_std then
            (
                printf "Error\n";
                data |> List.to_string ~f:string_of_int |> printf "Data: %s\n";
                sorted_by_count |> List.to_string ~f:string_of_int |> printf "Count: %s\n";
                sorted_by_std |> List.to_string ~f:string_of_int |> printf "Std: %s\n\n";
            )
        else
            (
                printf "Ok\n";
                data |> List.to_string ~f:string_of_int |> printf "Data:  %s\n";
                sorted_by_count |> List.to_string ~f:string_of_int |> printf "Count: %s\n";
                sorted_by_std |> List.to_string ~f:string_of_int |> printf "Std:   %s\n\n";
            )
    done

Заключение

Программировать на OCaml мне по-прежнему сложно. Жаль, что запись не сохранилась. Её большой размер обусловлен постоянными переключенями между vim и utop, где я смотрел сигнатуры функций и писал простой тестовый код.

Ещё я понял, что тестирующий код лучше помещять в рекурсивную функцию (с хвостовой рекурсией), если нужно прерывать тест после нахождения ошибки, так как в OCaml нет break, чтобы прервать выполнение цикла.