Шаг 54.
Язык программирования C#. Начала
Массивы. Операции с массивами (окончание)

    На этом шаге мы рассмотрим алгоритм сортировки массива.

    Следующий пример имеет отношение к сортировке массивов. Для этого используем метод пузырька. Метод пузырька может применяться к массиву из элементов, для которых имеют смысл операции сравнения. Сортировка массива выполняется следующим образом. Последовательно перебираются все элементы массива. Сравниваются пары соседних элементов. Если значение элемента слева больше значения элемента справа, то эти элементы обмениваются значениями. В противном случае ничего не происходит. После одного полного перебора элементов самое большое значение гарантированно будет у последнего элемента. Чтобы второе но величине значение было у предпоследнего элемента, необходимо еще раз перебрать элементы массива (и выполнить для них попарное сравнение). При этом последний элемент уже можно не проверять. Чтобы переместить на "правильную" позицию третье по величине значение, еще раз перебираются элементы массива (теперь можно не проверять два последних элемента). Процесс продолжается до тех пор, пока значения элементов не будут отсортированы в возрастающем порядке. Итак, один полный перебор элементов гарантирует перестановку в "правильную" позицию одного значения. Количество полных переборов на единицу меньше количества элементов в массиве, поскольку, когда второй элемент имеет "правильное" значение, то автоматически у первого элемента оно тоже "правильное". При первом переборе проверяются все элементы массива. За каждый следующий перебор проверяется на одни элемент меньше, чем это было для предыдущего раза.

    Теперь рассмотрим текст программы. Там методом пузырька сортируется символьный массив.

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace pr54_1
{
    class Program
    {
        static void Main()
        {
            // Символьная переменная: 
            char s;
            // Исходный символьный массив:
            char[] symbs = {'Q', 'Ы', 'a', 'B', 'R', 'A', 'r', 'q', 'b'};
            // Отображение содержимого массива:
            Console.WriteLine("Массив до сортировки:"); 
            for (int k = 0; k < symbs.Length; k++){
                Console.Write(symbs[k] + " ");
            }
            Console.WriteLine();
            // Сортировка элементов в массиве: 
            for (int i = 1; i < symbs.Length; i++){
                // Перебор элементов:
                for (int j = 0; j < symbs.Length-i; j++){
                    // Если значение элемента слева больше 
                    // значения элемента справа: 
                    if ( symbs[j] > symbs[j + 1] )
                    {
                        s = symbs[j+1]; 
                        symbs[j+1] = symbs[j]; 
                        symbs[j] = s;
                    }
                }
            }
            // Отображение содержимого массива:
            Console.WriteLine("Массив после сортировки:"); 
            for (int k=0; k < symbs.Length; k++){
                Console.Write(symbs[k] + " ");
            }
            Console.WriteLine();
            // Задержка:
            Console.ReadLine();
        }
    }
}
Архив проекта можно взять здесь.

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


Рис.1. Результат выполнения приложения

    Массив, предназначенный для сортировки, создается в программе командой

  char[] symbs = {'Q', 'Ы', 'a', 'B', 'R', 'A', 'r', 'q', 'b'};    .
Это символьный массив. Он инициализирован списком, содержащим строчные и прописные английские буквы и одну кириллическую (символ 'Ы'). Массив перед сортировкой отображается в консольном окне. Для этой цели использована конструкция цикла. После этого начинается сортировка элементов массива. Для сортировки использованы вложенные циклы. Внешний цикл с индексной переменной i "подсчитывает" общие переборы элементов в массиве. Значение индексной переменной i последовательно меняется с 1 до symbs.Length-1 включительно (то есть общее количество переборов на единицу меньше количества элементов в массиве). При фиксированном значении индексной переменной i во внутреннем цикле индексная переменная j пробегает значения от 0 до symbs.Length-i-1 включительно. Эта индексная переменная "перебирает" индексы элементов в массиве. За первый цикл (при значении переменной i равном 1) переменная j пробегает значения от 0 до symbs.Length-2. Здесь нужно учесть, что в теле цикла обрабатываются два элемента - с индексом j и с индексом j+1. При первом переборе просматриваются все элементы. Последний допустимый индекс в массиве определяется значением symbs.Length-1. Из условия, что больший индекс j+1 принимает максимально возможное значение symbs.Length-1, получаем, что максимально возможное значение индекса j равно symbs.Length-2. За каждый перебор просматривается на один элемент меньше, отсюда и получаем, что индекс j в общем случае должен быть меньше, чем symbs.Length-i.

    В теле внутреннего цикла размещена условная конструкция. Здесь проверяется условие symbs[ j ]>symbs [ j+1]. Оно истинное, если элемент слева больше элемента справа. Если так, то сначала командой

  s = symbs[j+1]; 
значение "элемента справа" записывается в переменную s. Командой
  symbs[j+1] = symbs[j]; 
значение "элемента слева" присваивается "элементу справа". Наконец, командой
  symbs[j] = s;
"элементу слева" присваивается значение переменной s, которое есть исходное значение "элемента справа". Таким образом, состоялся обмен значениями между элементами.

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


В кодовой таблице коды букв следуют один за другим в соответствии с тем, как буквы размещены в алфавите. Код строчных (маленьких) букв больше кодов прописных (больших) букв. Например, код английской буквы 'А' равен 65, а код английской буквы 'а' равен 97. Русская буква 'А' в стандартной раскладке имеет код 1040, а русская буква 'а' имеет код 1072. Поэтому при сортировке элементов символьного массива в порядке возрастания сначала следуют большие английские буквы в алфавитном порядке, затем английские маленькие буквы в алфавитном порядке, затем большие русские буквы в алфавитном порядке и после этого - маленькие русские буквы в алфавитном порядке.

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

    На следующем шаге мы рассмотрим цикл по массиву.




Предыдущий шаг Содержание Следующий шаг