Для чего применяется сортировка списков

Сортировка списков

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

Пользователь может задать три уровня сортировки одновременно: за одну операцию можно выполнить сортировку сначала по первому уров­ню, потом в полученном списке — по второму, а затем — по третьему уровню: Так, например, можно сразу отсортировать записи по фамилиям, по именам и по дате рождения сотрудников.

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

Рис. 3. Окно задания критериев и уровней сортировки.

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

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

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

Источник

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

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

На собеседованиях будущим стажёрам-разработчикам дают задания на знание структур данных и алгоритмов — в том числе сортировок. Академия Яндекса и соавтор специализации «Искусство разработки на современном C++» Илья Шишков составили список для подготовки с методами сортировки, примерами их реализации и гифками, чтобы лучше понять, как они работают.

Пузырьковая сортировка и её улучшения

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

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

Этот алгоритм считается учебным и почти не применяется на практике из-за низкой эффективности: он медленно работает на тестах, в которых маленькие элементы (их называют «черепахами») стоят в конце массива. Однако на нём основаны многие другие методы, например, шейкерная сортировка и сортировка расчёской.

Сортировка перемешиванием (шейкерная сортировка)

Шейкерная сортировка отличается от пузырьковой тем, что она двунаправленная: алгоритм перемещается не строго слева направо, а сначала слева направо, затем справа налево.

Сортировка расчёской

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

Первоначальный разрыв нужно выбирать не случайным образом, а с учётом специальной величины — фактора уменьшения, оптимальное значение которого равно 1,247. Сначала расстояние между элементами будет равняться размеру массива, поделённому на 1,247; на каждом последующем шаге расстояние будет снова делиться на фактор уменьшения — и так до окончания работы алгоритма.

Простые сортировки

Сортировка вставками

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

Сортировка выбором

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

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

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

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

Сортировка слиянием

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

Пирамидальная сортировка

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

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

Источник

ТЕМА 4.4. СПИСКИ. ОБРАБОТКА, СОРТИРОВКА И ФИЛЬТРАЦИЯ ТАБЛИЧНЫХ ДАННЫХ. СТРУКТУРИРОВАНИЕ ТАБЛИЦ

Познакомиться с технологиями:

Оглавление

4.4.1. Понятие списка (базы данных)

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

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

Ячейки верхней строки с именами полей образуют область имен полей.

Рис. 1. Структурные элементы списка (базы данных Excel)

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

Список содержит фиксированное количество полей (столбцов), определяющих структуру записи базы данных (строки).

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

4.4.2. Сортировка данных в списке

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

В среде Microsoft Excel предусмотрено три уровня сортировки, которые определяются в диалоговом окне Сортировка диапазона (Рис. 2).

В том же окне устанавливается порядок сортировки в столбцах – по возрастанию или убыванию. При сортировке по возрастанию упорядочение идет:

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

Рис. 2. Параметры сортировки

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

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

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

4.4.3. Фильтрация

Фильтрация данных в списке – это отбор данных по заданному критерию (условию). Осуществляется эта операция с помощью команды Данные/Фильтр. Имеется две разновидности этой команды, задаваемых параметрами: Автофильтр и Расширенный фильтр.

Фильтрация данных может осуществляться с помощью специальной формы, которая вызывается командой Данные/Форма.

4.4.4. Автофильтрация

Команда Данные/Фильтр/Автофильтр для каждого столбца строит список значений, который используется для задания условий фильтрации (Рис. 3). В каждом столбце появляется кнопка списка, нажав которую можно ознакомиться со списком критериев отбора.

Рис. 3. Список с автофильтром

Для каждого столбца в списке критериев отбора предусматриваются следующие варианты:

Рис. 4. Наложение условия по списку

Условие для отбора записей по конкретным значениям в определенном столбце может состоять из двух самостоятельных частей, соединенных логической связкой И/ИЛИ (Рис. 5). Каждая часть условия включает один из операторов отношения:

Рис. 5. Задание условия фильтрации

Примеры условий

Для поля Код предмета можно сформировать условия:

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

отобрать все записи, которые не содержат кода предмета п1

4.4.5. Расширенный фильтр

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

Расширенный фильтр позволяет задать условия отбора двух типов критериев:

Если критерий фильтрации формируется в нескольких столбцах, его называют множественным критерием.

Технология использования расширенного фильтра состоит из двух этапов:

Технология формирования области условий

Правила формирования Критерия сравнения

2-й способ. Множественный критерий сравнения – условия (точные значения полей) записаны в двух строках (Таблица 3). Номер группы, код предмета и оценка заданы как точные значения. На одной строке указаны оценка «4», на другой – «5». Связка “ИЛИ”.

Таблица 3. Задание множественного критерия. Связка “ИЛИ”

Номер группы

Код предмета

Оценка

