Неправильный подсчет сравнений/перестановок в сортировках - 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; }
ИИ поможет Вам:
- решить любую задачу по программированию
- объяснить код
- расставить комментарии в коде
- и т.д