Проблема с модифицированным алгоритмом сортировки пузырьков

Question

Хорошо, я пытаюсь написать алгоритм для сортировки массива, в данном случае массива случайных целых чисел. Я знаю, что QuickSort или подобное, очевидно, более эффективно, но для этого задания я должен в основном сделать модифицированную версию неэффективного алгоритма Bubble Sort.

Идея состоит в том, чтобы сравнить целые числа по пробелу. После каждого прохода предполагается, что зазор должен быть разрезан пополам. Если значение слева больше значения справа, они меняются местами. Предполагается, что выполнение должно продолжаться до тех пор, пока не произойдет обмен или не будет пробел 1. Я обычно довольно схожу с такого рода вещами, но кажется, что я чего-то не хватает. По какой-то причине алгоритм не сортирует мои массивы.

Вот мой код. Может быть, кто-то может увидеть, что я пропускаю:

public class ShellArray 
{ 
    private int capacity; 
    private int [] randArray; 
    private static final int RANGE = 200;    //Range set to 200 for possible integers. 

    public ShellArray(int capacity) 
    { 
     this.capacity = capacity; 
     randArray = new int[capacity]; 
     populate(randArray, RANGE, capacity); 
    } 

    /************************************************************************************************************************************************** 
    // 
    //Populates array with random integers within given range. 
    // 
    ***************************************************************************************************************************************************/ 

    private static void populate(int [] myArray, int numRange, int extent) 
    { 
     Random r = new Random(); 

     for (int i = 0; i < extent; i++) 
      myArray[i] = (r.nextInt(numRange)+1); 
    } 

    /************************************************************************************************************************************************** 
    // 
    //The first version of shellSort calls the second version with min value as 0 and max as length of randArray-1. Takes no parameters. 
    // 
    ***************************************************************************************************************************************************/ 
    public void shellSort() 
    { 
     shellSort(0, randArray.length-1); 
    } 

    /************************************************************************************************************************************************** 
    // 
    // shellSort which takes min and max parameters. Calculates gap at center, across which values are compared. Passes continue until gap size is 1 
    // and array is sorted. 
    // Uses boolean sorted to indicate when array is sorted so passes don't continue needelessly after array is sorted. Essentially, if no values 
    // are swapped after a pass, we know array is sorted and sorted is not set to false. 
    // 
    // Outer for loop controls position of final value. Since largest value is bubbled to end, position decreases by 1 after each pass. 
    // After each pass, size of gap is cut in half, as long as gap is 2 or greater. Otherwise gap would become too small. 
    // Inner for loop controls the index values to be compared. 
    // Uses swap method to swap values which are not in the correct order. 
    // Array is printed after each pass. 
    // 
    ***************************************************************************************************************************************************/ 

    public void shellSort(int min, int max) 
    { 
     String result; 
     int gap; 
     int j = 0; 
     int size = randArray.length-1; 
     boolean swapped; 

     for(gap = size/2; gap <= 0; gap = gap/2) 
     { 
      swapped = true; 

      while (swapped) 
      { 
       swapped = false; 
       int comp; 

       for(comp = 0; comp+gap <= size; comp++) 
       { 
        if (randArray[comp] > randArray[comp+gap]) 
        { 
         swap(comp, comp+gap); 
         swapped = true;  //swapped set to true if any element is swapped with another. 
        } 
        else 
         swapped = false; 
       } 
      } 

      result = ""; 
      for(int y = 0; y < randArray.length; y++) 
      { 
       result += randArray[y] + " "; 
       j++; 
      } 

      System.out.println("Pass " +j+": " +result+"\n"); 
     } 
    } 

    /************************************************************************************************************************************************** 
    // 
    // Swaps two values in the array. 
    // 
    ***************************************************************************************************************************************************/ 

    private void swap(int index1, int index2) 
    { 
     int temp = randArray[index1]; 
     randArray[index1] = randArray[index2]; 
     randArray[index2] = temp; 
    } 

    public String toString() 
    { 
     String result = ""; 

     for(int y = 0; y < randArray.length; y++) 
      result += randArray[y] +" "; 

     return result; 
    } 

} 

Answer 1

Вы не предоставили данные своего задания, но идея-то вдоль этих линий является то, что заключительная стадия (т.е. с gap == 1) является bona fide стандартно сортировать все самостоятельно - в этом случае, я думаю, сортировка пузырьков - и предыдущие этапы предварительно обрабатывают вход, так что эффективность этого окончательного сортирования намного лучше, чем для случайного ввода. По крайней мере, для gap == 1, тогда вы должны повторить цикл сортировки до тех пор, пока не будет свопов.

Есть два основных варианта возможны здесь, и вы не дали нам информацию, чтобы знать, какой вы хотите:

• Первый вариант сокращает разрыв после каждой итерации цикла сортировки, пока он не достигнет 1 , затем повторяется с этим промежутком, пока не будет больше свопов.
• Вторая вариация повторяет цикл сортировки с тем же зазором, пока не будет свопов, затем сжимается щель и повторяется.

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