Анализ некоторых методов сортировок массива на различных языках программирования
проект по информатике и икт на тему

ГОРОДСКАЯ НАУЧНО - ПРАКТИЧЕСКАЯ КОНФЕРЕНЦИЯ ШКОЛЬНИКОВ

«ШАГ В БУДУЩЕЕ»

РОССИЙСКАЯ ФЕДЕРАЦИЯ

ХАНТЫ-МАНСИЙСКИЙ АВТОНОМНЫЙ ОКРУГ – ЮГРА 

Анализ некоторых методов сортировок массива

на различных языках программирования

Научно-исследовательская работа

Автор:

Гаврилов Илья Викторович

ученик 8-А класса

Муниципального бюджетного общеобразовательного учреждени

муниципального образования г. Нягань « Гимназия»

Научный руководитель:

Юдина Ирина Игоревна

учитель информатики и ИКТ

первой квалификационной категории

Муниципального бюджетного общеобразовательного учреждени

муниципального образования г. Нягань « Гимназия»

Нягань 2014

Оглавление

Анализ некоторых методов сортировок массива на

различных языках программирования

 Гаврилов Илья Викторович

Россия, Ханты – Мансийский автономный округ – Югра,

Тюменская область, г. Нягань 

Муниципальное бюджетное общеобразовательное учреждение

муниципального образования г. Нягань « Гимназия», 8-А класс

Аннотация

На данный момент мировая компьютерная индустрия развивается очень стремительно. Производительность систем возрастает, а, следовательно, возрастают возможности обработки больших объёмов данных. Изучая языки программирования, я столкнулся с целым классом задач, в которых необходимо полученный результат отобразить в упорядоченном виде. Какой выбрать язык при обработке больших объемов числовых данных? И как это отобразится на выбранном методе сортировки массива. Объект и предмет исследования – методы сортировки данных, используемые  на различных языках программирования. Цель: исследовать некоторые методы сортировок на различных языках программирования. 

Задачи исследования:

1. Изучить источники данных о методах сортировки.
2. Провести анализ популярности языков программирования.
3. Составить программы сортировок на различных языках программирования.
4. Провести анализ и вычислить среднее время каждой сортировки.
5. Выявить преимущества и недостатки различных методов сортировок в зависимости от языка программирования.

Методы исследования:

• анализ научной литературы и Интернет-ресурсов по теме;
• эксперимент;
• сравнение и обобщение полученных результатов.

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

 Вывод: выбор языка программирования в первую очередь зависит от круга задач – C/C++/Java/C# скорее всего не сможет заменить JavaScript для веб-страниц и наоборот.

Анализ некоторых методов сортировок массива на

различных языках программирования

 Гаврилов Илья Викторович

Россия, Ханты – Мансийский автономный округ – Югра,

Тюменская область, г. Нягань 

Муниципальное бюджетное общеобразовательное учреждение

муниципального образования г. Нягань « Гимназия», 8-А класс

План исследования

Занимаясь программированием, я заметил, что часто приходится решать задачи на обработку числовых данных.  Изобретено множество различных алгоритмов сортировки и множество языков программирования. Зависит ли время сортировки массива от языка программирования? В настоящее время большой популярностью пользуется сеть Интернет. А значит, мы имеем дело с интерактивными сайтами.  Я предположил, что быстрая сортировка на языке JavaScript является  самой оптимальной при обработке числовых данных.

Для достижения намеченной цели  мною был разработан следующий план:

• 1 этап исследования.

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

В данной работе рассмотрены сортировки массивов на четырех языках программирования: C++, C#, Pascal и JavaScript.

Массив задает способ организации данных. Массивом называют упорядоченную совокупность элементов одного типа. Каждый элемент массива имеет индексы, определяющие порядок элементов. Число индексов характеризует размерность массива. Каждый индекс изменяется в некотором диапазоне [a,b]. В языке C#, как и во многих других языках, индексы задаются целочисленным типом. В других языках, например, в языке Паскаль, индексы могут принадлежать счетному конечному множеству, на котором определены функции, задающие следующий и предыдущий элемент. Диапазон [a,b] называется граничной парой, a - нижней границей, b - верхней границей индекса. При объявлении массива границы задаются выражениями. Если все границы заданы константными выражениями, то число элементов массива известно в момент его объявления и ему может быть выделена память еще на этапе трансляции. Такие массивы называются статическими. Если же выражения, задающие границы, зависят от переменных, то такие массивы называются динамическими, поскольку память им может быть отведена только динамически в процессе выполнения программы, когда становятся известными значения соответствующих переменных. Массиву, как правило, выделяется непрерывная область памяти.

