Количество положительных и отрицательных элементов массива
 Скачать 45.71 Kb.
|
|
АВТОНОМНАЯ НЕКОММЕРЧЕСКАЯ ПРОФЕССИОНАЛЬНАЯ ОБРАЗОВАТЕЛЬНАЯ ОРГАНИЗАЦИЯ БАШКИРСКИЙ КООПЕРАТИВНЫЙ ТЕХНИКУМ Курсовая работа на тему: Количество положительных и отрицательных элементов массива. Выполнил студент 2 курса Медведев Никита Группа СИС-1120 Руководитель Шагибалова Р.З. Дата представления: Дата защиты: Оценка: Уфа – 2021 Содержание Введение...............................................................................................................3-5 Массивы..........................................................................................................6-9 Типы массивов................................................................................................10 Двумерные массивы......................................................................................10 Многомерные массивы............................................................................10-12 Динамические массивы................................................................................12 Гетерогенные массивы.................................................................................13 Описание массивов..................................................................................13-14 Алгоритм сортировки...................................................................................15 4.1 История....................................................................................................15-16 4.2 Быстрая сортировка Хоара....................................................................16-17 4.3 Оценка алгоритма сортировки..............................................................17-18 4.4 Свойства и типы.....................................................................................18-19 Список алгоритмов сортировки..................................................................20 5.1 Алгоритмы устойчивой сортировки..........................................................20 5.2 Алгоритмы неустойчивой сортировки......................................................21 5.3 Непрактичные алгоритмы сортировки.....................................................22 5.4 Алгоритмы, не основанные на сравнениях..............................................22 6. Количества положительных и отрицательных элементов массив…23-25 Заключение..................................................................................................26 Список использованной литературы...................................................27-28 Введение. Самой распространенной структурой, реализованной практически во всех языках программирования, является массив. До сих пор мы рассматривали переменные, которые имели только одно значение, которые могли содержать в себе только одну величину определенного типа. Исключением являлись лишь строковые переменные, которые представляют собой совокупность данных символьного типа, но и при этом мы говорили о строке, как об отдельной величине. Вы знаете, что компьютер предназначен в основном для облегчения работы человека с большими информационными объемами. Поэтому во всех существующих языках имеются типы переменных, отвечающие за хранение больших массивов данных. В языке Паскаль они так и называются: "массивы". Массивом будем называть упорядоченную последовательность данных одного типа, объединенных под одним именем. Кстати, под это определение подходит множество объектов из реального мира: словарь (последовательность слов), мультфильм (последовательность картинок) и т.д. Проще всего представить себе массив в виде таблицы, где каждая величина находится в собственной ячейке. Положение ячейки в таблице должно однозначно определяться набором координат (индексов). Самой простой является линейная таблица, в которой для точного указания на элемент данных достаточно знания только одного числа (индекса). Мы с вами пока будем заниматься только линейными массивами, так как более сложные структуры строятся на их основе. Единственным действием, которое возможно произвести с массивом целиком - присваивание. Однако, присваивать можно только массивы одинаковых типов. Никаких других операций с массивами целиком произвести невозможно, но с элементами массивов можно работать точно также, как с простыми переменными соответствующего типа. Обращение к отдельному элементу массива производится при помощи указания имени всего массива и в квадратных скобках - индекса конкретного элемента. На данный момент существует множество алгоритмов сортировки данных. Зачастую выбор алгоритма решения задачи зависит от структуры сортируемых данных. В случае сортировки эта зависимость имеет большое значение, и методы сортировки обычно разделяют на две категории: - Сортировка массивов (внутренняя сортировка) - Сортировка последовательных файлов (внешняя сортировка) При внутренней сортировке массивы располагаются в оперативной памяти ЭВМ, что обеспечивает быстрый произвольный доступ к данным.При внешней сортировке файлы хранятся в более "медленной", но более вместительной внешней памяти, т.е. на запоминающих устройствах с механическим передвижением (магнитных дисках и других носителях). Критериями оценки методов сортировки являются: - количество операций сравнения пар ключей - число перестановок элементов - экономное использование памяти Цель курсовой работы: Систематизация, углубление и активное применение знаний по программированию в среде С++ Рассмотреть основные алгоритмы сортировки. Разработать, протестировать и проанализировать алгоритмы сортировки методом простых вставок и методом пузырькаОценить производительность данных алгоритмов и сравнить их между собой по различным характеристикам. С помощью ЭВМ можно решать самые разные задачи, в том числе автоматически выполнять требуемую сортировку данных. Сортировка может требоваться в различных ситуациях, например когда нужно отобразить визуально распределение данных. Для различных данных существуют определенные методы сортировок повышающие производительность и скорость сортировки именно для этого типа данных. Рассматриваемые в данной работе сортировки методы сортировки являются относительно простыми, и хотя их эффективность ниже чем у более сложных и совершенных методов, но они так же имеют ряд преимуществ, и к тому же лежат в основе большинства других методов сортировки. Рассматриваемые методы сортировок в силу своей простоты особенно хорошо подходят для изучения свойств большинства принципов сортировки, программы, основанные на данных методах легки для понимания и коротки (это также позволяет экономить память, занимаемую программой). Так же важно отметить, что хотя сложные алгоритмы требуют меньшего числа операций, но эти операции являются более сложными. Поэтому при относительно малом количестве сортируемых элементов простые методы сортировки работают достаточно быстро. Массивы Массив — структура данных, хранящая набор значений (элементов массива), идентифицируемых по индексу или набору индексов, принимающих целые (или приводимые к целым) значения из некоторого заданного непрерывного диапазона. Одномерный массив можно рассматривать как реализацию абстрактного типа данных — вектор. Размерность массива — это количество индексов, необходимое для однозначной адресации элемента в рамках массива. По количеству используемых индексов массивы делятся на одномерные, двумерные, трёхмерные и т. д. Форма или структура массива — сведения о количестве размерностей и размере (протяжённости) массива по каждой из размерностей может быть представлена одномерным массивом. Особенностью массива как структуры данных (в отличие, например, от связного списка) является константная вычислительная сложность доступа к элементу массива по индексу. Массив относится к структурам данных с произвольным доступом. В простейшем случае массив имеет константную длину по всем размерностям и может хранить данные только одного, заданного при описании, типа. Ряд языков поддерживает также динамические массивы, длина которых может изменяться по ходу работы программы, и гетерогенные массивы, которые могут в разных элементах хранить данные различных типов. Массивы состоят из ограниченного числа компонент, причем все компоненты массива имеют один и тот же тип, называемый базовым. Структура массива всегда однородна. Массив может состоять из элементов типа integer, real или char, либо других однотипных элементов. Из этого, правда, не следует делать вывод, что компоненты массива могут иметь только скалярный тип. Другая особенность массива состоит в том, что к любой его компоненте можно обращаться произвольным образом. Программа может сразу получить нужный ей элемент по его порядковому номеру (индексу). Индекс - это переменная типа INTEGER. В одномерном массиве элементы массива нумеруются одним индексом. Нужно четко понимать, что индекс ячейки массива не является ее содержимым. Содержимым являются хранимые в ячейках данные, а индексы только указывают на них. Действия в программе над массивом осуществляются путем использования имени переменной, связанной с областью данных, отведенной под массив. Массивом называется набор данных одного типа, расположенный в оперативной памяти. К элементу массива можно обратиться по его индексу (номеру). В памяти ЭВМ все элементы массива располагаются подряд. Каждый из индексов массива находится в некотором диапазоне (<нач. элемент>…<кон. элемент>). Причем конечный элемент больше либо равен начальному элементу. В качестве диапазона можно использовать: Integer, Char, Boolean. Очень часто это целочисленный тип (integer, word или byte), но может быть и логический и символьный. У разных массивов типы данных могут различаться. Например, один массив может состоять из чисел типа integer, а другой - из чисел типа real. Массив в языкет Паскаль это сложный тип данных, поэтому чаще всего его описывают в разделе переменных. <переем. массив>: array[<диапазон 1>..<диапазон N>]<тип переменной>; В языке Паскаль тип массива задается с использованием специального слова array (англ. - массив), и его объявление в программе выглядит следующим образом: Type < имя _ типа >= array [ I ] of T; где I - тип индекса массива, T - тип его элементов. Можно описывать сразу переменные типа массив, т.е. в разделе описания переменных: Var a,b: array [ I ] of T; Обычно тип индекса характеризуется некоторым диапазоном значений любого порядкового типа : I 1.. I n. Например, индексы могут изменяться в диапазоне 1..20 или ‘ a ’..’ n ’. При этом длину массива Паскаля характеризует выражение: (I n)- ord (I 1)+1. Для того чтобы ввести значения элементов массива, необходимо последовательно изменять значение индекса, начиная с первого до последнего, и вводить соответствующий элемент. Для реализации этих действий удобно использовать цикл с заданным числом повторений, т.е. простой арифметический цикл, где параметром цикла будет выступать переменная - индекс массива Паскаля. Значения элементов могут быть введены с клавиатуры или определены с помощью оператора присваивания. Массив состоит из нескольких элементов. Ко всему массиву можно обращаться по его имени. Можно обращаться к его элементу, но для этого надо задать индекс (индексы). Для объявления массива необходимо задать типы его индексов и компонент: Все компоненты должны быть одного и того же типа, который называют типом компонент или базовым (для массива) типом. Тип данных Массив позволяет одному идентификатору задать несколько значений, которые отличаются порядковым номером. Номер элемента массива указывается после идентификатора в квадратных скобках {M[5] - пятый элемент массива М}. При описании массива указывается диапазон номеров элементов массива и тип, к которому относится каждый его элемент. Массив — упорядоченный набор элементов, каждый из которых хранит одно значение, идентифицируемое с помощью одного или нескольких индексов. В простейшем случае массив имеет постоянную длину и хранит единицы данных одного и того же типа, а в качестве индексов выступают целые числа. Количество используемых индексов массива может быть различным: массивы с одним индексом называют одномерными, с двумя — двумерными, и т. д. Одномерный массив — нестрого соответствует вектору в математике; двумерный («строка», «столбец»)— матрице. Чаще всего применяются массивы с одним или двумя индексами; реже — с тремя; ещё большее количество индексов — встречается крайне редко. В некоторых языках программирования многомерные массивы создаются на основе одномерных, у которых элементы являются массивами. Поддержка индексных массивов (свой синтаксис объявления, функции для работы с элементами и т. д.) есть в большинстве высокоуровневых языков программирования. Максимально допустимая размерность массива, типы и диапазоны значений индексов, ограничения на типы элементов определяются языком программирования и (или) конкретным транслятором. В языках программирования, допускающих объявления программистом собственных типов, как правило, существует возможность создания типа «массив». В определении такого типа задаются типы и/или диапазоны значений каждого из индексов и тип элементов массива. Объявленный тип в дальнейшем может использоваться для определения переменных, формальных параметров и возвращаемых значений функций. Некоторые языки поддерживают для переменных-массивов операции присваивания (когда одной операцией всем элементам массива присваиваются значения соответствующих элементов другого массива). В языке программирования APL массив является основным типом данных (при этом нуль-мерный массив называется скаляром, одномерный — вектором, двумерный — матрицей). Помимо присваивания массивов в этом языке поддерживаются операции векторной и матричной арифметики, каждая из которых выполняется одной командой, операции сдвига данных в массивах, сортировка строк матрицы и т. п. Типы массивов. 2.1 Двумерные массивы. Двумерный массив (прямоугольная таблица (матрица, набор векторов)) - это пример массива, в котором элементы нумеруются двумя индексами, элемент которого зависит от его местоположения в строке и в столбце. В качестве номера (индекса) элемента массива используется выражение порядкового типа (чаще integer). Для определения позиции элемента в двумерном массиве необходимы два индекса. Любой двумерный массив есть матрица, а матрица есть таблица. Поэтому удобно описывать двумерные массивы путем указания границ изменения индексов (номеров) строк и столбцов. Например, таблица символов M × N, где M - число строк и N - число столбцов, может быть описана: 2.2 Многомерные массивы. Многомерный массив - это массив массивов, т. е. массив, элементами которого являются массивы. Размерность массива - это количество индексов, используемых для ссылки на конкретный элемент массива. Многомерные массивы объявляются точно так же, как и одномерные, только после имени массива ставится более одной пары квадратных скобок. Фактически двухмерный массив представляется как одномерный, элементы которого тоже массивы. Константное выражение, определяющее одну из размерностей массива, не может принимать нулевое значение: mas[0][7]; // ошибкаmas[l][7]; // правильно Можно инициализировать и многомерные массивы. Причем инициализация происходит построчно, т. е. в порядке возрастания самого правого индекса. Именно в таком порядке элементы многомерных массивов располагаются в памяти компьютера. Для примера рассмотрим, как будет выполнена инициализация трехмерного массива с восемью элементами:array[2][2][2]={23, 54, 16, 43, 82, 12, 9, 75}; Проинициализированный массив будет выглядеть так: [0][0][0]= =23; [0][0][1]= =54; [0][1][0]= =16; …….. [1][1][0]= =9; [1][1][1]= =75; Для наглядности при инициализации двухмерного массива список начальных значений следует оформлять в виде таблицы: int array[3][3]={ 34, 23, 67, 38, 56, 73, 37,94,28}; Многомерные массивы могут инициализироваться и без указания одной (самой левой) из размерностей массива. В этом случае количество элементов компилятор определяет по количеству членов в списке инициализации. Например, для массива array будет получен тот же, что и в предыдущем примере результат: int array[][3]={ 34, 23, 67, 38, 56, 73, 37,94,28}; Если необходимо проинициализировать не все элементы строки, а только несколько первых элементов, то в списке инициализации можно использовать фигурные скобки, охватывающие значения для этой строки. Например, если необходимо для массива array задать начальные значения для элементов array[0][0], array[l][0], array[l][l], array[2][0], array[2][l], array[2][2], то это можно сделать следующим образом: int array[][3]={{0}, {Ю,П}, {21,21,22}}; Здесь переменной int присваивается значение третьего элемента второй строки. 2.3 Динамические массивы. Динамическим называется массив, размер которого может изменяться вовремя исполнения программы. Возможность изменения размера отличает динамический массив от статического, размер которого задаётся на момент компиляции программы. Для изменения размера динамического массива язык программирования, поддерживающий такие массивы, должен предоставлять встроенную функцию или оператор. Динамические массивы дают возможность более гибкой работы с данными, так как позволяют не прогнозировать хранимые объёмы данных, а регулировать размер массива в соответствии с реально необходимыми объёмами. Также иногда к динамическим относят массивы переменной длины, размер которых не фиксируется при компиляции, а задаётся при создании или инициализации массива во время исполнения программы. От «настоящих» динамических массивов они отличаются тем, что для них не предоставляются средства автоматического изменения размера с сохранением содержимого, так что при необходимости программист должен реализовать такие средства самостоятельно. 2.4 Гетерогенные массивы. Гетерогенным называется массив, в разные элементы которого могут быть непосредственно записаны значения, относящиеся к различным типам данных. Массив, хранящий указатели на значения различных типов, не является гетерогенным, так как собственно хранящиеся в массиве данные относятся к единственному типу -- типу «указатель». Гетерогенные массивы удобны как универсальная структура для хранения наборов данных произвольных типов. Отсутствие их поддержки в языке программирования приводит к необходимости реализации более сложных схем хранения данных. С другой стороны, реализация гетерогенности требует усложнения механизма поддержки массивов в трансляторе языка. Гетерогенный массив как встроенный тип данных присутствует в языке PHP. Описание массивов. Можно инициализировать и многомерные массивы. Причем инициализация происходит построчно, т. е. в порядке возрастания самого правого индекса. Именно в таком порядке элементы многомерных массивов располагаются в памяти компьютера. Для примера рассмотрим, как будет выполнена инициализация трехмерного массива с восемью элементами:array[2][2][2]={23, 54, 16, 43, 82, 12, 9, 75}; Проинициализированный массив будет выглядеть так: [0][0][0]= =23; [0][0][1]= =54; [0][1][0]= =16; …….. [1][1][0]= =9; [1][1][1]= =75; Для наглядности при инициализации двухмерного массива список начальных значений следует оформлять в виде таблицы: int array[3][3]={ 34, 23, 67, 38, 56, 73, 37,94,28}; Многомерные массивы могут инициализироваться и без указания одной (самой левой) из размерностей массива. В этом случае количество элементов компилятор определяет по количеству членов в списке инициализации. Например, для массива array будет получен тот же, что и в предыдущем примере результат: int array[][3]={ 34, 23, 67, 38, 56, 73, 37,94,28}; Если необходимо проинициализировать не все элементы строки, а только несколько первых элементов, то в списке инициализации можно использовать фигурные скобки, охватывающие значения для этой строки. Например, если необходимо для массива array задать начальные значения для элементов array[0][0], array[l][0], array[l][l], array[2][0], array[2][l], array[2][2], то это можно сделать следующим образом: int array[][3]={{0}, {Ю,П}, {21,21,22}}; Здесь переменной int присваивается значение третьего элемента второй строки. Каждый из индексов массива находится в некотором диапазоне (<нач. элемент>…<кон. элемент>). Причем конечный элемент больше либо равен начальному элементу. В качестве диапазона можно использовать: Integer, Char, Boolean. Массив в языке Паскаль это сложный тип данных, поэтому чаще всего его описывают в разделе переменных. <переем. массив>: array[<диапазон 1>..<диапазон N>]<тип переменной>; Пример: список студентов группыSpisok: array[1..40] String[20]; Алгоритм сортировки. Алгоритм сортировки - это алгоритм для упорядочивания элементов в массиве. В случае, когда элемент в массиве имеет несколько полей, поле, служащее критерием порядка, называется ключом сортировки. На практике в качестве ключа часто выступает число, а в остальных полях хранятся какие-либо данные, никак не влияющие на работу алгоритма. 4.1 История. Первые прототипы современных методов сортировки появились уже в XIX веке. К 1890 году для ускорения обработки данных переписи населения в США американец Герман Холлерит создал первый статистический табулятор — электромеханическую машину, предназначенную для автоматической обработки информации, записанной на перфокартах. У машины Холлерита имелся специальный «сортировальный ящик» из 26 внутренних отделений. При работе с машиной от оператора требовалось вставить перфокарту и опустить рукоятку. Благодаря пробитым на перфокарте отверстиям замыкалась определённая электрическая цепь, и на единицу увеличивалось показание связанного с ней циферблата. Одновременно с этим открывалась одна из 26 крышек сортировального ящика, и в соответствующее отделение перемещалась перфокарта, после чего крышка закрывалась. Данная машина позволила обрабатывать около 50 карт в минуту, что ускорило обработку данных в 3 раза. К переписи населения 1900 года Холлерит усовершенствовал машину, автоматизировав подачу карт. Работа сортировальной машины Холлерита основывалась на методах поразрядной сортировки. В патенте на машину обозначена сортировка «по отдельности для каждого столбца», но не определён порядок. В другой аналогичной машине, запатентованной в 1894 году Джоном Гором, упоминается сортировка со столбца десятков. Метод сортировки, начиная со столбца единиц, впервые появляется в литературе в конце 1930-х годов. К этому времени сортировальные машины уже позволяли обрабатывать до 400 карт в минуту. 4.2 Быстрая сортировка Хоара. К 1952 году на практике уже применялись многие методы внутренней сортировки, но теория была развита сравнительно слабо. В октябре 1952 года Даниэль Гольденберг привёл пять методов сортировки с анализом наилучшего и наихудшего случаев для каждого из них. В 1954 году Гарольд Сьюворд развил идеи Гольденберга, а также проанализировал методы внешней сортировки. Говард Демут в 1956 году рассмотрел три абстрактные модели задачи сортировки: с использованием циклической памяти, линейной памяти и памяти с произвольным доступом. Для каждой из этих задач автор предложил оптимальные или почти оптимальные методы сортировки, что помогло связать теорию с практикой. Из-за малого числа людей, связанных с вычислительной техникой, эти доклады не появлялись в «открытой литературе». Первой большой обзорной статьёй о сортировке, появившейся в печати в 1955 году, стала работа Дж. Хоскена, в которой он описал всё имевшееся на тот момент оборудование специального назначения и методы сортировки для ЭВМ, основываясь на брошюрах фирм-изготовителей. В 1956 году Э. Френд в своей работе проанализировал математические свойства большого числа алгоритмов внутренней и внешней сортировки, предложив некоторые новые методы. После этого было предложено множество различных алгоритмов сортировки: например, вычисление адреса в 1956 году; слияние с вставкой, обменная поразрядная сортировка, каскадное слияние и метод Шелла в 1959 году, многофазное слияние и вставки в дерево в 1960 году, осциллирующая сортировка и быстрая сортировка Хоара в 1962 году, пирамидальная сортировка Уильямса и обменная сортировка со слиянием Бэтчера в 1964 году. В конце 60-х годов произошло и интенсивное развитие теории сортировки. Появившиеся позже алгоритмы во многом являлись вариациями уже известных методов. Получили распространение адаптивные методы сортировки, ориентированные на более быстрое выполнение в случаях, когда входная последовательность удовлетворяет заранее установленным критериям. 4.3 Оценка алгоритма сортировки. Алгоритмы сортировки оцениваются по скорости выполнения и эффективности использования памяти: - Время — основной параметр, характеризующий быстродействие алгоритма. Называется также вычислительной сложностью. Для упорядочения важны худшее, среднее и лучшее поведение алгоритма в терминах мощности входного множества A. Если на вход алгоритму подаётся множество A, то обозначим n = |A|. Для типичного алгоритма хорошее поведение — это O(n log n) и плохое поведение — это O(n2). Идеальное поведение для упорядочения — O(n). Алгоритмы сортировки, использующие только абстрактную операцию сравнения ключей, всегда нуждаются по меньшей мере в сравнениях. Тем не менее, существует алгоритм сортировки Хана (Yijie Han) с вычислительной сложностью O(n log log n), использующий тот факт, что пространство ключей ограничено (он чрезвычайно сложен, а за О-обозначением скрывается весьма большой коэффициент, что делает невозможным его применение в повседневной практике). Также существует понятие сортирующих сетей. Предполагая, что можно одновременно (например, при параллельном вычислении) проводить несколько сравнений, можно отсортировать n чисел за O(log2 n) операций. При этом число n должно быть заранее известно. - Память — ряд алгоритмов требует выделения дополнительной памяти под временное хранение данных. Как правило, эти алгоритмы требуют O(log n) памяти. При оценке не учитывается место, которое занимает исходный массив и независящие от входной последовательности затраты, например, на хранение кода программы (так как всё это потребляет O(1)). Алгоритмы сортировки, не потребляющие дополнительной памяти, относят к сортировкам на месте. 4.4 Свойства и типы. Устойчивость — устойчивая сортировка не меняет взаимного расположения элементов с одинаковыми ключами. Естественность поведения — эффективность метода при обработке уже упорядоченных или частично упорядоченных данных. Алгоритм ведёт себя естественно, если учитывает эту характеристику входной последовательности и работает лучше. Использование операции сравнения. Алгоритмы, использующие для сортировки сравнение элементов между собой, называются основанными на сравнениях. Минимальная трудоемкость худшего случая для этих алгоритмов составляет {\displaystyle O}O({\displaystyle n\cdot \log n}n\cdot \log n), но они отличаются гибкостью применения. Для специальных случаев (типов данных) существуют более эффективные алгоритмы. Ещё одним важным свойством алгоритма является его сфера применения. Здесь основных типов упорядочения два: - Внутренняя сортировка оперирует массивами, целиком помещающимися в оперативной памяти с произвольным доступом к любой ячейке. Данные обычно упорядочиваются на том же месте без дополнительных затрат. В современных архитектурах персональных компьютеров широко применяется подкачка и кэширование памяти. Алгоритм сортировки должен хорошо сочетаться с применяемыми алгоритмами кэширования и подкачки. - Внешняя сортировка оперирует запоминающими устройствами большого объёма, но не с произвольным доступом, а последовательным (упорядочение файлов), то есть в данный момент «виден» только один элемент, а затраты на перемотку по сравнению с памятью неоправданно велики. Это накладывает некоторые дополнительные ограничения на алгоритм и приводит к специальным методам упорядочения, обычно использующим дополнительное дисковое пространство. Кроме того, доступ к данным во внешней памяти производится намного медленнее, чем операции с оперативной памятью. - Доступ к носителю осуществляется последовательным образом: в каждый момент времени можно считать или записать только элемент, следующий за текущим. - Объём данных не позволяет им разместиться в ОЗУ. Также алгоритмы классифицируются по: - потребности в дополнительной памяти или её отсутствию - потребности в знаниях о структуре данных, выходящих за рамки операции сравнения, или отсутствию таковой Список алгоритмов сортировки. 5.1 Алгоритмы устойчивой сортировки. - Сортировка пузырьком (англ. Bubble sort) — для каждой пары индексов производится обмен, если элементы расположены не по порядку. Сложность алгоритма: O(n^2). - Сортировка перемешиванием (англ. Cocktail sort). Сложность алгоритма: O(n^2). - Сортировка вставками (англ. Insertion sort) — определяем, где текущий элемент должен находиться в упорядоченном списке, и вставляем его туда. Сложность алгоритма: O(n^2). - Гномья сортировка (англ. Gnome sort; первоначально опубликована под названием «глупая сортировка» [stupid sort] за простоту реализации) — сходна с сортировкой вставками. Сложность алгоритма — O(n^2).; рекурсивная версия требует дополнительно O(n^2) памяти. - Сортировка слиянием (англ. Merge sort) — выстраиваем первую и вторую половину списка отдельно, а затем объединяем упорядоченные списки. Сложность алгоритма: O(nlog n). Требуется O(n) дополнительной памяти. - Сортировка с помощью двоичного дерева (англ. Tree sort). Сложность алгоритма: O(n\log n) в лучшем случае, а O(n^2) в худшем. Требуется O(n) дополнительной памяти. - Сортировка Timsort (англ. Timsort) — комбинированный алгоритм (используется сортировка вставками и сортировка слиянием). Сложность алгоритма: O(n\log n) Требуется O(n) дополнительной памяти. Разработан для использования в языке Python. 5.2 Алгоритмы неустойчивой сортировки. - Сортировка выбором (англ. Selection sort) — поиск наименьшего или наибольшего элемента и помещение его в начало или конец упорядоченного списка. Сложность алгоритма: O(n^2) - Сортировка расчёской (англ. Comb sort) — сложность алгоритма: O(n^2); улучшение сортировки пузырьком. - Сортировка Шелла (англ. Shell sort) — улучшение сортировки вставками. Сложность алгоритма меняется в зависимости от выбора последовательности длин промежутков; при определённом выборе. - Пирамидальная сортировка (сортировка кучи, Heapsort) — сложность алгоритма: O(n\log n) превращаем список в кучу, берём наибольший элемент и добавляем его в конец списка. - Плавная сортировка (англ. Smoothsort) — сложность алгоритма O(n\log n) - Быстрая сортировка (англ. Quicksort), в варианте с минимальными затратами памяти — сложность алгоритма: O(n\log n) — среднее время, O(n^2) — худший случай; широко известен как быстрейший из известных для упорядочения больших случайных списков; с разбиением исходного набора данных на две половины так, что любой элемент первой половины упорядочен относительно любого элемента второй половины; затем алгоритм применяется рекурсивно к каждой половине. При использовании O(n) дополнительной памяти можно сделать сортировку устойчивой. - Интроспективная сортировка (англ. Introsort) — сложность алгоритма: O(n\log n), сочетание быстрой и пирамидальной сортировки. Пирамидальная сортировка применяется в случае, если глубина рекурсии превышает log n. - Терпеливая сортировка (англ. Patience sorting) — сложность алгоритма: O(n\log n) — наихудший случай, требует дополнительно O(n) памяти, также находит самую длинную увеличивающуюся подпоследовательность. - Stooge sort — рекурсивный алгоритм сортировки 5.3 Непрактичные алгоритмы сортировки. - Bogosort (также глупая сортировка, stupid sort) — O(n\cdot n!) в среднем. Произвольно перемешать массив, проверить порядок. - Сортировка перестановкой — O(n^2\cdot n!) — худшее время. Для каждой пары осуществляется проверка верного порядка и генерируются всевозможные перестановки исходного массива. - Гравитационная сортировка (англ. Bead sort) — O(\sqrt n), требуется специализированное аппаратное обеспечение. - Блинная сортировка (англ. Pancake sorting) — O(n), требуется специализированное аппаратное обеспечение. 5.4 Алгоритмы, не основанные на сравнениях. - Блочная сортировка (Корзинная сортировка, англ. Bucket sort) — требуется O(k) дополнительной памяти и знание о природе сортируемых данных, выходящее за рамки функций «переставить» и «сравнить». Сложность алгоритма: O(n). - Поразрядная сортировка (она же цифровая сортировка, англ. Radix sort) — сложность алгоритма: O(nk); требуется O(k) дополнительной памяти. - Сортировка подсчётом (англ. Counting sort). Сложность алгоритма: O(n+k). Требуется O(n+k) дополнительной памяти. Количества отрицательных и положительных элементов в массиве.Задача.В заданном массиве чисел найти (посчитать) количество положительных и количество отрицательных элементов. Например, задан массив целых чисел [10, -5, 3, 2, 0, -1, 8, 0, 10, 3]. В нем 6 положительных и 2 отрицательных элемента (нули ни к тем, ни к другим не относятся). Решение.Для решения данной задачи введем две переменные (pos и neg) для подсчета количества соответственно положительных и отрицательных элементов массива. Будем проверять очередной элемент-число в том же цикле, в котором массив заполняется. Если элемент меньше нуля, значит будем увеличивать на 1 переменную neg. Иначе, если элемент меньше нуля - будем увеличивать pos. Мы не можем опустить проверку на положительность (которая идет второй), ведь число может оказаться равным нулю, и в таком случае никакую переменную счетчик увеличивать не надо. После завершения цикла остается только вывести на экран значения переменных pos и neg, которые содержат количества положительных и отрицательных элементов массива. Исходный код программы поиска количества положительных и отрицательных элементов массива на языке Pascal: const N = 30; var a: array[1..N] of integer; i, pos, neg: byte; begin randomize; pos := 0; neg := 0; for i:=1 to N do begin a[i] := random(100) - 50; write(a[i]:4); if a[i] < 0 then neg := neg + 1 else if a[i] > 0 then pos := pos + 1; end; writeln; writeln('Положительных: ', pos); writeln('Отрицательных: ', neg); end. Заключение. Итак, мы изучили раздел «Массивы» и узнали что массив - это именованная группа однотипных данных, хранящихся в последовательных ячейках памяти. Узнали, что массивы бывают следующих видов: одномерные, двухмерные, динамические и гетерогенные. Чтобы составить массив необходимо задать типы его индексов и компоненты. Эти типы данных массивов позволяет одному идентификатору задать несколько значений, которые отличаются порядковым номером. Номер элемента массива указывается после идентификатора в квадратных скобках {M[5] - пятый элемент массива М}. При описании массива указывается диапазон номеров элементов массива и тип, к которому относится каждый его элемент. Единственным действием, которое возможно произвести с массивом целиком это присваивание. Однако, присваивать можно только массивы одинаковых типов. В языке Паскаль тип массива задается с использованием специального слова array. Каждый элемент массива - это переменная, которой можно присваивать значения в операторах и функциях. Для того, чтобы указать элемент массива, необходимо записать все его индексы. После объявления массива каждый его элемент можно обработать, указав идентификатор (имя) массива и индекс элемента в квадратных скобках. Массив в языке Паскаль это сложный тип данных, поэтому чаще всего его описывают в разделе переменных. Массив нельзя ввести с клавиатуры одной командой, для этого организовывается цикл с параметром. При выводе массива в строку нужно использовать Write, которая будет находиться в цикле с параметром, а после цикла нужно поставить WriteLn. Над массивами нельзя выполнять арифметические действия (вычитать, складывать и др.). Все действия при составлении массива нужно выполнять поэлементно. Список использованной литературы. 1. В. В. Фаронов, Turbo Pascal в подлиннике, BHV-Санкт-Петербург, 2004. 1056 стр. 2. С. А. Немнюгин, Turbo Pascal. Программирование на языке высокого уровня: Учебник для вузов, 2-е издание, Питер, 2005. - 544 стр. 3. С. А. Немнюгин, Turbo Pascal:Практикум, 2-е издание, Питер, 2004. - 272 стр. 4. Т. А. Павловская, Паскаль. Программирование на языке высокого уровня: Учебник для вузов, Питер, 2004. - 400 стр. 5. В. И. Грызлов, Т. П. Грызлова, Турбо Паскаль 7.0. Учебный курс, Питер, 2004. - 416 стр. 6. В. Кораблев, Турбо Паскаль 7.0. Самоучитель, 16-е издание, Питер, 2004. - 480 стр. 7. Демичев Е.М. Основы программирования. 2005 8. Стивен Прата. Язык программирования Паскаль. 2006 9. Мильвидский А. М. Введение в Java. 1998 10. М. Плискин Эволюция языков программирования, 2002 11. Мясников В.А., Майоров С.А. ЭВМ для всех.. 1985 12. Львовский М.Б. Методическое пособие «BOOK» по информатике для 9-11 классов. 13. Поляков Д. Б., Круглое И. Ю. Программирование в среде Турбо Паскаль: М., 1992. 14. Хершель Р. Турбо Паскаль. Вологда, 1991. 15. Дузелбаев С.Т., Омарбекова А.С., Шарипбаева А.А., Юсубекова С.О. Основы алгоритмизации и программирования, Астана, Фолиант, 2008 16. Карпиленко Е.В., Основы программирования, Ростов н/Д, Феникс, 2007. 17. http://www.cyberforum.ru 18. http://www.knowledge.allbest.ru 19. http://www.twirpx.com |