Задача «Сортировка данных»

Постановка задачи

Сравните ваши действия по поиску нужной фамилии в неупорядоченном списке или же в таком же, но упорядоченном по алфавиту, и представьте себе, что в этом списке более 140 млн человек. Тогда становится понятной важность задачи упорядочения данных по одному или нескольким критериям, которую программисты называют задачей сортировки.

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

Здесь же мы рассмотрим только два простейших, но далеко не самых эффективных алгоритмов внутренней (т.е. внутри одного массива) сортировки. Нужно же вам с чего-то начинать!  Это пузырьковая сортировка и сортировка через минимальный элемент.

Алгоритмы

Алгоритм сортировки через минимальный элемент основан на следующей идее: Первый элемент массива сравниваем с минимальным элементом из всех оставшихся элементов. Если минимальный элемент больше первого, то поменяем их местами. Это гарантирует размещение наименьшего элемента в начале массива. А теперь тоже самое сделаем для последовательности, начиная со второго элемента, затем с третьего и т.д. вплоть до тех пор, пока эта последовательность не сократится до одного элемента. Нахождение минимального элемента последовательности полезно выделить в отдельный метод, тогда алгоритм станет еще прозрачнее.

Алгоритм пузырьковой сортировки по убыванию основан на идее всплывания более легкого элемента вверх (в конец массива), обмениваясь местами с соседними элементами. Здесь также необходимы два цикла, чтобы полностью отсортировать все элементы.

Программная реализация

В классе Program объявим:
const int N_max = 1000000;  // максимальная размерность массива
static double[] a = new double[N_max];  // массив
Каждый блок программы оформим как отдельный статический метод класса Program (в предыдущем примере разделялись только строками комментариев).
Далее все должно быть понятно из комментариев в тексте программы.

// Сортировка через минимальный элемент и Пузырьковая сортировка
using System;
namespace ConsoleApplication4
{
   class Program
   {
      const int N_max = 1000000;  // максимальная размерность массива
      static double[] a = new double[N_max];  // объявление массива
        
      static void Main(string[] args)
      {
         int n = InputA();  // количество элементов и ввод массива
         OutputA("До сортировки", n);  // вывод массива
         MaxSort(n);        // сортировка по по возрастанию
         OutputA("После сортировки через минимальный элемент", n);
         BoobleSort(n);     // сортировка по убыванию
         OutputA("После пузырьковой сортировки", n);
         Console.ReadKey();
      }
      // Ввод данных 
      static int InputA()
      {
         int n;
         Console.Write("Ввести кол-во чисел: ");
         n = Convert.ToInt32(Console.ReadLine());
         for (int i = 0; i < n; i++)
         {
            Console.Write("a[{0}]=", i);
            a[i] = Convert.ToDouble(Console.ReadLine());
         }
         return n;
      }
      // Вывод массива
      static void OutputA(string z, int n)
      {
         Console.WriteLine(z);
         for (int i = 0; i < n; i++)
         {
            Console.Write("{0:#.#}    ",a[i]);
         }
         Console.WriteLine();
      }
      // Сортировка через минимальный элемент по возрастанию
      static void MaxSort(int n)
      {                
         double p;
         int k;
         for (int i = 0; i < n - 1; i++)
         {
            k = k_min(i + 1, n);
            if (a[i] > a[k])
            {
               p = a[i];
               a[i] = a[k];
               a[k] = p;
            }
         }
      }
      // Нахождение минимального элемента массива от j до n
      static int k_min(int j, int n)
      {
         double min=a[j];
         int k=j;
         for (int i = j + 1; i < n; i++)
         {
            if (a[i] < min)
            {
               min = a[i];
               k = i;
            }
         }
         return k;
      }
      // Пузырьковая сортировка по убыванию
      static void BoobleSort(int n)
      {
         double c;
         for (int i = n - 1; i > 0; i--)
             for (int j = 0; j < i; j++)
             {
                if (a[j]<a[j + 1])
                {
                    c = a[j];
                    a[j] = a[j + 1];
                    a[j + 1] = c;
                }
            }
        }
    }
}

Обратите внимание на то, насколько эффективно выделять методы (подпрограммы с точки зрения структурного программирования) и присваивать им смысловые имена: каждый из 6 методов размещается менее чем на одной странице и легко анализируется.  Метод OutputA( ) вызывается трижды с разными заголовками.

Результат:

Вопрос на «засыпку»

Сколько операторов нужно изменить для смены направления сортировки (по убыванию — для первого, по возрастанию — для второго алгоритма)?

Следующая задача — Линейный и бинарный поиск

---

NEW: Наш Чат, в котором вы можете обсудить любые вопросы, идеи, поделиться опытом или связаться с администраторами.

---

Помощь проекту: