Что не так с моим двоичным кодом вставки?

Question

Я новичок в Java пытается создать класс, который реализует бинарную вставки рода и сортирует случайные массивы данных размером 50, 500, 5000, 50000 и 500000.

Программа отлично работает, когда я реализовывал это как сортировка вставки.

public double InsertionSort(long array[]) { 
      setType("Insertion Sort"); 
      long temp; 
      int y; 
      double numOfSwap = 0, numOfComparisons = 0; 
      double startTime = System.nanoTime(); 
      for (int x = 1; x < array.length; x++) { 
       temp = array[x]; 
       numOfSwap++; 
       y = x; 
       numOfComparisons++; 
       while ((y > 0)) { 
        numOfComparisons++; 
        if ((array[y - 1]) > temp) { 
         array[y] = array[y - 1]; 
         numOfSwap++; 
         y = y - 1; 
        } else 
         break; 
       } 
       array[y] = temp; 
       numOfSwap++; 
      } 
      double endTime = System.nanoTime(); 
      setSwap(numOfSwap/3); 
      setComparisons(numOfComparisons); 
      setTime(endTime - startTime); 
      return getTime(); 

     } 

Но когда я попытался вставить двоичный поиск, он больше не работал.

public double binaryInsertionSort(long array[], int value, int left, int right) { 
      setType("Binary Insertion Sort"); 
      long temp; 
      int y; 
      int left, right; 
      double numOfSwap = 0, numOfComparisons = 0; 
      double startTime = System.nanoTime(); 
      for (int x = 1; x < array.length; x++) { 
       temp = array[x]; 
       numOfSwqp++; 
       int left = y; 
       int right = x; 
       if (left>right) 
        return -1; 
       int middle = (left + right)/2; 
       if (array[middle] == value) 
        return middle; 
       numOfComparisons++; 
       else if (array[middle]>value) 
        return binaryInsertionSort(array, value,left, middle -1); 
       numOfComparisons++; 
       else 
        return binaryInsertionSort (array, value, middle +1, right); 
       numOfComparisons++; 
      } 
      double endTime = System.nanoTime(); 
      setSwap(numOfSwap/3); 
      setComparisons(numOfComparisons); 
      setTime(endTime - startTime); 
      return getTime(); 
     } 

Может кто-нибудь помочь мне исправить мой код?

Answer 1

Были ошибки в коде. Я исправил их. Прежде всего, ваши left и right переменные определены в этой строке: -

public double binaryInsertionSort(long array[], int value, int left, int right) 

почему вы снова их определения в теле метода. Поэтому я удалил их двойное объявление. Во-вторых, вы присвоили значение left переменной до y, что было неправильно. На самом деле вам нужно назначить значение y to влево. Третья ошибка в вашем коде была неправильной. Вы определили binaryInsertionSort с четырьмя параметрами, и вы вызывали его по одному параметру, поэтому я изменил ваши вызовы метода следующим образом: -

sortTime = binaryInsertionSort (sortedArray, 10,20,30);

Отдых были незначительными ошибками. Вот Corect код вашего `метода binaryInsertionSort: -

public double binaryInsertionSort(long array[], int value, int left, int right) { 

setType("Binary Insertion Sort"); 

long temp; 

int y=0; 

//int left, right; 

double numOfSwap = 0, numOfComparisons = 0; 

double startTime = System.nanoTime(); 

for (int x = 1; x < array.length; x++) { 

temp = array[x]; 

numOfSwap++; 

y=left; 

right = x; 

if (left>right){ 
return -1; 
} 

int middle = (left + right)/2; 

if (array[middle] == value){ 

    numOfComparisons++; 
    return middle; 

} else if (array[middle]>value){ 

    numOfComparisons++; 
    return binaryInsertionSort(array, value,left, middle -1); 

} else{ 

    numOfComparisons++;  
    return binaryInsertionSort (array, value, middle +1, right); 
    } 

} 

double endTime = System.nanoTime(); 

setSwap(numOfSwap/3); 

setComparisons(numOfComparisons); 

setTime(endTime - startTime); 

return getTime(); 

} 
` 

Я отправил вам заполнить исправленный код вашей программы. Проверьте свой почтовый ящик. Подтвердите, полезен ли вам мой ответ или нет. Happy Coding :)

Answer 2

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

Кроме того, есть некоторые различные странности в вашем коде:

• это нетипично и не выгодно реализовать любой вариант вставки сортировки рекурсивно.

• Ваша конкретная попытка рекурсивной реализации в любом случае не имеет смысла: основной цикл будет запускать только одну итерацию, а код после цикла будет мертв.

• Трудно быть уверенным, но я думаю, что у вас есть идея создания двоичной вставки. Кажется, вы пытаетесь разделить массив на части, чтобы отсортировать их рекурсивно, например сортировку слияния или быстрый сортировку, но это не так, как работает сортировка двоичных вставок. Сортировка двоичной вставки отличается от стандартной сортировки вставки главным образом тем, что вместо поиска в линейном поиске используется двоичный поиск, чтобы найти позицию вставки для каждого элемента.