Проблема с реализацией двунаправленной сортировки - PullRequest
Новая
       30

Проблема с реализацией двунаправленной сортировки

1 голос
/ 19 сентября 2019

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

Я могу получить логику, необходимую для выполнения задачи. Но я думаю, что я делаю что-то не так со сравнением переменных или, возможно, реализую сопоставимые

public void sort(T[] input) {

for(int i=0; i<input.length -1; i++){

    int min = i;
    int max = i;

    for(int j=i+1; j<input.length; j++){

        if(input[min].compareTo((input[j])) > 0  )
        {
            min = j;
            T swap = input[min];
            input[min] = input[i];
            input[i] = swap;

        }
    }

    for(int k=i+1; k<input.length; k++){

        if(input[max].compareTo((input[k])) < 0  )
        {
            max = k;
            T swap = input[max];
            input[max] = input[i];
            input[i] = swap;

        }
    }


}


}

///// Тестовый файл 

   /** Returns true if the input array is ordered (every element ≤ 
    * the following one.)
    * 
    * @param data Array to check
     * @return     True if array is ordered
     */
    boolean isOrdered(Integer[] data) {
    for(int i = 0; i < data.length - 1; ++i)
        if(data[i] > data[i+1])
            return false;

    return true;
}

/** Counts the number of times x occurs in the array in.
 * 
 * @param in Array
 * @param x  Element to count
 * @return   Count of x's in the array
 */
int countElement(Integer[] in, Integer x) {
    int c = 0;
    for(int i : in) 
        if(i == x)
            c++;

    return c;
}

/** Returns true if both arrays contain the same elements, 
 * disregarding order (i.e., is one a permutation of the other).
 * @param in  Unsorted array
 * @param out Potentially-sorted array to check
 * @return    True if out is a permutation of in
 */
boolean sameElements(Integer[] in, Integer[] out) {
    for(Integer i : in)
        if(countElement(in,i) != countElement(out,i))
            return false;

    return true;
}

/** Creates an array of the given size filled with random values.
 * 
 * @param size Size of the resulting array
 * @return     Array of random values
 */
Integer[] randomArray(int size) {
    Integer[] arr = new Integer[size];
    for(int i = 0; i < size; ++i)
        arr[i] = Math.round((float)Math.random() * Integer.MAX_VALUE);

    return arr;
}

/** Tests the DoubleSelectionSort dss against the unsorted data.
 * 
 * @param dss  Sorter to use
 * @param data Array to sort and check
 */
void testSort(DoubleSelectionSort dss, Integer[] data) {
    Integer[] sorted = Arrays.copyOf(data, data.length);
    dss.sort(sorted);        

    assertTrue("Result of sort is not sorted in order", isOrdered(sorted));
    assertTrue("Result of sort has different elements from input", sameElements(data, sorted));
}

@Test
public void testSort() {
    System.out.println("sort");
    DoubleSelectionSort<Integer> dss = new DoubleSelectionSort<>();

    // Test on arrays size 0 to 100
    for(int i = 0; i <= 100; ++i)
        testSort(dss, randomArray(i));               
  }

}

testSort Failed: Результат сортировки не отсортирован по порядку

1 Ответ

0 голосов
/ 19 сентября 2019

Похоже, вы используете неправильные условия в логике сортировки Selection Sort.Я привел здесь пример функции Selection Sort с типом generic.Пожалуйста, посмотрите на это: 

public static <E extends Comparable<E>> void selectionSort(E[] list)
{
    for(int i=0; i<list.length -1; i++)
    {
        int iSmall = i;

        for(int j=i+1; j<list.length; j++)
        {
            if(list[iSmall].compareTo((list[j])) > 0  )
            {
                iSmall = j;
            }
        }
        E iSwap = list[iSmall];
        list[iSmall] = list[i];
        list[i] = iSwap;

    }
}
...