В языке C++ все массивы являются статическими; более того, все массивы являются 0-базируемыми. Это означает, что нижняя граница всех индексов массива фиксирована и равна нулю. Введение такого ограничения имеет свою логику, поскольку здесь широко используется адресная арифметика. Так, несколько странное выражение mas + i, где mas - это имя массива, а i - индексное выражение, имеет вполне определенный смысл для C++ программистов. Имя массива интерпретируется как адрес первого элемента массива, к этому адресу прибавляется число, равное произведению i на размер памяти, необходимой для одного элемента массива. В результате сложения в такой адресной арифметике эффективно вычисляется адрес элемента mas[i].

В языке C# снято существенное ограничение языка C++ на статичность массивов. Массивы в языке C# являются настоящими динамическими массивами. Как следствие этого, массивы относятся к ссылочным типам, память им отводится динамически в "куче". К сожалению, не снято ограничение 0-базируемости, хотя, в таком ограничении уже нет логики из-за отсутствия в C# адресной арифметики. Было бы гораздо удобнее во многих задачах иметь возможность работать с массивами, у которых нижняя граница не равна нулю.

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

Отсчет индексов массивов в языке JavaScript начинается с нуля и для них используются 32-битные целые числа - первый элемент массива имеет индекс 0. Массивы в JavaScript являются динамическими: они могут увеличиваться и уменьшаться в размерах по мере необходимости; нет необходимости объявлять фиксированные размеры массивов при их создании или повторно распределять память при изменении их размеров.

Массивы в языке JavaScript - это специализированная форма объектов, а индексы массивов означают чуть больше, чем просто имена свойств, которые по совпадению являются целыми числами.

Научная значимость данной работы состоит в описании и исследовании наиболее популярных методов сортировки на языках программирования C++, C#, Pascal и JavaScript. Практическая значимость темы «Сортировка массивов» состоит в анализе проблем реализации и использовании различных видов сортировок в зависимости от выбранного языка.

• 2 этап исследования.

Критерии оценки алгоритмов сортировки. Для каждого метода сортировки имеется много алгоритмов. Каждый алгоритм имеет свои достоинства, но в целом оценка алгоритма сортировки в значительной степени зависит от времени.

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

• 3 этап исследования.

Изучения выбранных методов сортировки (с составлением их на четырёх языках программирования).

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

Сортировка пузырьковым методом использует метод обменной сортировки. Она основана на выполнении в цикле операций сравнения и при необходимости обмена соседних элементов. Ее название происходит из-за подобия процессу движения пузырьков в резервуаре с водой, когда каждый пузырек находит свой собственный уровень.

• 4 этап исследования.

На данном этапе я сравнил  методы сортировки массивов по выбранному критерию на языках программирования C++, C#, Pascal и JavaScript.

• 5 этап исследования.

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

Исходя из того, что основным критерием эффективности алгоритма сортировки является скорость, можно сделать вывод, что:

• при использовании быстрой сортировки:

• для массива менее 100 элементов – выбор языка программирования не имеет значение;
• от 100-500 элементов  и свыше 10000 элементов – уверенно лидирует C++;
• от 500 до 1000 – можно использовать не только C++, а и C#, и Pascal.

• при использовании сортировки пузырьком:

• до 100 элементов - выбор языка программирования не имеет значение;
• от 100-1000 элементов - C++ и C#;
• от 1000 до 4000 элементов – JavaScript;
• от 4000 до 10000 элементов - C#, однако, если в массиве более 7000 элементов разницы между выбором сортировки на языке C#, C++ и JavaScrip практически не существует.

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

1. Довгаль С.И. Персональные ЭВМ: Турбо-Паскаль V6.0, Объектное программирование, Локальные сети. (учебное пособие)/, С.И. Довгаль, Б.Ю.   Литвинов, А.И. Сбитнев, - Киев: Информсистема сервис, 1993. -  210с.
2.  Дональд Кнут Искусство программирования, том 3. Сортировка и поиск = The Art of Computer Programming, vol.3. Sorting and Searching. — 2-е изд. — М.: «Вильямс», 2007. — 824 с.
3. Офицеров, Д.В. Программирование в интегрированной среде Турбо-Паскаль: Справ. пособие. /Д.В. Офицеров, В.А. Старых - Мн.: Беларусь, 1992. - 240с.
4. Павловская, Т.А. Паскаль. Программирование на языке высокого уровня: Учебник для вузов/ Т.А. Павловская – СПб.: Питер, 2006. -  123 с.
5. Стиллмен Э., Дж. Грин. Изучаем С#.– СПб.: Питер, 2012. -  704 с.
6. http://algolist.manual.ru
7. http://blogerator.ru/page/samij-vostrebovannij-populjarnij-jazyka-programmirovanija-rejting-tiobe-pypl-redmonk-statistika
8. http://info-comp.ru/programmirovanie/270-populjarnyje-jazyki-vjeb-programmirovanija.html

