Comments 14
Первые алгоритмы хоть как то сортируют, а «разумный замысел» — выше человеческого понимания -) Надо было назвать «Божественным замыслом»
Кто не понял алгоритм, вот вам реализацияВ этом месте под спойлером я ожидал увидеть brainfuck=)
А «Джаред Даймонд» это разве не обычный sleepsort?
Если, как написано в тексте, использовать массив, то сложность Dropsort, вроде, O(n*n). А вот если двусвязный список, то тогда действительно O(n).
Вообще-то да, при каждом сбросе из массива сдвиг оставшихся элементов влево приводит к итоговому O(n2).
Конечно же, так выгодно обрабатывать список, а не массив.
Конечно же, так выгодно обрабатывать список, а не массив.
Да не, вроде можно и за O(n) на массиве. Если хранить 2 указателя: на текущий элемент и на последний «проверенный и не удалённый» и проверяя их между собой на каждому шаге. В конце надо будет только создать новый массив и скопировать туда все оставшиеся элементы, но это всё равно O(n).
Ну да, если не in-place, то вроде можно за O(n). Согласен.
in-place:
#include <iostream>
#include <ctime>
#include <cstdlib>
int main()
{
int n = 10;
int* a = new int[n];
std::srand(std::time(NULL));
for (int i = 0; i < n; i++) {
a[i] = std::rand() % 10;
std::cout << a[i] << " ";
}
std::cout << std::endl;
// dropsort
int j = 0;
for (int i = 1; i < n; i++) {
if (a[i] >= a[j]) {
j++;
if (j < i)
a[j] = a[i];
}
}
n = j + 1;
// end of dropsort
for (int i = 0; i < n; i++)
std::cout << a[i] << " ";
std::cout << std::endl;
return 0;
}
Спасибо, интересно.
Очень понравился Dropsort:)
Очень понравился Dropsort:)
Sign up to leave a comment.
Эзотерические сортировки Дэвида Морган-Мара