Интервал Shellsort Вопрос Java - PullRequest
Новая
       20

Интервал Shellsort Вопрос Java

0 голосов
/ 04 мая 2011

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

Это моя сортировка Shellsort, когда h равен стандартному размеру интервала: 

    public void shellSort() 
    {
    int inner, outer;
    int temp;
    int h = 1;

    while (h <= length / 3)
    {
      h = h * 3 + 1; 
    }

    while (h > 0) 
    {

      for (outer = h; outer < length; outer++) 
      {
        temp = data[outer];
        inner = outer;

        while (inner > h - 1 && data[inner - h] >= temp) 
        {
          data[inner] = data[inner - h];
          inner -= h;
        }
        data[inner] = temp;
      }

      h = (h - 1) / 3; 

    }

  }

А вот моя попытка использовать интервал простых чисел 

      private int[]  primes = {0, 1, 3, 7, 13, 31, 97, 211, 503, 1013, 2503, 5171};
      public void shellSort() 
      {
        int inner, outer;
        int temp;
        int count = this.h.length - 1;
        int h = 1;

        h = primes[primes.length - 1] * 2 > length ? primes[primes.length - 1] : primes[primes.length - 2];

        while (h > 0) 
        {         
          for (outer = h; outer < length; outer++) 
          {
            temp = data[outer];
            inner = outer;

            while (inner > h - 1 && data[inner - h] >= temp) 
            {
              data[inner] = data[inner - h];
              inner -= h;
            }
            data[inner] = temp;
          }

          if(count - 1 > 0)           
              h = primes[count - 1];              

        }

      }

Я пытаюсь сравнить два, основанные на эффективности в реальном времени, и я не могу понять, как заставить этот интервал между циклами работать.

Я пытаюсь проверить:

  • Shellsort работает лучше, чем O (N ^ 2) с правильно выбранными размерами интервалов
  • Выбранная серия размеров интервалов важна для достижения лучшего, чем O (N ^ 2) времени выполнения

Спасибо за любую помощь.

1 Ответ

0 голосов
/ 06 мая 2011

Вы, вероятно, хотите уменьшить значение count в каждой итерации внешнего цикла. В вашем коде оно все еще равно this.h.length-1, что равно 11. Поэтому после каждой итерации внешнего цикла вы выполняете условие if count-1 > 0, поэтому вы устанавливаете h = this.h[count-1], который, как я считаю, равен 2503. Итак, Вы повторно входите в цикл.

Кстати, вызов списка размеров интервалов h серьезно ухудшает читабельность. Вы должны назвать это как минимум hs.

...