Анализ некоторых методов сортировок массива на

различных языках программирования

 Гаврилов Илья Викторович

Россия, Ханты – Мансийский автономный округ – Югра,

Тюменская область, г. Нягань 

Муниципальное бюджетное общеобразовательное учреждение

муниципального образования г. Нягань « Гимназия», 8-А класс

1. Теоретическая часть

1.1 Понятие сортировки

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

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

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

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

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

1.2. Анализ популярности языков программирования

Какой язык программирования самый популярный среди программистов? А какой из них лучше котируется на рынке? Подобные вопросы задают не только новички, подбирающие «наиболее удачный инструмент», в который стоит инвестировать свои время и силы. Эти вопросы волнуют и перманентно самосовершенствующихся программистов-профи, которые стремятся угнаться за постоянно меняющейся конъюнктурой рынка.

В поисках ответа рассмотрим рейтинги  разных методик оценки языков программирования.

Компания TIOBE Software выпускает один из самых популярных рейтингов языков программирования. Поэтому для начала приведем именно эти самые последние цифры:

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

Полностью по аналогии с TIOBE рейтинг PYPL выходит одновременно с ним и выдает итоговую таблицу (Top10) в полностью аналогичном формате — вот он за июль 2013:

Ниже идет сопроводительный график динамики популярности языков по версии PYPL:

Глядя на эти данные, в качестве базовой интерпретации графиков PYPL можно сделать следующие утверждения:

• популярность C# всегда колеблется в любопытной противофазе к популярности языка C в любой контрольный период;
• рост C# коррелирует с групповым падением C++ и VBasic и, скорее всего, идет за счет последних;
• рост Python коррелирует с падением Perl и, скорее всего, идет за счет последнего;
• стабильно растущими можно обозначить лишь два языка: Python и Objective-C;
• стабильно теряющими свою популярность можно назвать языки Perl и VBasic;
• языки Java и Javascript сохраняют стабильную популярность в течение уже долгого времени;
• явные лидеры рынка, популярность которых пока в стратосфере, — это Java и PHP;
• популярность нишевых конкурентов C# и Java пока несопоставима, с сильным креном в сторону Java;
• при сохранении текущего тренда Python станет популярней своего прямого рыночного конкурента PHP (на новых/текущих проектах) уже в 2015 году.

Компания Jobs Tractor постоянно мониторит все предложения о работе в Твиттере от ведущих ИТ-компаний мира. По состоянию на июль 2013 года текущая раскладка спроса вот такая:

Здесь полностью подтверждаются данные рейтинга PYPL, где в качестве наиболее востребованных фигурирует троица: Java, PHP, Objective-C. А вот дальше начинаются отличия, впрочем, не столь принципиальные.

Ниже приводится рост популярности языков в предложениях работодателей — в динамике он изменялся таким образом:

Чтобы как-то перепроверить эту статистику, я обратился к крупному агрегатору предложений о работе — indeed.com, который к тому же умеет выявлять тренды между частотой подобных предложений.

Очевидно, что лидеры в общем количестве заявок — C, Java и Javascript.

1.3 Критерии оценки алгоритмов сортировки

Для каждого метода сортировки имеется много алгоритмов. Каждый алгоритм имеет свои достоинства, но в целом оценка алгоритма сортировки зависит от времени сортировки.

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

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

1.4 Постановка задачи сортировки и методы её решения

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

Более важным для выбора алгоритма является местоположение данных - в оперативной памяти компьютера или на внешнем устройстве.

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

При разработке программы можно воспользоваться различными алгоритмами и различными языками программирования. В данной работе рассмотрены два основных метода сортировки: пузырьковая и быстрая на языках программирования C++, C#, Pascal и JavaScript.

.

1.5 Сортировка пузырьковым методом

Наиболее известной является сортировка пузырьковым методом. Ее популярность объясняется запоминающимся названием и простотой алгоритма. Однако эта сортировка является одной из самых худших среди всех когда-либо придуманных сортировок.

Сортировка пузырьковым методом использует метод обменной сортировки. Она основана на выполнении в цикле операций сравнения и при необходимости обмена соседних элементов. Ее название происходит из-за подобия процессу движения пузырьков в резервуаре с водой, когда каждый пузырек находит свой собственный уровень. Программа сортировки методом пузырька представлена в приложении I.

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