Вычисляемый критерий представляет собой формулу в виде логического условия, которая возвращает логическое значение ИСТИНА или ЛОЖЬ. Формула обязательно содержит оператор отношения, который сравнивает некоторые вычисляемые выражения.

Имя столбца, содержащего формулу вычисляемого критерия, должно отличаться от имени столбца в списке.

Пример

Из списка (Рис. 3) выбрать записи о студентах группы 133, получивших оценку ниже общего среднего балла или получивших оценку 5. Пример вычисляемого критерия представлен в таблице (Таблица 4). Столбец Номер группы имеет такое же имя как и столбец в исходном списке, потому что для отбора группы используется критерий сравнения. Имя столбца Оценка1 отличается от имени столбца в исходном списке, т.к. здесь используется вычисляемый критерий.

Таблица 4. 1-й способ задания вычисляемого критерия

Номер группы

Оценка1

Рис. 9. Исходная таблица для автостуктурирования

По каждому виду начислений в строке Итого рассчитывается с помощью функции СУММ общая сумма по ячейкам столбца. Порядок следования исходных данных и результатов (итогов) – слева направо, сверху вниз, позволяет применить автоструктурирование таблицы (Рис. 10).

После ввода в таблицу исходных данных и формул курсор устанавливается в произвольную ячейку списка и выполняется команда Данные/Группа и Структура/Создать структуру. Все структурные части таблицы создаются автоматически.

Рис. 10. Таблица после автоструктурирования

Структурирование таблицы с автоматическим подведением итогов

В среде Excel существует инструмент структурирования с одновременным подведением итогов. Команда Данные/Итоги создает структуру таблицы и одновременно вставляет строки промежуточных и общих итогов для выбранных столбцов в соответствии с заданной функцией (Таблица 8).

Примечание. Для получения итогов по группам следует заранее упорядочить строки списка с помощью команды Данные/Сортировка.

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

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

Команда Данные/Итоги может выполняться для одного списка многократно. Созданные ранее промежуточные итоги могут как заменяться новыми, так и оставаться неизменными посредством установки или снятия флажка параметра Заменить текущие итоги (Рис. 11). Таким образом, имеется возможность подведения итогов различных уровней вложенности.

Таблица 8. Функции для подведения автоматических итогов

Операция

Значение в строке итогов по группе

Источник

Для чего применяется сортировка списков

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

Сортировка списков

В качестве примера рассмотрим таблицу с итогами сессии.

Обратим внимание на следующие особенности сортировки:

Гораздо реже, чем сортировка по строкам, применяется сортировка по столбцам. Но она в Excel также возможна. В этом случае признаком сортировки является одна из строк списка, например, заголовок, или итоговая строка. Для выполнения сортировки необходимо в окне «Сортировка диапазона» нажать кнопку «Параметры» и установить переключатель «Сортировать столбцы диапазона».

Поиск записей

Применение фильтров

Автофильтр

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

Для задания более сложного условия фильтрации необходимо в соответствующем раскрывающемся списке выбрать «[Условие. ]» и сформулировать его в открывшемся окне «Пользовательский автофильтр». Окно содержит поля для ввода знаков логических отношений и метки логических операций И и ИЛИ. Например, для отбора записей, соответствующих студентам, получившим по информатике 4 или 5, следует выполнить настройки, как показано на рисунке.

Достоинство автофильтра в простоте его применения. Недостаток: в отсутствии возможности формулировать сложные условия, связывающие условия фильтрации в разных столбцах операцией ИЛИ.

Расширенный фильтр

Для применения расширенного фильтра требуется предварительная подготовка, состоящая из двух этапов:

В качестве критериев можно использовать содержимое ячеек таблицы или логические выражения с использованием содержимого.

В качестве примера рассмотрим условие фильтрации («Группа»=154 И «Оценка по информатике»>3) ИЛИ («Группа»=155 И «Оценка по информатике»>3).

Исходная таблица, блок критериев и новая таблица с результатами фильтрации показаны на рисунке.

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

Контрольные вопросы

Что называется списком в табличном процессоре Excel?

Как Excel определяет границы списка?

Что такое режим автозаполнения ячеек?

Для чего применяется сортировка списков?

В каких ситуациях применяется сортировка списков по нескольким признакам?

Список состоит из двух полей: фамилии студента и оценке по информатике. Какие из этих полей следует использовать как первичный и вторичный признаки сортировки? Обоснуйте ответ.

Как сделать так, чтобы при сортировке списка поле с порядковыми номерами записей осталось неотсортированным?

Что такое поиск информации в списке?

Что такое маска поиска? Как она записывается?

Что такое фильтр? Какие виды фильтров имеются в Excel?

Объясните принцип работы автофильтра.

Объясните принцип работы расширенного фильтра.

Чем расширенный фильтр отличается от автофильтра?

Каковы правила формирования блока критериев в расширенном фильтре?

Источник

Работа со списками