Руководитель
МОУ-СОШ с. Кировское Марксовского района Саратовской области
СОРТИРОВКА – ОТ ХАОСА К ПОРЯДКУ
Сортировка массива – один из наиболее распространенных процессов обработки данных.
Так, например, список учеников класса, фамилии в телефонном справочнике, банковские картотеки клиентов всегда отсортированы в определённом порядке для облегчения доступа к нужной информации.
Механические сортировки – построение солдат по росту, раскладка денежных купюр или игральных карт по их достоинству и т. д., имеют место в повседневной жизни и кажутся простыми. Простота эта иллюзорна, потому что сортируется небольшое количество элементов.
Первые программы сортировки были написаны фон Нейманом в 1945 году и до середины 60-х годов какого-либо продвижения в теории сортировки не наблюдалось. Проблема сортировки остро возникла с широким внедрением ЭВМ в бизнес, где необходимо было обрабатывать огромные массивы числовой и текстовой информации.
Методы сортировки делятся на прямые и улучшенные.
Улучшенные методы сортировки основываются на тех же принципах, что и прямые, с использованием оригинальных идей и рационализаций для ускорения процесса преобразования массива данных. Поэтому для понимания основных принципов большинства сортировок изучение лучше начинать с прямых методов. К тому же, так как улучшенные методы требуют большого числа операций, для массивов размерностью меньше 100 элементов, прямые методы оказываются эффективнее. Прямые методы актуальны еще и тем, что моделируют естественное поведение человека, осуществляющего сортировку вручную.
Прямые методы разделяются по принципу, лежащему в их основе, на сортировки:
o обменом (метод пузырька);
o выбором (метод выбора);
o вставкой (метод вставки).
Для оценки быстродействия алгоритмов различных методов сортировки, как правило, используют два показателя:
o количество присваиваний;
o количество сравнений.
Прямые методы сортировки требуют приблизительно n2 сравнений, где n – размерность массива. Количество присваиваний чаще всего зависит от предварительной упорядоченности массива.
В данной работе автор исследует прямые методы сортировки одномерного массива, определяет, какие из методов наиболее эффективны, и в каких случаях. А также показывает, как путем усложнения алгоритма, можно добиться значительного выигрыша в эффективности. В презентации проекта наглядно демонстрируется процесс сортировки одномерного массива с помощью эффектов анимации.
