Подсчет количества свопов и сравнений: выбор сортировки

Question

Я пытаюсь подсчитать количество перестановок и сравнений, которые выполняет мой алгоритм сортировки выбора. CountSwaps является глобальной переменной.

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

 public static void SelectionSort(int[] Array) // descending order
    {
        int countComps = 0;
        int max;
        Stopwatch timer = new Stopwatch();
        timer.Start();
        for (int i = 0; i <= Array.Length - 1; i++) // go through the list
        {
            countComps++;
            max = i; // maximum equals the current position in list
            for (int j = i + 1; j < Array.Length; j++)
            {
                if (Array[j] > Array[max])
                    max = j; // max equals biggest in list j
            }
            countSwaps = 0;
            swap(Array, i, max); 
            countSwaps++;
        }           
        Console.WriteLine("Array after Basic Selection Sort");
        Display(Array);
        timer.Stop();
        Console.WriteLine("Time Taken for Basic Selection Sort is {0} milliseconds", timer.ElapsedMilliseconds);
        Console.WriteLine("The number of swaps is : {0} ", countSwaps);
        Console.WriteLine("The number of comparisons is : {0} ", countComps);

Мой счетчик свопов дает выходное значение 1, что явно неверно. Мой счетчик сравнения дает выходное значение 5128 - это относится к числу значений в текстовом файле. Я уверен, что сравнения должны быть число значений в списке - 1.

Answer 1

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

        …}
        countSwaps = 0; // <--------- here!
        swap(Array, i, max); …

Во-вторых, вы вообще не учитываете сравнения;Вы подсчитываете, сколько раз запускается внешний цикл.Вы должны увеличивать countComps каждый раз, когда происходит фактическое сравнение:

        for (int j = i + 1; j < Array.Length; j++)
        {
            ++countComps; <--------- here!
            if (Array[j] > Array[max])
                max = j; // max equals biggest in list j
        }

Сортировка выбора - это сортировка O (n ^ 2), и вы, вероятно, получите несколько миллионов сравнений для 5000 записей, чтоэто много, и именно поэтому мы обычно не используем сортировку выбора для больших коллекций.Сортировка O (n * log n), такая как сортировка слиянием, будет производить что-то вроде 60 тыс. Сравнений.