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;

}

}


 

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

44804. Правило минимума Либиха. Закон оптимума. Закон толерантности Шелфорда 38 KB
  Закон оптимума. Закон толерантности Шелфорда. Закон минимума Либиха закон открытый. Либихом 1840 согласно которому относительное действие отдельного экологического фактора тем сильнее чем больше он находится по сравнению с другими факторами в минимуме; по данному закону от вещества концентрация которого лежит в минимуме зависят рост растений величина и устойчивость их урожайности.
44805. Понятие популяции. Структура и динамика популяций 41 KB
  Свободно скрещивающихся и дающих плодовитое потомство Основные характеристики популяций: 1 численность– общее количество особей на выделяемой территории; 2 плотность популяции – среднее число особей на единицу площади или объема занимаемого популяцией пространства; плотность популяции можно выражать также через массу членов популяции в единице пространства; 3 рождаемость– число новых особей появившихся за единицу времени в результате размножения; 4 смертность – показатель отражающий количество погибших в популяции особей за...
44806. Потоки вещества и энергии в биологических сообществах. Продуценты, консументы, редуценты. Трофические цепи и трофические сети. Пирамиды численности и биомассы в сообществах 37.5 KB
  Энергия основа работы экосистемы основной источник энергии Солнце. Поток солнечной энергии протекает через фототрофные экосистем при передаче в пищевых трофических цепях происходит рассеивание в виде тепла Пищевая цепь сеть – последовательность организмов где каждый предыдущий пища для последующего. Из всей поступающей солнечной энергии растениями усваивается только 2 остальное расходуется на транспирацию отражается листьями идет на нагревание воздуха воды и почвы.
44807. Продуктивность экосистем. Первичная и вторичная продукция 18.66 KB
  Пример экосистемы пруд с обитающими в нём растениями рыбами беспозвоночными животными микроорганизмами составляющими живую компоненту системы биоценоз. Все живые компоненты экосистемы – продуценты консументы редуценты составляют общую биомассу живой вес. Для экосистемы океана пирамида биомассы имеет перевернутый вид т. Знание энергетики экосистемы и количественных ее показателей позволяют точно учесть возможность изъятия из природной экосистемы того или иного количества растительной и животной биомассы без подрыва ее эффективности.
44809. Тhe purpose of grammar as a linguistic discipline 25 KB
  Lаnguаge is mens of forming nd storing ides s reflections of relity nd exchnging them in the process of humn intercourse. Lnguge is socil by nture; Lnguge incorportes the three constituent prts sides ech being inherent in it by virtue of its socil nture. Only the unity of these three elements forms lnguge; without ny one of them there is no humn lnguge in the bove sense. The phonologicl system is the subfoundtion of lnguge; it determines the mteril phoneticl ppernce of its significtive units.
44810. Предмет, содержание и задачи экономического анализа 38.5 KB
  ЭА осуществляемый на уровне отдельной фирмы предприятия называется обычно анализом хозяйственной деятельности. Предмет любой науки – это часть или сторона объективной действительности которая изучается только данной наукой; это хозяйственные процессы предприятий объединений ассоциаций социально-экономическая эффективность и конечные финансовые результаты их деятельности складывающиеся под воздействием объективных и субъективных факторов получающие отражение через систему экономической информации. Как видно из определения ЭА имеет...
44811. Анализ школьных учебников и методической литературы по химии 21.71 KB
  Анализ школьных учебников и методической литературы по химии. B сложной системе обучения химии учебник занимает важное место. В нем присутствуют все структурные элементы которые присущи обучению химии в целом: содержание предмета химии методы обучения средства обучении и организация учебной деятельности учащегося. Межпредметные связи в преподавании химии.
44812. Модель. Моделирование баз 41 KB
  При предметном моделировании строят физическую модель которая соответствующим образом отражает основные физические свойства и характеристики моделируемого объекта при этом модель и реальный объект мотуг иметь разную физическую природу. Если же модель и объект одной и той же физической природы то моделирование будет физическим. Абстрактное моделирование связана с построением абстрактной модели которая представляет собой математические диаграммы и т.