Алгоритмы сортировки

ВСЕРОССИЙСКИЙ ЗАОЧНЫЙ ФИНАНСОВО-ЭКОНОМИЧЕСКИЙ

ИНСТИТУТ

КАФЕДРА АВТОМАТИЗИРОВАННОЙ ОБРАБОТКИ

ЭКОНОМИЧЕСКОЙ ИНФОРМАЦИИ 
 
 
 
 

КУРСОВАЯ  РАБОТА

по дисциплине «Информатика»

на тему «Алгоритмы сортировки» 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

   ОГЛАВЛЕНИЕ 

ВВЕДЕНИЕ...………………………………………………….…………………....3

1.ТЕОРЕТИЧЕСКАЯ  ЧАСТЬ……………………………….……………………..5

1.1. Понятие алгоритма сортировки..………...…...…..……………………….…..5

1.2. Характеристика основных видов алгоритма сортировки ……………….…..8

1. Сортировка пузырьком
2. Сортировка перемешиванием
3. Сортировка методом вставок
4. Сортировка подсчётом
5. Сортировка слиянием
6. Цифровая сортировка
7. Поразрядная сортировка
8. Сортировка методом выбора
9. Сортировка методом Шелла
10. Пирамидальная сортировка
11. Быстрая сортировка

2. ПРАКТИЧЕСКАЯ  ЧАСТЬ…………………………………………………….....17

2.1. Практическое задание №7………...………….………………….…….…….....17

2.2. Описание алгоритма решения практического задания……………....…….....19

ЗАКЛЮЧЕНИЕ……………………………………………………………….……...24

СПИСОК  ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ……...……………...…………..25 
 
 
 
 
 
 
 
 

   ВВЕДЕНИЕ 

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

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

       Сам термин «информатика» (informatique) возник в 60-х годах во Франции для определения области исследований, связанных с автоматизацией обработки информации с помощью электронных вычислительных машин (ЭВМ). Этот термин был образован слиянием слов information (информация) и automatique (автоматика) для обозначения информационной автоматики или автоматизированной переработки информации.

       Данная курсовая работа состоит из двух частей: теоретической и практической.

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

       В практической части курсовой работы с помощью пакетов прикладных программ (ППП) будут решены и описаны следующие задачи:

1. создание таблиц и заполнение таблиц данными;
2. применение математических формул для выполнения запросов в ППП;
3. построение графиков.

       Краткие характеристики ПК и программного обеспечения, использованных для выполнения и оформления курсовой работы: 
 

       

• Процессор: INTEL PENTIUM 4 1.7 GHz;
• Оперативная память: SD RAM 256mb;
• Жесткий диск: HDD 40Gb;
• Видеокарта: ATI RADEON 9600pro;
• Клавиатура: Logitech G15;
• Мышь: Logitech G9.

       Программные средства: операционная система Windows ХР Professional sp2, пакет прикладных программ – MS Office 2003(из него использованы для выполнения курсовой работы: текстовый процессор MS Word 2003,  табличный процессор MS Excel2003). 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

   1. ТЕОРЕТИЧЕСКАЯ ЧАСТЬ 

    

1. Понятие алгоритма

 

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

    Слово «алгоритм» происходит от имени узбекского математика девятого века Аль-Харезми, который сформулировал правило четырёх арифметических действий над многозначными числами. В дальнейшем это слово стало использоваться не только в математике, а фактически любую последовательность действий, приводящих к конечному результату, стали называть алгоритмом, а каждое действие шагом алгоритма. Алгоритм обладает рядом свойств, связанных с необходимостью выполнения определенных требований к процессу вычисления. Это следующие свойства: 1) определённость; 2) массовость; 3) результативность; 4) дискретность. Определённость алгоритма означает,  что каждый шаг алгоритма должен быть точен, общепонятен, и исключать возможность различного толкования, другими словами алгоритм должен быть таким, чтобы его мог повторить любой пользователь. Массовость заключается в том, что алгоритм предназначен для решения целого класса задач, которые отличаются только своими входными условиями. Результативность означает, что пошаговый процесс решения задачи в соответствии с алгоритмом должен заканчиваться через определенное конечное число шагов.

   Формы представления алгоритма:

