Главная · Карта сайта · Поиск · Статьи · Компьютерные курсы · Обучающие программы · Открытые проекты · Веб-программирование · Создание интернет-сайта · Полезные ссылки · Глоссарий · Контакты · Декабрь 09 2016 20:17:38
Последнее опубликованное

Что такое Model-View-Controller
Pattern Model-View-Controller

Как создать свой веб-сайт
Как создать свой сайт в интернете

Разное
Статистика

Основы программирования. Сортировка


Содержание курса

Ford Mustang - тоже классика в своем жанре...

Шаг 1. Сортировка чисел методом "пузырька"

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

Описание алгоритма

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

Используемые конструкции языка программирования

Цикл с предусловием while - организация повторения последовательности операций, заключенных между { и } в C# и размещенных до оператора End While в VB.NET. Повторение осуществляется до тех пор, пока условие цикла истинно. В нашем случае это означает: пока переменная _changed соответствует значению true.

Цикл со счетчиком for - организация конечного, определенного в заголовке цикла числа повторений последовательности операций, заключенных между { и } в C# и размещенных до оператора Next в VB.NET. Каждая итерация цикла for характеризуется номером итерации, который, в нашем случае, хранится в переменной i и с каждым шагом изменяется в соответствии с определением заголовка цикла. В приведенном примере - увеличивается на единицу.

Оператор условного перехода if - организация разветвления хода выполнения алгоритма в зависимости от условия. Если условие истинно, то выполняется последовательность операций, заключенных между { и } в C# и после оператора Then в VB.NET. Если условие ложно, то, в случае наличия конструкции else, сначала выполняется последовательность операций, соответствующих else, а потом осуществляется переход к операции, следующей сразу же за оператором условного перехода if.

