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

У меня возникли проблемы с попыткой выяснить, сколько свопов и сравнений для массива int с использованием сортировки выбором в Java. Я смущен тем, где в циклах подсчитываются своп и сравнения. Мы будем очень признательны за любые рекомендации.

    public class IntSelectionSorter {

public static int count = 0;
public static int count2 = 0;

public static void selectionSort(int[] array)
{
    int startScan;
    int index;
    int minIndex;
    int minValue;

    for (startScan = 0; startScan < (array.length - 1); startScan++)
    {
        minIndex = startScan;
        minValue = array[startScan];

        for (index = startScan + 1; index < array.length; index++)
        {
            count2++;
            if (array[index] < minValue)
            {
                minValue = array[index];
                count++;
                minIndex = index;
            }
        }
        array[minIndex] = array[startScan];
        count++;
        array[startScan] = minValue;
        count++;
    }
}

}


java selection-sort
person Nosuchluck    schedule 27.11.2016    source источник
comment
В чем конкретно проблема? Что вы ожидаете от него, и что он делает вместо этого?   -  person Andy Turner    schedule 28.11.2016
comment
Я создаю сортировщик выбора для массива int, который должен подсчитывать количество свопов и сравнений. Я уже создал Bubble Sorter для использования того же массива int. Я не уверен, что использовал своп (количество) и сравнение (количество2) в нужных местах в этом сортировщике выбора. Я получаю ответ из 48 свопов и 300 сравнений. Если я изменю, где я поставлю count и count2, я получу разные ответы. Остальные файлы тоже могу выложить.   -  person Nosuchluck    schedule 28.11.2016

Ответы (2)


arrow_upward
0
arrow_downward

count2 кажется правильным. количество должно быть изменено следующим образом:

for (startScan = 0; startScan < (array.length - 1); startScan++)
{
    minIndex = startScan;
    minValue = array[startScan];

    for (index = startScan + 1; index < array.length; index++)
    {
        count2++;
        if (array[index] < minValue)
        {
            minValue = array[index];
            // count++; delete this
            minIndex = index;
        }
    }
    if (minIndex != startScan) {
        array[minIndex] = array[startScan];
        count++;
        array[startScan] = minValue;
    }
}

в основном, увеличивайте счетчик только тогда, когда есть необходимость поменять местами, т.е. когда в массиве после startScan есть другое число, которое меньше значения при startScan.

person Sourabh    schedule 27.11.2016
comment
Большое спасибо за помощь! Это имеет больше смысла. Однако я получаю 0 свопов и 300 сравнений. Это не кажется правильным. - person Nosuchluck; 28.11.2016
comment
Я провел тест на это, и он дал правильный ответ. Проверен входной массив [2,1,4,3], и он действительно дает 2 свопа (первый для индекса 0, а второй для индекса 2). какой вход вы пытаетесь? - person Sourabh; 28.11.2016

arrow_upward
0
arrow_downward

открытый класс SortingTest {

public static void main(String[] args) 
{
    int[] values = { 1,53,86,21,49,32,90,65,33,11,34,68,54,32,78,80,35,22,96,59,265,44324,123,3123,25435};

    System.out.println("Original Order: ");
    for (int element : values) 
        System.out.print(element + " ");

    IntBubbleSorter.bubbleSort(values);

    System.out.println("\nSorted order: ");
    for (int element : values) 
        System.out.print(element + " ");

    System.out.println();

    System.out.print("\n Bubble Sort Swaps:" + IntBubbleSorter.count);
    System.out.print("\n Bubble Sort Comparisons:" + IntBubbleSorter.count2);

    System.out.println();

    System.out.println("\nOriginal Order: ");
    for (int element : values) 
        System.out.print(element + " ");

    IntSelectionSorter.selectionSort(values);

    System.out.println("\nSorted order: ");
    for (int element : values) 
        System.out.print(element + " ");

    System.out.println();

    System.out.print("\n Selection Sort Swaps:" + IntSelectionSorter.count);
    System.out.print("\n Selection Sort Comparisons:" + IntSelectionSorter.count2);

    System.out.println();

    System.out.println("\nOriginal Order: ");
    for (int element : values) 
        System.out.print(element + " ");

    IntInsertionSorter.insertionSort(values);

    System.out.println("\nSorted order: ");
    for (int element : values) 
        System.out.print(element + " ");

    System.out.println();

    System.out.print("\n Insertion Sort Swaps:" + IntInsertionSorter.count);
    System.out.print("\n Insertion Sort Comparisons:" + IntInsertionSorter.count2);
}

}

person Nosuchluck    schedule 27.11.2016