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;

}

}


 

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

27081. Архитектура MRP II 131.24 KB
  Архитектура MRP II Объяснить что такое MRP II Что такое архитектура Как архитектура относится к классу данной системы 1. Концепция MRP II Manufacturing Resource Planning Планирование производственных. В отличие от MRP рассматривающего производственные мощности как неограниченные MRP II содержит специальную функцию позволяющую согласовывать потребности в материалах с возможностями производства. Таким образом MRP II представляет собой сочетание планирования по MRP с функцией CRP включая управление складами снабжением продажами и...
27082. Архитектура MRP-систем 132.39 KB
  Архитектура MRPсистем. Объяснить что такое MRP. В 60е годы был разработан метод MRP Material Requirements Planning Планирование потребностей в материалах позволяющий устранить недостатки простейших систем управления запасами. MRP базируется на данных основного производственного плана при составлении которого за исходную точку принимается ожидаемый спрос на готовую продукцию либо иные возникающие потребности в материалах.
27083. MRP II (Manufacturing Resources Planning) 34.44 KB
  В общем случае можно выделить следующие направления:  планирование бизнеса  планирование производства  формирование основного производственного планаграфика  MRP  CRP Системы MRP II предполагают вовлечение в информационную интеграцию финансовой составляющей планирование бизнеса. В системах MRP II предполагается специальный инструментарий формирования финансового плана и составления бюджетных смет прогнозирования и управления движением денежных средств на основании которых определяется возможность реализации производственного...
27084. MRP (Material Requirements Planning) 17.84 KB
  MRP Material Requirements Planning MRP системы интенсивная разработка теории которых осуществлялась с начала 60 годов в настоящее время присутствуют практически во всех интегрированных информационных системах управления предприятием. В настоящее время использование современных интегрированных систем на Российских предприятиях пока не нашло широкого распространения тем более функциональности планирования материальных ресурсов MRP В каких случаях использование MRP систем является целесообразным Прежде всего необходимо заметить что MRP...
27085. SCM 95.29 KB
  supply chain management SCM организационная стратегия и прикладное программное обеспечение предназначенные для автоматизации и управления всеми этапами снабжения предприятия и для контроля всего товародвижения. SCMсистемы охватывает весь товарный цикл: закупку сырья производство распространение товара. Выделяется шесть основных областей на которых сосредоточено управление цепями поставок: производство поставки месторасположение запасы транспортировка и информация В составе SCMсистемы можно условно выделить две подсистемы: SCP ...
27086. Информация в бизнесе. Информационная поддержка бизнеса 15.71 KB
  Информация сведения об объектах и явлениях окружающей среды их параметрах свойствах и состоянии которые воспринимают информационные системы живые организмы управляющие машины и др. Финансовоуправленческие системы включают подкласс малых интегрированных систем. Такие системы предназначены для ведения учета по одному или нескольким направлениям бухгалтерия сбыт склад кадры и т. Системы этого класса обычно универсальны цикл их внедрения невелик иногда можно воспользоваться коробочным вариантом купив программу и самостоятельно...
27087. Документооборот 14.98 KB
  Следует отметить что в этом определении упор делается на словах движение документов то есть их пути из одного подразделения или от одного сотрудника к другому. Автоматизация позволяет сократить время на обработку документов а также снижает риски случайной потери данных кроме того СЭД позволяет руководству контролировать выполнение управленческих решений. Возможность параллельного выполнения операций позволяющая сократить время движения документов и повышения оперативности их исполнения Непрерывность движения документа позволяющая...
27088. Корпоративная информационная система(КИС) 12.02 KB
  Основными блоками корпоративных информационных систем являются: система хранения база данных хранилище; система сбора и концентрации информации; системы поддержки принятия решений бизнеслогика базируется на обработке; специальные взаимодействия.
27089. ОСНОВНІ ВІДОМОСТІ ПРО ВАГОНИ. ТИПИ, ЗАГАЛЬНА БУДОВА, ТЕХНІКО-ЕКОНОМІЧНІ ПОКАЗНИКИ ВАГОНІВ. ПОЗНАЧКИ ТА НАДПИСИ НА ВАГОНАХ 337.5 KB
  Типи та конструкції сучасних вантажних, пасажирських та рефрижераторних вагонів являють собою доволі складну інженерну побудову. Тому інженери, що працюють в системі вагонного господарства залізничного транспорту та в вагонній промисловості, повинні добре знати конструкцію вагонів