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;

}

}


 

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

26345. Североамериканская война за независимость и образование США 18.58 KB
  В нем убедительно доказывалось насколько абсурдно бороться за свободу не порывая с метрополией и что только независимость и республиканский образ правления дадут Америке великое будущее. а также на традицию борьбы за свободу американских колонистов. Все люди сотворены равными гласила Декларация независимости все они одарены Создателем некоторыми неотъемлемыми правами к числу которых относятся право на жизнь свободу и стремление к счастью. Говоря о естественных и неотчуждаемых правах человека Джефферсон изменил традиционную...
26346. Политическая борьба в США после окончания Войны за независимость. Американская конституция 1787 г 20.18 KB
  представляла отдельным штатам фактическую самостоятельность вплоть до права объявления войны; конгресс же конфедерации являлся консультативным органом и даже бюджет его составлялся только из добровольных взносов штатов. Уже первая конституция Статьи конфедерации знала институт президента глава которого возглавлял Конгресс своего рода собрание дипломатов тринадцати участвующих штатов. в большинстве отдельных штатов была разработана новая конституция губернаторов сделали чисто исполнительными органами парламентов урезав ссылаясь на...
26347. Франция в п.п. XVII в. Ришелье 20.09 KB
  Ришелье. Ришелье занимал пост первого министра Людовика XIII и был фактическим руководителем государства. Ришелье и политика укрепления абсолютизма. Ришелье многое сделал для укрепления абсолютизма.
26348. Внутренняя и внешняя политика Франции в годы правления Людовика XIV 19.96 KB
  Внутренняя и внешняя политика Франции в годы правления Людовика XIV. Внутренняя политика Людовика XIV Внешний блеск царствования Людовика XIV страшно истощил силы населения которое временами очень бедствовало особенно во вторую половину царствования когда Людовика XIV окружали в основном бездарности или посредственности. Сосредоточивая управление всеми делами в своих руках или в руках министров Людовик XIV окончательно утвердил во Франции систему бюрократической централизации. Стесняя права церкви по отношению к королевской власти и...
26349. Французская абсолютная монархия в XVIII в. – внутренняя и внешняя политика Людовика XV 13.64 KB
  – внутренняя и внешняя политика Людовика XV. Система Людовика XIV привела страну к совершённому разорению под бременем тяжёлых налогов громадного государственного долга и постоянных дефицитов. И Людовик XV и Людовик XVI были люди беспечные не знавшие иной жизни кроме придворной; они ничего не сделали для улучшения общего положения дел. В начале царствования Людовика XV который приходился Людовику XIV правнуком за малолетством короля управлял герцог Орлеанский Филипп.
26350. Франция при Людовике XVI. Революционная ситуация 1787-1789 г 26.35 KB
  Франция при Людовике XVI. Людо́вик XVI 23 августа 1754 21 января 1793 король Франции из династии Бурбонов сын дофина Людовика Фердинанда наследовал своему деду Людовику XV в 1774. Людовик сначала принял конституцию 1791 года отказался от абсолютизма и стал конституционным монархом однако вскоре начал нерешительно противодействовать радикальным мерам революционеров и даже попытался бежать из страны. После свержения республиканские власти лишили Людовика XVI титула короля и дали ему фамилию Капет фр.
26351. Начало Французской буржуазной революции. Взятие Бастилии 14.43 KB
  12 июля в Париж проникли известия об отставке министра Неккера которому король приказал покинуть пределы Франции. Уже вечером 12 июля произошли первые столкновения народа с правительственными войсками. Утром 13 июля над Парижем загудел набат призывая парижан к восстанию. 13 июля парижские выборщики организовали Постоянный комитет преобразованный позднее в коммуну Парижский муниципалитет.
26352. Буржуазные преобразования во Франции в 1789 – 1791 г 21.47 KB
  Уже в июле Собрание создало комиссию по подготовке декларации и конституции Франции. Однако изза роста крестьянских восстаний Собрание безотлагательно начинает с решения аграрного вопроса. Призывая остальную часть дворянства пожертвовать своими правами в интересах справедливости и принести жертвы на алтарь отечества Учредительное собрание 11 августа приняло декреты по аграрному вопросу. Таким образом не решив сути аграрного вопроса Учредительное собрание в декретах 4 11 августа объявило что полностью уничтожает феодальный режим.
26353. Общественно – политическая жизнь Франции в 1791 – 1792 гг. Вареннский кризис и Конституция 1791г 21.07 KB
  и переезд короля и Собрания в Париж резиденцией монархии стал дворец в Тюильри. Дантон Шометт Кондорсе выступали ее горячими поборниками на собраниях секций. Депутаты Учредительного собрания на момент разбирательства временно отрешили короля от власти. Не теряя надежды после стольких преобразований договориться с Людовиком XVI и установить в королевстве конституционную монархию а также стремясь дать самый решительный отпор сторонникам республики депутаты Собрания прикладывали все усилия для спасения сильно пошатнувшейся репутации...