1.6 Быстрая сортировка 

Это основной алгоритм сортировки, ибо в большинстве случаев он дает наилучшие результаты (придумал Hoare). Основная идея заключается в следующем. Выберем некий элемент M внутри диапазона, например в середине. Затем все элементы большие этого числа переносятся в одну сторону, а меньшие в другую. На практике это выглядит так:

• ищем первый элемент меньший (или равный) выбранного элемента Х от начала диапазона,
• ищем первый элемент больший (или равный) выбранного элемента Х от конца диапазона,
• меняем их местами.

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

1.7 Сравнительный анализ методов сортировки на различных языках программирования

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

Исследование производилось на неотсортированном  массиве.

В результате были получены следующие данные.

По полученным данным были построены графики (приложение I, II).

Итак, какой же метод является лучшим? И от чего зависит выбор того или иного метода при решении задач на сортировку?

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

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

2. Практическая часть

В программировании довольно часто приходится при решении различного типа задач использовать тот или иной метод сортировки.

В практической части работы представлены:

• сортировки , при решении  которых используются сортировки одномерных массивов на языках программирования C++, C#, Pascal и JavaScript;
• компьютерная презентация по теме «Анализ некоторых методов сортировок массива на различных языках программирования».

Быстрая сортировка

Сортировка пузырьком

Заключение

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

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

Так, сортировка большого числа элементов пузырьковым методом потребует много времени, т.к. время выполнения сортировки находится в квадратичной зависимости от числа элементов массива. Для больших объемов данных эти сортировки будут медленными, а начиная с некоторой величины, они будут слишком медленными, чтобы их можно было использовать на практике. Однако, они идеально подходят для сортировки небольшого количества элементов. Исходя из того, что основным критерием эффективности алгоритма сортировки является скорость, можно сделать вывод, что:

• при использовании быстрой сортировки: для массива менее 100 элементов – выбор языка программирования не имеет значение; от 100-500 элементов  и свыше 10000 элементов – уверенно лидирует C++; от 500 до 1000 – можно использовать не только C++, а и C#, и Pascal;
• при использовании сортировки пузырьком: до 100 элементов - выбор языка программирования не имеет значение; от 100-1000 элементов - C++ и C#; от 1000 до 4000 элементов – JavaScript; от 4000 до 10000 элементов - C#, однако, если в массиве более 7000 элементов разницы между выбором сортировки на языке C#, C++ и JavaScrip практически не существует.

Выбор языка программирования в первую очередь зависит от круга задач – C/C++/Java/C# скорее всего не сможет заменить JavaScript для веб-страниц и наоборот.

Список используемой литературы

1.  Джордейн, Р. Справочник программиста персональных компьютеров типа IBM PC, XT и AT: Пер. с англ./ Предисл. Н.В. Гайского, 2001 – 116с.
2. Довгаль С.И. Персональные ЭВМ: Турбо-Паскаль V6.0, Объектное программирование, Локальные сети. (учебное пособие)/, С.И. Довгаль, Б.Ю.   Литвинов, А.И. Сбитнев , - Киев: Информсистема сервис, 1993. -  210с.
3.  Дональд Кнут Искусство программирования, том 3. Сортировка и поиск = The Art of Computer Programming, vol.3. Sorting and Searching. — 2-е изд. — М.: «Вильямс», 2007. — 824 с.
4. Корнеев, В.В. Современные микропроцессоры. /В.В. Корнеев, А.В. Киселев - М.: Нолидж, 1998.-376с.
5. Офицеров, Д.В. Программирование в интегрированной среде Турбо-Паскаль: Справ. пособие. /Д.В. Офицеров, В.А. Старых - Мн.: Беларусь, 1992. - 240с.
6. Павловская, Т.А. Паскаль. Программирование на языке высокого уровня: Учебник для вузов/ Т.А. Павловская – СПб.: Питер, 2006. -  123 с.
7. Перминов, О.Н. Программирование на языке Паскаль. / О.Н. Перминов - М.: Радио и связь, 1988. - 156с.
8.  Прайс, Д. Программирование на языке Паскаль: Практическое руководство. Пер. с англ./Д. Прайс - М.: Мир, 1987. - 232с.
9. Стиллмен Э., Дж. Грин. Изучаем С#.– СПб.: Питер, 2012. -  704 с.
10. http://algolist.manual.ru
11. http://blogerator.ru/page/samij-vostrebovannij-populjarnij-jazyka-programmirovanija-rejting-tiobe-pypl-redmonk-statistika

http://info-comp.ru/programmirovanie/270-populjarnyje-jazyki-vjeb-programmirovanija.html

Приложения