1.2. Implement bogo sort algorithm for an array of integers. (WARNING: you should not implement destroy the universe step). Test it by sorting the following array: [4242, 42, -42, 31415].
получился вот такой код:
module Utils {
static public print_array(arr: array[int]): void {
for (mutable i = 0; i < arr.Length; ++i)
System.Console.WriteLine("{0}", arr[i]);
}
}
module BogoSort {
static public sort(arr: array[int]): void {
def r = System.Random();
mutable idx = array(arr.Length);
mutable test_arr = array(arr.Length);
def do_sort(): void {
def is_sorted(arr: array[int]): bool {
def check_is_sorted(arr: array[int], len: int): bool {
if (len < 2)
true
else
arr[len - 2] <= arr[len - 1] && check_is_sorted(arr, len - 1)
}
check_is_sorted(arr, arr.Length)
}
for (mutable i = 0; i < arr.Length; ++i) {
def new_unique_indexes(): void {
idx[i] = r.Next(arr.Length);
for (mutable j = 0; j < i; ++j)
when (idx[i] == idx[j])
new_unique_indexes();
}
new_unique_indexes();
test_arr[i] = arr[idx[i]];
}
if (!is_sorted(test_arr)) {
// System.Console.WriteLine("array not sorted, run do_sort again");
// Utils.print_array(test_arr);
do_sort();
} else {
//System.Console.WriteLine("array sorted, we do it!!!");
// Utils.print_array(test_arr);
}
for (mutable i = 0; i < arr.Length; ++i)
arr[i] = test_arr[i];
}
do_sort();
}
}
module BogoSortTester {
static public Main(): void {
def arr = array[4242, 42, -42, 31415];
System.Console.WriteLine("Input:");
Utils.print_array(arr);
BogoSort.sort(arr);
System.Console.WriteLine("Output:");
Utils.print_array(arr);
}
}
почему-то уверен, что имея больший опыт в Nemrle, можно написать короче,
не могли бы вы подсказать как именно можно это сделать?
Здравствуйте, Аноним, Вы писали:
А>Изучаю nemerle(кстати как оно произноситься?), А>делаю упражнение отсюда:
А>http://nemerle.org/Grok_Base_structure_of_programs
А>1.2. Implement bogo sort algorithm for an array of integers. (WARNING: you should not implement destroy the universe step). Test it by sorting the following array: [4242, 42, -42, 31415].
А>получился вот такой код:
[skipped]
Во-первых случайную перестановку можно генерировать за O(n) и намного проще, например так:
for (mutable i = n - 1; i > 0; --i)
arr[i] <-> arr[r.Next (i + 1)];
А во-вторых рекурсия как-то неаккуратно используется, надо хотя бы так:
if (!is_sorted(test_arr)) {
// System.Console.WriteLine("array not sorted, run do_sort again");
// Utils.print_array(test_arr);
do_sort();
} else {
//System.Console.WriteLine("array sorted, we do it!!!");
// Utils.print_array(test_arr);for (mutable i = 0; i < arr.Length; ++i)
arr[i] = test_arr[i];
}
И та же ошибка (выполнение ненужных действий) была при генерации случайной перестановки.
Здравствуйте, Аноним, Вы писали:
А>почему-то уверен, что имея больший опыт в Nemrle, можно написать короче, А>не могли бы вы подсказать как именно можно это сделать?
Например так:
using System;
using Nemerle.Utility;
module BogoSort
{
public BogoSort[T](this arr : array[T]) : void where T : IComparable
{
def is_sorted()
{
foreach(i in [1..arr.Length-1])
when (arr[i].CompareTo(arr[i-1]) < 0) Nemerle.Imperative.Return(false);
true// slightly shorter variant
// mutable m = arr[0];
// arr.ForAll(x => { def r = x.CompareTo(m) >= 0; m = x; r })
}
def r = Random();
while(!is_sorted())
foreach(i in [0..arr.Length-1])
arr[i] <-> arr[r.Next(arr.Length)];
}
}
module BogoSortTest
{
Main() : void
{
def r = array[4242, 42, -42, 31415];
Console.WriteLine($"Input: $(arr.ToList())");
arr.BogoSort();
Console.WriteLine($"Output: $(arr.ToList())");
}
}
А>(кстати как оно произносится?),
So how do you pronounce "Nemerle"? Does it rhyme with "M-perl"?
Actually it is not clear. We would have to ask Ursula Le Guin Most English-speaking people pronounce it like that. We, in Poland, tend to accent the last syllabe and pronounce the last e --Malekith 11:01, 1 Oct 2005 (CEST)
Здравствуйте, Vermicious Knid, Вы писали:
[skipped]
VK> // slightly shorter variant
VK> // mutable m = arr[0];
VK> // arr.ForAll(x => { def r = x.CompareTo(m) >= 0; m = x; r })
Кстати, небольшой офф по поводу ForAll, Exists, Map и т.п., то что они применяются в прямом порядке не следует из названия.
А например для ForAll это критично, думаю стоит придумать эти именам синонимы для чёрных дел ForAllForward, LeftmostExists или как-то еще.
Здравствуйте, VladD2, Вы писали:
VD>Надо бы все же добавить макрос for (min <= i < max) ... VD>Тогда можно будет подобные кострукции прописывать более выразительно: VD>
VD>for (1 <= i < arr.Length)
VD> when (arr[i].CompareTo(arr[i - 1]) < 0)
VD> return false;
VD>
+1, отрезки без правой границы часто более удобны, "[a,m), [m,b)" намного лучше чем "[a,m-1], [m,b-1]"
Здравствуйте, VladD2, Вы писали:
VD>Здравствуйте, Иванков Дмитрий, Вы писали:
ИД>>+1, отрезки без правой границы часто более удобны, "[a,m), [m,b)" намного лучше чем "[a,m-1], [m,b-1]"
VD>В немерле нельзя использовать не парные скобки.
Ага, поэтому когда была мысль реализовать, смотрел в сторону какого-нибудь суффикса или префикса для интервала, или же другого имени макроса.
Но "0 <= i < n" вполне подходит
Здравствуйте, Алексей П, Вы писали:
АП>Здравствуйте, VladD2, Вы писали:
VD>>Надо бы все же добавить макрос for (min <= i < max) ...
АП>Уже предлагал и давно сделал. АП>Расширения библиотеки макросов
Most English-speaking people pronounce it like that. We, in Poland, tend to accent the last syllabe and pronounce the last e --Malekith 11:01, 1 Oct 2005 (CEST)
ForAllForward, LeftmostExists или как-то еще.
