Метод прямого выбора паскаль

Одномерные массивы: задачи сортировок элементов массива

Сортировка методом простого выбора (простой перебор)

Это наиболее естественный алгоритм упорядочивания. При данной сортировке из массива выбирается элемент с наименьшим значением и обменивается с первым элементом. Затем из оставшихся n — 1 элементов снова выбирается элемент с наименьшим ключом и обменивается со вторым элементом, и т.д. ( рис. 12.2)

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

Как и в пузырьковой сортировке , внешний цикл выполняется n-1 раз, а внутренний – в среднем n/2 раз. Следовательно, сортировка методом простого выбора требует

Сортировка методом простого включения (сдвиг-вставка, вставками, вставка и сдвиг)

Хотя этот метод сортировки намного менее эффективен, чем сложные алгоритмы (такие как быстрая сортировка ), у него есть ряд преимуществ:

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

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

В отличие от пузырьковой сортировки и сортировки простого выбора, количество сравнений в сортировке вставками зависит от изначальной упорядоченности списка. Если список уже отсортирован, количество сравнений равно n-1 ; в противном случае его производительность является величиной порядка n 2 .

Ключевые термины

Ключ сортировки – это часть данных, определяющая порядок элементов.

Сортировка – это упорядочивание набора однотипных данных по возрастанию или убыванию.

Сортировка методом «пузырька» – это алгоритм попарного сравнения элементов одномерного массива.

Сортировка методом простого включения – это алгоритм последовательного помещения элемента массива в отсортированную часть в соответствии с ключом сортировки .

Сортировка методом простого выбора – это алгоритм последовательного обмена минимального и первого элементов неотсортированной части массива.

Реализация алгоритмов сортировок включением и выбором при написании программы на Паскале

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

Краткие теоретические сведения

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

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

a[1] a[2] a[3] . . . a[N]

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

Методы внутренней сортировки

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

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

Сортировки включением

Сортировка прямым включением.Элементы условно разделяют на готовую a[1]. a[i-1] и входную последовательности a[i]. a[n]. Сначала i=2. На каждом шаге, увеличивая i на единицу, берут i-й элемент входной последовательности и передают в готовую последовательность, вставляя на подходящее место.

Итак, в начале рассматривается второй элемент (i=2) последовательности ключей. Он сравнивается с первым элементом (a[i-1]) и если он его меньше, то они меняются местами. В противном случае проход заканчивается, i увеличивается на 1 и процесс повторяется. Заметим, что упорядоченная последовательность a[i-1] называется готовой последовательностью и новый элемент вставляется в готовую последовательность на свое место.

На каждом проходе происходит перемещение i-того элемента в готовую последовательность, а некоторое число элементов сдвигается вправо. Данный процесс перемещения называется просачиванием элемента.

Здесь и далее, во всех процедурах сортировки ключи упорядочиваются по возрастанию. На входе процедур — количество элементов массива (n), на выходе — упорядоченный массив элементов(а).

Procedure Straight_Insertion(n:integer; Var a:t);

Уроки 58 — 61
Сортировка массива
(§ 21. Сортировка массива)
Составление программы на Паскале сортировки массива
Тест по теме «Программное управление работой компьютера»

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

§ 21. Сортировка массива. Программа на Паскале сортировки методом пузырька

§ 21. Сортировка массива
Программа на Паскале сортировки методом пузырька

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

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

Вывод результатов на экран организован так, чтобы на экране номера мест, занятых командами, названия команд и набранные очки выводились в три ровных столбца. Названия разных команд имеют разную длину. Самое длинное название у команды ТОРПЕДО-МЕТАЛЛУРГ состоит из 17 символов. Для выравнивания длин строк каждое название дополняется пробелами до 18 символов. Число добавляемых пробелов вычисляется так:

Здесь length ( ) — это стандартная функция, вычисляющая длину строки (число символов), указанной в скобках. Например, для ЦСКА длина строки равна 4, а для ТОРПЕДО-МЕТАЛЛУРГ длина равна 17. Значит, к ЦСКА добавится 14 пробелов, а к ТОРПЕДО-МЕТАЛЛУРГ — 1 пробел.

В операторе Team [I] : = Team [I] + ‘ ‘; используется операция «+» присоединения символов. В данном случае присоединяется пробел. К строке Team [l] добавится столько пробелов, сколько раз повторится присоединение. После этого по команде

Writeln(1:2,’ ‘,Team[I]:18, B[I]:2)

в ровные колонки выведутся места, названия команд и очки. Результаты будут иметь на экране следующий вид:

Демонстрации к уроку

Коротко о главном

Метод пузырька — алгоритм сортировки числового массива.

