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;

}

}


 

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

85307. Системы исходных понятий народной художественной культуры 37.16 KB
  Основными понятиями являются – культура ценности традиция этническая культура. Ценности – первым кто ввел это понятие в научный оборот был польский психолог В. Для большинства исследователей понятие ценности сродни понятию установка. Клакхон – ценностиэто осознанное или неосознанное характерное для индивида или группы индивидов представления о желаемом которое определяет выбор целей с учетом возможных последствий.
85308. Календарные праздники и обряды: структура, функции, художественные элементы 35.95 KB
  Основные зимние праздники приходились на январь. Дети девушки и парни под Рождество ходили по домам колядовать Колядовали и в Новый год. Молодежь наряжалась стариками и старухами цыганами гусарами; мазали лица сажей надевали вывороченные наизнанку шубы и ходили по деревне подшучивая над всеми разыгрывая сценки веселясь. Ходили друг к другу в гости обильно угощались блинами оладьями пирогами была и выпивка.
85309. Календарные праздники и обряды на Руси; их связь с зимним и летним солнцеворотами; весенним и осенним равноденствием; с циклами сельскохозяйственных работ; с языческими и христианскими основами веры 35 KB
  Важнейшие на Руси языческие обряды и праздники были слиты с земледельческим трудом с жизнью природы а значит с мифологическими олицетворениями природных сил. Первыми еще в глубокой древности возникли праздники связанные с земледельческим календарем предков восточных славян. Начинаясь в декабре когда солнце поворачивается на лето предвещая скорое пробуждение кормилицы материземли от зимнего сна и заканчиваясь осенью с завершением уборки урожая праздники составляли целостный календарный цикл.
85310. Система церковных праздников 35.79 KB
  Среди двунадесятых праздников три подвижных: Вход Господень в Иерусалим за неделю до Пасхи Вербное воскресенье Вознесение Господне Вознесение в 40й день по Пасхе и день Святой Троицы Пятидесятница Троица в 50й день по Пасхе. Неподвижные великие праздники: Крещение Господне Богоявление Водокрещи Иордань 619 января; Сретение Господне Сретение 215 февраля; Благовещение Пресвятой Богородицы Благовещенье 25 марта 7 апреля; Преображение Господне второй Спас Спас на горе средний Спас Спас яблочный 619...
85311. Классификация традиционных календарных праздников и обрядов русского народа 37.14 KB
  Расписное яйцо было столь важным атрибутом обрядов что длительное время примерно с Х века держался обычай пользоваться специально изготовленными керамическими разукрашенными яйцами писанками. Для землепашца это время критическое все что мог он на полях сделал брошенное зерно дало всходы теперь все зависело от природы а значит от прихоти управляющих природными стихиями существ. И ожидали в это время от русалок не только шалостей и козней но и орошения полей живительной влагой способствующей колошению хлебов. Во время праздника...
85312. Функции фольклора 29.24 KB
  Функции фольклора в целом и отдельных его жанров не могли не изменяться в зависимости от общих изменений структуры всей духовной культуры от типа соотношения фольклорных и условно говоря ldquo;нефольклорныхrdquo; форм и видов духовной культуры. Важнейшие общественные функции фольклора функции народной истории народной философии народной социологии.
85313. Методология и методы изучения народной художественной культуры 33.46 KB
  Виды научных исследований в области НХТ. Теоретические исследования НХК выявление сущности принципов функций закономерностей развития НХТ и т. Фольклористические исследования фиксирующие образцы НХТ выявляющие особенности жанров сказки песни театральные тексты и т. Понятие модели в педагогике возможности педагогического моделирования в разработке направлений развития объединений и организаций занимающихся НХТ.
85314. Традиционное народное жилище: структура, функции 44.65 KB
  Кочевой образ жизни издавна определил тип герметически замкнутого компактного жилищасборноразборной сооружения из решетчатого каркаса и войлочного покрытия круглого в основания и полусферическим верхом. Остов стен составляется из связанных между собой складных деревянных решёток которые определяют размеры и вместимость жилища. Если северная часть считалась почётной то южное пространство примыкающая к двери самая низшая часть жилища. Таким образом круглая юрта оригинальный исторически сложившийся образец жилища идеально...
85315. Научные предпосылки формирования курса «Теория и история народной художественной культуры» 35.12 KB
  Этнология сравнительная дисциплина целью которой является описание культуры а изначально и физических обличий между народами и объяснение таких различий по средствам реконструкции истории развития народов миграции и взаимодействия этносов. Эта концепция рассматривает происхождение культуры и культурных элементов в первобытном состоянии человечества. История культуры представляется как непрерывный процесс прямолинейный процесс перехода от простого к более сложному.