4875

Алгоритмы сортировки в массивах. Сортировка методом пузырька, вставками, выбором. Сортировка Шелла

Лекция

Информатика, кибернетика и программирование

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

Русский

2012-11-28

40 KB

41 чел.

Алгоритмы сортировки в массивах. Сортировка методом «пузырька», вставками, выбором. Сортировка Шелла.

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

В качестве простейшего алгоритма сортировки рассмотрим широко известную «пузырьковую» сортировку (сортировка простым обменом). Суть алгоритма заключается в последовательном проходе по массиву и сравнением каждой пары соседних элементов с переупорядочиванием этой пары в случае нарушения порядка. Нетрудно заметить, что при каждом таком полном проходе «наибольший» из неупорядоченных элементов окажется на соответствующем месте в конце последовательности, т.е. как бы «всплывет» (как пузырёк воздуха в воде) и встанет на свое место, отсюда и название алгоритма. Такие проходы по массиву повторяются до тех пор, пока не окажется, что за весь проход ни одна пара соседних элементов не поменялась местами – это будет означать, что все элемент в массиве расположены в правильном порядке. В худшем случае придется выполнить N проходов, что приводит к оценке сложности алгоритма в O(N*N) операций.

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

void insertSort( double * A, int N )

{

 // i - 1 определяет границу между упорядоченной

 // и неупорядоченной частями, поэтому начинаем сразу со второго

 // по счету элемента

 for ( int i = 1; i < N; ++i )

 {

 // Выбираем и запоминаем очередной элемент

 double selected = A[i];

 // j + 1 - индекс подходящего места в упорядоченной части

 int j = i - 1;

 // Определяем подходящее место одновременно со сдвигом

 // соответствующих элементов в упорядоченной части

 while ( j >= 0 && A[j] > selected )

 {

  A[ j + 1 ] = A[j];

  --j;

 }

 // Размещаем элемент на новом месте

 A[ j + 1 ] = selected;

}

}

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

void selectSort( double * A, int N )

{

 // Индекс i соответствует границе между упорядоченной

 // и неупорядоченной частями

 for ( int i = 0; i < N; ++i )

{

 // Индекс минимального элемента

 int minIdx = i;

 // Ищем минимальный элемент в неупорядоченной части

 for ( int j = i + 1; j < N; ++j )

 {

  if ( A[j] < A[minIdx] )

   minIdx = j;

 }

 // Обмениваем местами минимальный элемент и первый

 // в неупорядоченной части

 double tmp = A[i];

 A[i] = A[minIdx];

 A[minIdx] = tmp;

 }

}

Сортировка Шелла предполагает модификацию алгоритма вставками, призванную уменьшить суммарное количество перестановок. Основная идея состоит в многопроходной сортировке исходной последовательности простым алгоритмом вставок, причем на каждом этапе сортируются все подпоследовательности в исходном массиве, образованные элементами, расположенными друг от друга на фиксированном расстоянии. Каждый последующий этап использует меньший шаг, завершается сортировка Шелла проходом с шагом 1. Несмотря на то, что фактически, последним этапом алгоритма является обычная сортировка вставками, существенный выигрыш достигается за счет того, что на первых, «грубых» этапах сортировки, некоторые элементы оказываются близко к своим окончательным местам за гораздо меньшее количество операций. В качестве последовательности расстояний между элементами, используемых на каждом проходе, чаще всего используют степени двойки: 2k, 2k-1,…, 4, 2, 1.

void shellSort( double * A, int N )

{

 // Определяем максимальную степень 2, не превышающую N

 int maxpow2 = std::log( static_cast< double >( N ) ) /

       std::log( 2.0 );

 // Определяем начальный шаг сортировки

 int step = std::pow( 2.0, maxpow2 );

 while ( step > 0 )

{

 // Сортировка вставками всех

 // подпоследовательностей с шагом step  

 for ( int i = step; i < N; ++i )

 {

  double selected = A[i];

  int j = i - step;

  while ( j >=0 && A[j] > selected )

  {

   A[ j + step ] = A[j];

   j -= step;

  }

  A[ j + step ] = selected;

 }

 // Уменьшаем шаг

 step /= 2;

}

}


 

А также другие работы, которые могут Вас заинтересовать

13472. Изучение методов получения заготовок литьем 1.02 MB
  Лабораторная работа №1 Изучение методов получения заготовок литьем Используя рисунки представленные в методических указаниях материалы лабораторных стендов а также рекомендуемую литературу изучить технологический процесс получения заготовок литьем и подготови...
13474. Изучение методов получения заготовок давлением (пластическим деформированием) 4.81 MB
  Лабораторная работа №2 Изучение методов получения заготовок давлением пластическим деформированием Используя рисунки представленные в методических указаниях материалы лабораторных стендов а также рекомендуемую литературу изучить технологический процесс по...
13475. Изучение технологического оснащения токарной обработки 1.05 MB
  Лабораторная работа №3 Изучение технологического оснащения токарной обработки. Используя рисунки представленные в методических указаниях материалы лабораторных стендов а также рекомендуемую литературу изучить средства технологического оснащения оборудование...
13476. Подготовка текста в Microsoft Word 838 KB
  Лабораторная работа Тема: Подготовка текста в Microsoft Word Цель работы: Научиться создавать таблицы и формулы работать с документом в режиме исправлений создавать формы бланки для проведения опросов и тестирования выполнять слияние документа с источником данных об...
13477. Объекты системы 1С:Предприятие 759.5 KB
  Объекты системы 1С:Предприятие В системе 1С:Предприятие можно выделить две основные составляющие: технологическая платформа; прикладные решения автоматизации различных участков деятельности которые создаются с помощью технологической платформы. В техн...
13478. Создание новой информационной базы 199 KB
  Документы Лабораторная работа Задача 1. Создание новой информационной базы. 1. Выполните Пуск|Программы|1C Предприятие 8.1|Конфигуратор. 2. В появившемся окне Запуск 1С:предприятия щелкните по кнопке Добавить. 3. В появившемся окне Добавление информационной базы/г
13479. Создание регистра накопления остатков 279.5 KB
  Регистры накопления Лабораторная работа Задача 1. Создание регистра накопления остатков. 1. Откройте базу МояБаза1 в режиме конфигуратора. 2. Создайте документ Поступление. В области шапки документа укажите один дополнительный реквизит Заказчик тип данных Спра...
13480. Организация непериодических регистров сведений 163 KB
  Регистры сведений Лабораторная работа Задача 1. Организация непериодических регистров сведений. Пусть в организации имеется несколько филиалов каждый из которых включает несколько подразделений. В каждом конкретном подразделении филиала определено ответственно