Структура алгоритма метода пузырька — два вложенных цикла с переменной длиной внутреннего цикла.

length() — функция определения длины строковой переменной.

В Паскале существует операция присоединения строк. Ее знак — «+».

Вопросы и задания

1. Как пояснить название метода сортировки массива — «метод пузырька»?

2. Сколько проходов с перестановками элементов потребуется при сортировке массива из 100 чисел?

3. Введите в компьютер программу Premier_liga_2.

а) Выполните ее, получите результаты. Сравните с результатами, приведенными в параграфе.

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

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

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

5. Условие то же, что и в предыдущем задании. Но в качестве исходных данных вводится еще два массива: с числом забитых и пропущенных мячей каждой командой.

Следующая страница Компьютерный практикум ЦОР. Сортировка массива (Задание 1 — 4)

Метод парных перестановок на языке Паскаль

Как организовать дистанционное обучение во время карантина?

Помогает проект «Инфоурок»

Описание презентации по отдельным слайдам:

Сортировка в одномерных массивах (10 класс)

Сортировка в массиве осуществляется следующим образом: Под сортировкой понимают упорядочивание элементов. Возможны следующие виды сортировки: — по возрастанию элементов (каждый следующий больше предыдущего); — по убыванию элементов (каждый следующий меньше предыдущего); — не убыванию элементов (каждый следующий больше или равен предыдущему); — не возрастанию элементов (каждый следующий меньше или равен предыдущему). Существует много алгоритмов сортировки. Разберём два из них: метод парных перестановок (пузырьковый) и метод прямого выбора.

Метод парных перестановок Смысл этого метода заключается в сравнивании соседних элементов и, если нужно, их перестановке. Причём за один просмотр всех пар сортировка не достигает нужного результата. Приходится просматривать все пары элементов несколько раз. Задача1. Отсортировать по возрастанию 5 элементов одномерного массива. Ввод массива осуществить любым способом. Пусть массив называется M, счётчик элементов I, количество элементов в нём N, количество повторов для просмотра всех пар соседних элементов J, ячейка для обмена B. Формирование (ввод) и печать (вывод) массива рассматривались ранее. Поэтому подробно эти действия рассматриваться не будут.

Алгоритм. Объявить и сформировать массив. Отобразить исходный массив. Для каждого J от 1 до N-1 повторять: Для каждого I от 1 до N-1 повторять: Если M(I)>M(I+1) то: Присвоить B значение M(I) Присвоить M(I) значение M(I+1) Присвоить M(I+1) значение B Конец Если Конец Цикла по I Конец Цикла по J Отобразить отсортированный массив. Конец Алгоритма

program tyy; uses Crt; const n = 5; type TVector=array[1..n] of integer; var M : TVector;B : integer; i,j : Integer; begin ClrScr; writeln(‘Введите элементы массива:’); for i:=1 to n do Read (M[i]); Writeln; for j:=n downto 1 do for i:=1 to j-1 do if M[i] > M[i+1] then begin B := M[i]; M[i] := M[i+1]; M[i+1] := B; end; Writeln (‘Отсортированный массив:’); for i:=1 to n do Write(M[i]:3); end.

Выберите книгу со скидкой:

История России. С древнейших времен до XVI века. 6 класс. Контурные карты

350 руб. 55.00 руб.

Контурные карты История России конец XVII-XVIII век. 8 класс. (Новые)

350 руб. 55.00 руб.

История России. 7 класс. Рабочая тетрадь.

350 руб. 137.00 руб.

История России. 6 класс. Рабочая тетрадь.

350 руб. 137.00 руб.

История России XX-начало XXI в. Атлас с контурными картами.

350 руб. 106.00 руб.

История России. XVI-конец XVII века. 7 класс. Контурные карты

350 руб. 55.00 руб.

История России. 8 класс. Рабочая тетрадь. История России. 8 класс. Рабочая тетрадь.

350 руб. 137.00 руб.

История России XIX – начало XX века. 9 класс. Контурные карты (Историко-культурный стандарт)

350 руб. 55.00 руб.

История России. 9 класс. Рабочая тетрадь.

350 руб. 137.00 руб.

ЕГЭ. История России в таблицах и схемах для подготовки к ЕГЭ. 10-11 классы

350 руб. 80.00 руб.

ЕГЭ. История России в таблицах и схемах. 10-11 классы

350 руб. 80.00 руб.

История России в рассказах для детей. ХV — ХVII века

350 руб. 137.00 руб.

БОЛЕЕ 58 000 КНИГ И ШИРОКИЙ ВЫБОР КАНЦТОВАРОВ! ИНФОЛАВКА

