Почему мои алгоритмы сортировки возвращают одинаковое количество сравнений? - PullRequest
Новая
       33

Почему мои алгоритмы сортировки возвращают одинаковое количество сравнений?

0 голосов
/ 29 апреля 2018

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

Почему мой код продолжает возвращать одинаковые значения сравнения? 

import java.util.Random;

public class AssignmentIV {

public static void main(String[] args) {
    int[] testRuns = new int[4];        //stores the values for the generation of random arrays
    testRuns[0] = 10;
    testRuns[1] = 100;
    testRuns[2] = 1000;
    testRuns[3] = 10000;

    String[] algorithms = new String[3];        //stores the names of the algorithms 
    algorithms[0] = "Selection Sort";
    algorithms[1] = "Enhanced Bubble Sort";
    algorithms[2] = "Insertion Sort";

    int countComparisons;


    for(int i=0; i<3; i++)      //loops through the different algorithms
    {
        System.out.println("SORTING ALGORITHM: " + algorithms[i] + "\n");

        for(int j=0; j<4; j++)      //loops through different amounts (10, 100, 1000, 10000) of values for each algorithm
        {
            countComparisons = 0;

            int[] test = Generate(testRuns[j]);     //creates an array filled with random values

            if(algorithms[i] == "Selection Sort")
                countComparisons = selectionSort(test);             //calls the selection sort method
            else if(algorithms[i] == "Enhanced Bubble Sort")
                countComparisons = enhancedBubbleSort(test);        //calls the enhanced bubble sort method
            else if(algorithms[i] == "Insertion Sort")
                countComparisons = insertionSort(test);             //calls the insertion sort method

            System.out.println("Number of values in array: " + testRuns[j]);            //prints the number of values in the array
            System.out.println("Number of comparisons required: " + countComparisons + "\n");           //prints the number of comparisons required to sort the array
        }
    }
}


//method to populate an array with randomized integers
public static int[] Generate(int size)
{
    int[] valueArray = new int[size]; 


    //number generator is created
    Random gen = new Random();

    //each position in an array is filled with a random
    //integer up to maximum Integer.MAX_VALUE
    for(int i=0; i<size; i++)
    {
        valueArray[i] = gen.nextInt(Integer.MAX_VALUE);
    }
    return valueArray;
}

//sorts an array using selection sort and returns the number of comparisons made
public static int selectionSort(int[] arr)
{
    int count = 0;
    int min, min_location;

    for(int i=0; i < arr.length-1; i++)
    {
        min = arr[i];
        min_location = i;
        for(int j=i+1; j < arr.length; j++)
        {
            if(arr[j] < min)
            {
                min = j;
                min_location = j;
            }
            count++;
        }

        arr[min_location] = arr[i];
        arr[i] = min;
    }
    return count;
}

//sorts an array using enhanced bubble sort and returns the number of comparisons made
public static int enhancedBubbleSort(int[] arr)
{
    int count = 0;

    for(int i=0; i < arr.length-1; i++)
    {
        for(int j=0; j < arr.length-i-1; j++)
        {
            if(arr[j] > arr[j+1])
            {
                int temp = arr[j];
                arr[j] = arr[j+1];
                arr[j+1] = temp;
            }
            count++;
        }
    }

    return count;
}

//sorts an array using insertion sort and returns the number of comparisons made
public static int insertionSort(int[] arr)
{
    int count = 0;

    for(int i=1; i < arr.length; i++)
    {
        for(int j=i; j>0; j--)
        {
            if(arr[j] < arr[j-1])
            {
                int temp = arr[j];
                arr[j] = arr[j-1];
                arr[j-1] = temp;
            }
            count++;
        }
    }

    return count;
}
}

Вот вывод: 

SORTING ALGORITHM: Selection Sort

Number of values in array: 10
Number of comparisons required: 45

Number of values in array: 100
Number of comparisons required: 4950

Number of values in array: 1000
Number of comparisons required: 499500

Number of values in array: 10000
Number of comparisons required: 49995000

SORTING ALGORITHM: Enhanced Bubble Sort

Number of values in array: 10
Number of comparisons required: 45

Number of values in array: 100
Number of comparisons required: 4950

Number of values in array: 1000
Number of comparisons required: 499500

Number of values in array: 10000
Number of comparisons required: 49995000

SORTING ALGORITHM: Insertion Sort

Number of values in array: 10
Number of comparisons required: 45

Number of values in array: 100
Number of comparisons required: 4950

Number of values in array: 1000
Number of comparisons required: 499500

Number of values in array: 10000
Number of comparisons required: 49995000

1 Ответ

0 голосов
/ 29 апреля 2018

Количество сравнений в этих алгоритмах не зависит от значений данных. Вы должны ожидать постоянных отсчетов.

Чтобы увидеть это, обратите внимание, что если вы увеличиваете количество, то оно не входит в оператор "если". Это просто подсчет проходов через циклы, которые управляют операцией сортировки.

...