1. Словесная форма;
2. Словесно-аналитическая форма;
3. В виде блок-схемы (графическое изображение алгоритма);
4. В виде программы на алгоритмическом языке программирования.

 
 
 
 

   Виды  алгоритмических структур:

1. Линейный алгоритм, в которой все команды выполняются последовательно одна за другой.
2. Разветвляющийся, в которой в зависимости от условия выполнения либо одна серия команд, либо другая.
3. Циклический, в которой многократно повторяется некоторый участок алгоритма.

 

     I-ое поколение алгоритмических языков - конец 1950-х начало 1960-х. Совершенствовались ассемблерные языки. В настоящее время они применяются для создания драйверов оборудования ПК.

   II-ое поколение - 60е годы. В это время появляются универсальные языки высшего уровня: ФОРТРАН, АЛГОЛ, КОБОЛ, обеспечивающие создание программ для решения задач различного класса.

   III-e  поколение. С начала 1970-х годов начался переход на создание больших программных комплексов. Они в основном применяются для проектирования приложений баз данных и средств визуального программирования.

   В середине 1990-х – 4 поколение языков программирования, назначение которых для образования инструкции текст программ на универсальном языке программирования. Система 4 поколения имеет открытую архитектуру и поддерживает значительное число программных продуктов.  

   Языки программирования:

1. Бейсик отличается встроенными математическими функциями и простыми языковыми конструкциями.
2. Паскаль предназначен для решения вычислительных и информационно-логических задач.
3. Си + + был разработан для облегчения процесса переноса программного обеспечения с одной ЭВМ на другую.
4. Ада ориентирован для применения в системах реального времени и предназначен для разработки программного обеспечения встроенных вычислительных систем.
5. Java (джава) предназначен для создания надёжных, переносимых, распределённых сетевых программных приложений, работающих в архитектуре клиент–сервер, а также удобен для администраторов сети.
6. другим объектно-ориентировочным языком является язык Delphi (дельпхи). Обеспечивает взаимодействие с базами данных, создание различных видов баз, а также работу экономических программ и сети интернет.

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

    1.2 Характеристика основных видов алгоритмов сортировки. 

    Алгоритм  сортировки — это алгоритм для упорядочения элементов в списке. В случае, когда элемент списка имеет несколько полей, поле по которому производится сортировка, называется ключом сортировки. На практике, в качестве ключа часто выступает число, а в остальных полях хранятся какие-либо данные, никак не влияющие на работу алгоритма.

   Пожалуй, никакая другая проблема не породила такого количества разнообразнейших решений, как задача сортировки. Существует ли некий «универсальный», наилучший  алгоритм? Вообще говоря, нет. Однако, имея приблизительные характеристики входных данных, можно подобрать метод, работающий оптимальным образом.

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

   Практически каждый алгоритм сортировки можно разбить на три части:

1. сравнение, определяющее упорядоченность пары элементов;
2. перестановку, меняющую местами пару элементов;
3. собственно сортирующий алгоритм, который осуществляет сравнение и перестановку элементов до тех пор, пока все элементы множества не будут упорядочены.

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

    Основные  виды сортировок:

    a)Сортиро́вка пузырько́м (англ. bubble sort) — простой алгоритм сортировки. Алгоритм состоит в повторяющихся проходах по сортируемому массиву. За каждый проход элементы последовательно сравниваются попарно и, если порядок в паре неверный, выполняется обмен элементов. Проходы по массиву повторяются до тех пор, пока на очередном проходе не окажется, что обмены больше не нужны, что означает — массив отсортирован. При проходе алгоритма, элемент, стоящий не на своём месте, «всплывает» до нужной позиции как пузырёк в воде, отсюда и название алгоритма.

     Сортировка  методом пузырька имеет сложность O(n2). Для понимания и реализации это — простейший алгоритм сортировки, но эффективен он лишь для небольших массивов. 

Пример реализации алгоритма (язык Pascal):

 for i := n - 1 downto 1 do

   for j := 1 to i do

     if a[j] > a[j+1] then

     begin

       t := a[j];

       a[j] := a[j+1];

       a[j+1] := t;

     end; 
 

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

    Лучший  случай для этой сортировки — отсортированный массив (О(n)), худший — отсортированный в обратном порядке (O(n²)).