Инфолавка — книжный магазин для педагогов и родителей от проекта «Инфоурок»

Бесплатный
Дистанционный конкурс «Стоп коронавирус»

• Рожкова Ирина Сергеевна
• Написать
• 1312
• 06.04.2016

Номер материала: ДБ-013616

Добавляйте авторские материалы и получите призы от Инфоурок

Еженедельный призовой фонд 100 000 Р

• 06.04.2016
• 10786

• 06.04.2016
• 888

• 06.04.2016
• 2197

Не нашли то что искали?

Вам будут интересны эти курсы:

Все материалы, размещенные на сайте, созданы авторами сайта либо размещены пользователями сайта и представлены на сайте исключительно для ознакомления. Авторские права на материалы принадлежат их законным авторам. Частичное или полное копирование материалов сайта без письменного разрешения администрации сайта запрещено! Мнение редакции может не совпадать с точкой зрения авторов.

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

Лабораторная работа
Сортировка методом прямого выбора
в среде программирования Turbo Pascal 7.0 (DOS) (Паскаль)
Программа и описание

Среда программирования: Turbo Pascal 7.0 (DOS)

Название работы: Сортировка методом прямого выбора

Вид работы: Лабораторная работа

Тематика работы: Алгоритмы

Объем программы: 2 (по десятибалльной шкале)

Уровень сложности: 2 (по десятибалльной шкале)

Разработчик (автор): Программист сайта kursovik.com (письмо автору)

Ключевые слова: сортировка, прямой, выбор, упорядочение, массив

Описание (отчет): Есть , посмотреть оглавление

Перед покупкой работы не забудьте проверить её оригинальность. Запросить у администратора проверку текущей оригинальности работы по версии системы Антиплагиат.РУ

Лабораторная работа
Сортировка методом прямого выбора

Стоимость ИСХОДНОГО ТЕКСТА программы составляет 400 руб РФ

Стоимость ОПИСАНИЯ к программе составляет 80 руб РФ

Продажа каждой работы строго учитывается,
у каждой работы есть своя история продаж.

Как можно приобрести данную готовую работу ?

Заполните форму, которая расположена чуть Выше данного текста и нажмите кнопку «Приобрести»

Мы поддерживаем следующие способы оплаты:

• любые банковские карты: Visa, MasterCard, Maestro, МИР
• электронные деньги: QIWI, WebMoney, Яндекс.Деньги
• оплата по квитанции в любом банке на территории России
• оплата через отделения Евросети и Связного
• оплата с баланса мобильного телефона
• оплата через PayPal
• оплата наличными

Автоматическая оплата возможна с территории следующих государств:
Россия, Украина, Беларусь, Казахстан, Молдова, Литва, Латвия, Эстония,
Грузия, Армения, Азербайджан, Узбекистан, Таджикистан, Киргизия, Туркмения
С помощью электронных денег и PayPal оплата возможна со всего мира.

После заполнения формы Вы получите на свой E-mail автоматическое письмо со всеми подробностями оплаты заказа.

В течение нескольких минут с момента оплата заказа. Мы работаем 7 дней в неделю.

На Ваш E-mail адрес и в личном кабинете нашего сайта sys.kursovik.com.

Да, после оплаты Вы получите все файлы проекта данной работы, при желании сможете редактировать (видоизменять) программу (ее описание) самостоятельно.

Да, мы можем гарантировать уникальность данной работы.
Она была разработана нашим программистом на заказ и выставлена на продажу 1 декабря 2004 года.

Обычно работы по программированию всегда показывают больше 50% уникального текста.
Это напрямую связано с тем, что даже если введение, заключение и теоретическая глава вдруг окажутся неуникальными, то сам текст программы и описание ее работы слихвой компенсируют этот недостаток, т.к. они пишутся с нуля, скопировать их вряд ли откуда можно.
Тем не мнее, если вдруг при проверке купленной у нас готовой работы, она не дотятянет до требуемого в Вашем ВУЗе процента уникальности, то мы готовы поднять его при помощи специальной программы.
ВНИМАНИЕ ! Это предложение действительно только для готовых работ, купленных на нашем сайте ! Повышать уникальность каких-либо других работ мы не будем 🙂

Готового нет, но Вы можете заказать его дополнительно. Для этого заполните пожалуйста форму, приведенную ниже. В форме укажите требуемое оглавление(план) отчета. Если в Вашем ВУЗе никаких особых требований к отчету не выдвигают, тогда выберите пункт «требований к отчету нет, всё на усмотрение программиста».

Рекомендуем Вам также посмотреть нашу рубрику «вопросы и ответы».

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