Неправильный подсчет сравнений/перестановок в сортировках - C#
Формулировка задачи:
Доброго времени суток!
Пробую подсчитать количество сравнений и перестановок в алгоритмах сортировок выбора и обмена. Проблема в том, что подсчет очевидно неправильный, когда мы передаем отсортированный и обратно отсортированный массив (т.е в обратном порядке). Подскажите в чем может быть ошибка?
using System;
using System.Linq;
public class Test
{
const int n = 56;
public static void Main()
{
//Создаем массив на 56 элементов
int[] A1 = new int[n];
Random ran_1 = new Random();
Random ran_2 = new Random();
Console.WriteLine("\nСортируем отсортированный массив\n");
//Отсортипрованные массивы
for (int i = 0; i < n; i++)
{
A1[i] = i+1;
Console.Write(A1[i] + " ");
}
//Сортировка выбором
SortVyborVozrast(A1);
Console.WriteLine("\nСортируем отсортированный массив\n");
for (int i = 0; i < n; i++)
{
A1[i] = i+1;
Console.Write(A1[i] + " ");
}
//Сортировка обменом
SortObmenVozrast(A1);
Console.WriteLine("\nСортируем массив в обратном порядке\n");
// Обращаем массив
for (int i = n-1; i >= 0; i--)
{
A1[i] = i+1;
Console.Write(A1[i] + " ");
}
//И сортируем
SortVyborVozrast(A1);
Console.WriteLine("\nСортируем массив в обратном порядке\n");
//Повторно обращаем массив
for (int i = n-1; i >= 0; i--)
{
A1[i] = i+1;
Console.Write(A1[i] + " ");
}
SortObmenVozrast(A1);
Console.WriteLine("Массив случайных чисел:\n");
//Заполняем его случайными числами
for (int i = 0; i < n; i++)
{
A1[i] = ran_1.Next(1, n);
Console.Write(A1[i] + " ");
}
Console.WriteLine("\nСортируем массив случайных чисел");
//Сортировка выбором
SortVyborVozrast(A1);
Console.WriteLine("\nМассив случайных чисел:\n");
//Инициализируем массив заново
for (int i = 0; i < n; i++)
{
A1[i] = ran_2.Next(1, n);
Console.Write(A1[i] + " ");
}
//Сортировка обменом
SortObmenVozrast(A1);
Console.ReadKey();
}
public static void Write(int[] A)
{
Console.WriteLine("После сортировки:\n");
for (int i = 0; i < n; i++)
Console.Write(A[i] + " ");
}
public static void SortVyborVozrast(int[] A)
{
int temp, min, comparison = 0, swap = 0;
for (int i = 0; i < n - 1; i++)
{
min = i;
for (int j = i + 1; j < n; j++)
{
if (A[j] < A[min])
{
min = j;
swap++;
}
comparison++;
}
if(min!=i){
temp = A[i];
A[i] = A[min];
A[min] = temp;
swap += 4;
}
}
Write(A);
Console.WriteLine("\n Сортировка выбором. Сравнений= " + comparison + " Перестановок= " + swap);
}
public static void SortObmenVozrast(int[] A)
{
int temp, comparison = 0, swap = 0;
for (int i = 1; i < n; i++)
{
for (int j = 0; j < n - 1; j++)
{
if (A[j] > A[j + 1])
{
temp = A[j];
A[j] = A[j + 1];
A[j + 1] = temp;
swap += 3;
}
comparison++;
}
}
Write(A);
Console.WriteLine("\nСортировка Обменом. Сравнений= " + comparison + " Перестановок= " + swap);
}
}Решение задачи: «Неправильный подсчет сравнений/перестановок в сортировках»
textual
Листинг программы
if(min!=i){
temp = A[i];
A[i] = A[min];
A[min] = temp;
swap += 4;
}