Массив целых чисел. В данном примере для представления сортируемой последовательности в памяти используется массив целых чисел _val. Массив – это набор переменных одного типа, объединенных одним именем. Каждый элемент массива идентифицируется именем массива и индексом – порядковым номером элемента в последовательности, указанным в скобках (в квадратных в случае C# и круглых в случае VB.NET). В программировании чаще всего элементы в массивах нумеруются, начиная с нуля. Если быть точным, то в конкретном примере используется не массив в классическом его понимании, а линейный список элементов List, но внешне обработка массива и подобного списка в цикле for ничем отличаться не будет. Более подробно про применение массивов в программировании будет рассказано позже, а на данном этапе важно понять общий принцип обработки поименованных наборов однотипных значений.

Более подробно про основные конструкции наиболее известных языков программирования можно прочитать здесь.

Фрагмент исходного кода

C#:
     bool _changed = true;
     while (_changed)
     {
         _changed = false;
         for (int i = 0; i < _vals.Count - 1; i++)
         {
             if (_vals[i] > _vals[i + 1])
             {
                 int _val = _vals[i + 1];
                 _vals[i + 1] = _vals[i];
                 _vals[i] = _val;
                 _changed = true;
             }
         }
     }
VB.NET:
        Dim _changed As Boolean = True
        While _changed
            _changed = False
            For i As Integer = 0 To _vals.Count - 2 Step 1
                If _vals(i) > _vals(i + 1) Then
                    Dim _val As Integer
                    _val = _vals(i + 1)
                    _vals(i + 1) = _vals(i)
                    _vals(i) = _val
                    _changed = True
                End If
            Next
        End While

Комментарии к программному коду

Итак, выше приведены фрагменты программ, реализующих этот замечательный алгоритм сортировки на языках программирования C# и VB.NET. Для первого входа в цикл while нам необходимо сразу присвоить логической или булевой переменной _changed значение 'истина' (true). В начале тела цикла while мы ей присваиваем значение 'ложь' (false) и начинаем уже в теле цикле for поиск пары чисел, первое из которых больше второго. Индексация в списке чисел, в нашем случае, начинается с '0', поэтому порядковый номер итерации цикла for начинается с '0': for (int i = 0;.... Если бы мы хотели пройти до самого конца последовательности чисел, то нам бы следовало поставить условие i < _vals.Count, но, поскольку мы проверяем числа парами, то нам достаточно поставить условие завершения цикла i строго меньше размера последовательности "минус один": ...i < _vals.Count - 1;.... За каждую итерацию значение переменной i должно увеличиваться на единицу, что отражено в алгоритме на C# фрагментом i++, а в алгоритме на VB.NET фрагментом Step 1. Если на определенной итерации мы находим два числа, чей порядок с точки зрения сортировки нарушен, то мы, после их перестановки (с использование отдельной переменной _val, необходимой для временного хранения значения одного из переставляемых элементов последовательности), также выставляем переменной _changed значение 'истина', чтобы внешний цикл while не завершился, и продолжаем цикл for дальше. Если ни одной пары чисел переставлено не было, то переменная _changed остается со значением 'ложь', и внешний цикл while завершается. Таким образом, в ходе каждой итерации меньшие числа приближаются к началу последовательности, как пузырьки в стакане с газировкой стремятся наверх.

Оптимизация алгоритма

Приведенный алгоритм требует оптимизации. Внутренний цикл for каждый раз выполняет не что иное, как поиск максимального элемента, который, в результате, оказывается в конце последовательности. При первом же проходе внутреннего цикла максимальный элемент будет найден, и все последующие сравнения с ним к перестановке элементов уже не приведут. При втором выполнении цикла for будет определен 2-й по величине элемент, при третьем – третий и т.д. Получается, что с каждым разом программа все больше и больше выполняет бесполезной работы, сравнивая между собой уже отсортированные по возрастанию элементы. Решение: внутренний цикл должен с каждым разом выполнять на одну итерацию меньше. Для этого придется ввести отдельную целочисленную переменную, например _sorted, которую следует объявить, также как переменную _changed, до цикла while и инициализировать ее нулем. в C# это будет выглядеть так: int _sorted = 0; а в VB.NET так: Dim _sorted As Integer = 0. Определение заголовка цикла for следует изменить следующим образом: for (int i = 0; i < _vals.Count – 1 - _sorted; i++) в C# и For i As Integer = 0 To _vals.Count – 2 - _sorted Step 1 в VB.NET. После цикла for переменную _sorted следует увеличивать на единицу: _sorted++; в C# и _sorted = _sorted + 1 в VB.NET. В полных версиях алгоритма эти изменения уже присутствуют.

Полные версии алгоритмов

На языке C#.
На языке VB.NET.

Резюме

В ходе изучения кода алгоритмов, вы сразу же и познакомитесь с некоторыми основными конструкциями алгоритмических языков программирования, такими как циклы while, for и оператором условного перехода if. Если вы читаете этот текст, значит, у вас есть доступ в интернет - узнайте более подробно про алгоритм сортировки ‘пузырьком’ в Википедии, пройдя по ссылке выше.

Самостоятельно

Обязательно запустите программы под управлением Microsoft Visual Studio или Coding Craft Studio и попробуйте, к примеру, поменять целочисленный тип int и Integer на вещественный double. Обо всех сложностях и проблемах, связанных с использованием Coding Craft Studio пишите здесь.

Важно: Обратите внимание на конструкцию try-catch, которая была использована при вводе исходной последовательности чисел (в полной версии алгоритма). Именно эта конструкция позволяет корректно обрабатывать исключительные ситуации, возникающие в программе в ходе ошибок вычисления или ошибок ввода исходных данных. Тема обработки исключительных ситуаций в более или менее полном виде рассматривается в разделах курса программирования C# Quick Guide™.

Далее: Нахождение простых чисел.



Компьютерные курсы и курсы программирования
Основы программирования

Курс для начинающих программистов на C# и VB.NET.

SQL 25™

Построение SQL запросов и работа с базой данных.

C# Quick Guide™

Программирование на C#. Краткое руководство.

RegEx

Применение регулярных выражений.

Plug-in архитектура

Примеры программной Plug-in архитектуры.

XML и его расширения

Язык разметки XML и его расширения с примерами.

HTML и разметка гипертекста

Языки HTML, XHTML и CSS с примерами разметки.

Основы веб-дизайна

Основы веб-дизайна: решения типовых задач верстки.

Программирование на PHP

Руководство по программированию на PHP для начинающих.

Справочные материалы

Шаблоны проектирования
Каталог шаблонов проектирования программных компонентов.

Рефакторинг кода
Каталог приемов рефакторинга программного кода.

Гость
Имя

Пароль



Забыли пароль?
Запросите новый здесь
.
Coding Craft. Все права защищены © 2011. Проект Инициативного Народного Фронта Образования - ИНФО-проект.