Идентификация скоплений (сегментов) данных для реализации сортировки скоплений - PullRequest
Новая
       15

Идентификация скоплений (сегментов) данных для реализации сортировки скоплений

2 голосов
/ 28 ноября 2010

Я ищу реализацию Clump Sort на любом языке или его псевдокод. Оригинальная исследовательская работа не содержит никаких. Поскольку я не могу найти какое-либо существующее решение (в основном из-за того, что этот метод довольно новый), я решил реализовать его самостоятельно. Итак, в качестве первого шага мне нужно идентифицировать скопления данных в нашем числовом вводе. Я понимаю, что это может пойти в сторону искусственного интеллекта, но я готов к этому, так как я все равно знаю основы.

Итак, есть идеи о том, как идентифицировать скопления данных, ребята? А пока я хочу сосредоточиться на скоплениях чисел, которые поднимаются или опускаются.

Например:
3, 7, 10, 56, 4, 1, 3, 34
имеет 3 комка в порядке следования:
3, 7, 10, 56
4
1, 3, 34

У меня вопрос, как это сделать программно?

(Сортировка комков: http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=5489222)

Спасибо!

UPDATE:

Хорошо, потратив некоторое время, я нашел решение, но понятия не имею, было ли то же самое в уме автора статьи. Если бы это было так, мы, вероятно, добавили к сложности сортировки кучи вместо того, чтобы минимизировать ее. 

int[] input = { 30, 7, 10, 56, 4, 1, 3, 34 };
List<ClumpStartEnd> clumps = new List<ClumpStartEnd>();
public void ClumpIdentifier(int start)
{
    for (int i = start + 1; i < input.Length + 1; i++)
    {
        if (i == input.Length || input[i] < input[i - 1])
        {
            clumps.Add(new ClumpStartEnd(start, i - 1));
            ClumpIdentifier(i);
            break;
        }
    }
}

1 Ответ

0 голосов
/ 02 сентября 2011

Я согласен, что Тимсорт будет лучшим выбором, но я впервые обнаружил это вскоре после того, как статья была представлена;извините за это.

Оценка алгоритма ФП не имеет смысла.Каждый раз, когда Clump встречает инверсию, он чередуется между ожиданием восходящего и нисходящего порядка.Таким образом, 3, 7, 10, 56, 4, 1, 3, 34 - это восходящий цикл 3, 7, 10, 56, затем инверсия начинает нисходящий цикл 4, 1, затем инверсия этого порядка начинает восходящий цикл.3, 34.

...