4875

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

Лекция

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

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

Русский

2012-11-28

40 KB

42 чел.

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

Под сортировкой будем понимать упорядочивание элементов в соответствии с некоторым выбранным правилом. В качестве правила упорядочивания может служить любой предикат, т.е. функция, ставящая в соответствие паре элементов значение 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;

}

}


 

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

49039. Выполнение действия в виде функций с динамическим распределением памяти программным способом 365.5 KB
  Вывести результат сглаживания заданной вещественной матрицы размером 10 на 10. Соседями элемента Аij в матрице назовем элементы. Операция сглаживания матрицы дает новую матрицу того же размера, каждый элемент которой получается как среднее арифметическое имеющихся соседей соответствующего элемента исходной матрицы.
49040. Решение дифференциального уравнение с заданными начальными значениями 451 KB
  Данное уравнение необходимо решить методом Эйлера и Эйлера модифицированного а также сравнить результаты и сделать вывод об эффективности методов построить их графики.Метод Эйлера Данный метод одношаговый. Обобщим формулу для решения дифференциальных уравнений методом Эйлера: 3.Эйлер модифицированный Для уменьшения погрешности вычислений часто используется модифицированный метод Эйлера.
49041. WEB – СЕРВИС 1.21 MB
  Приходится разбираться с многочисленными параметрами конфигурации pche PHP и MySQL. Денвер это те же самые дистрибутивы pche PHP MySQL. Денвер создавался для того чтобы упростить настройку и установку свободно распространяемых программ pche PHP MySQL и т. Базовый пакет содержит большинство необходимых Webпрограммисту программ и утилит: pche с поддержкой SSI mod_rewrite mod_php.
49043. Расчёт и моделирование частотно-избирательного усилителя 712.5 KB
  Еще один буферный каскад должен согласовывать последний УК с входным сопротивлением RCфильтра и еще один на полевом транзисторе с высоким выходным сопротивлением датчика. Итого схема будет состоять из датчика трех буферных каскадов двух усилительных RCфильтра и нагрузки. Схема будет состоять из датчика 4х каскадов усиления одного буферного каскада для согласования с RCфильтром RCфильтра.
49044. Основные жизненные процессы 439.5 KB
  В организованной структуре ее элементы осуществляют только такую активность, которая не нарушает существования и функционирования органического целого. Поэтому повышение (или усложнение) организации означает уменьшение степени свободы частей целого. Жестко организованные объекты имеют нулевую степень свободы частей
49045. Прогнозирование курса доллара 198.5 KB
  Практическое применение нейронных сетей для прогнозирования курса доллара. Целью данной курсовой работы является прогнозирование курса доллара с использованием нейросетевых технологий. Основными задачами на пути достижения поставленной цели являются: Составление модели для прогнозирования курса доллара; Создание оптимально работающей нейросети для прогнозирования курсов доллара.
49046. Учебно-методическое пособие к выполнению индивидуальных заданий и контрольных работ по общей химии 576.94 KB
  Химия – одна из фундаментальных наук естествознания, формирующих естественно-научное мировоззрение будущих специалистов. Наличие прочных химических знаний способствует воспитанию творческой личности, целостно воспринимающей мир, способной прогнозировать эффективность новых решений, организовывать их практическую реализацию, активно влиять на процессы, происходящие в социальной и профессиональной сферах.
49047. Устройство селекции по амплитуде с формированием стробирующего импульса внешнему устройству 201.5 KB
  Данное устройство обеспечивает измерение амплитуды импульсов следующих с периодом 50 мкс осуществляет их селекцию по амплитуде и выдачу импульса уровня 0 длительностью 05 мкс если амплитуда в пределах допустимого диапазона. Описание принципа работы Микропроцессорный блок осуществляет опрос входа в моменты прихода импульсов ВИК с периодом 50 мкс. При попадании в порог ≤ 5В запускается таймер который формирует строб длительностью 05 мкс.5мкс.