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;

}

}


 

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

67482. Завдання, організація та актуальні питання медичної служби Збройних Сил України на воєнний час 148 KB
  Навчальна та виховна мета: розкрити найбільш складні та актуальні питання щодо ролі та місця у військовій медицині наукової дисципліни організації медичного забезпечення військ; ознайомити з організаційною структурою медичної служби ЗС України та її завданнями на воєнний час...
67483. ПОНЯТТЯ ТА СИСТЕМА ПРИРОДНОРЕСУРСОВОГО ПРАВА 145 KB
  Наукове значення природи полягає в безкінечній різноманітності об’єктів та процесів, які її складають і потребують вивчення. Іншими словами, природа є важливим джерелом наукових знань, основою для розвитку різноманітних галузей науки.
67484. РОБОТОТЕХНІЧНІ СИСТЕМИ (РТС), ЇХ СТРУКТУРА 337 KB
  Роботизований технологічний процес технологічний процес в якому в ролі основного технологічного устаткування використовуються промислові роботи і маніпулятори. З цією метою роботи доцільно сполучити з таким технологічним устаткуванням яке оснащене числовим програмним...
67485. Предприятие в условиях рыночной экономики 280 KB
  Цель моей работы рассмотреть и показать на примере, как предприятие функционирует в условиях рыночной экономики, какие виды и организационно-правовые формы предприятия существуют, какую роль играет ценообразование и какие методы планирования применяют предприятия.
67486. Экономика природопользования 353.5 KB
  Экономические механизмы природопользования Реализация экономических механизмов осуществляется через многие институты: кадастры своды экономических экологических организационных и технических показателей характеризующих количество и качество природного ресурса а также категории...
67487. Основы экологического права 216 KB
  Экологическое право является важным инструментом используемым государством в интересах сохранения и рационального использования окружающей природной среды. Нормами экологического права следует считать правила поведения регулирующие отношения людей по поводу охраны и использования окружающей природной среды.
67488. Конфликтология как наука: объект, предмет, функции, методы исследования конфликтов 127.5 KB
  Конфликтология как наука: объект предмет функции методы исследования конфликтов Ключевые понятия лекции Структура конфликта Принцип детерминизма Динамика конфликта Принцип системности Разрешение конфликта Принцип развития Конфликтное взаимодействие Структурно-функциональный...
67489. Эволюция конфликтологической мысли 375 KB
  Эволюция конфликтологической мысли Рассматриваемые в лекции вопросы Накопление знаний о конфликтах в Древнем мире Средние века и Новое время Развитие конфликтологии в рамках психологической науки XIXXX вв. Становление теории конфликта как самостоятельной области научных исследований.
67490. Динамика развития конфликта: основные этапы и их характеристика 189 KB
  Динамика развития конфликта: основные этапы и их характеристика Ключевые понятия лекции Динамика конфликта Завершение конфликта Конфликтная ситуация Послеконфликтный период Открытый конфликт Компромисс Инцидент Профилактика конфликта Социальная напряженность Создание образа...