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;

}

}


 

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

52140. Розвязування рівнянь 120.33 KB
  Мета уроку: Розв’язувати найрізноманітніші рівняння, що відрізняються за тематикою і аналіз ситуації у яких припускаються найбільш поширені помилки; підвищення строгості математичних міркувань; виховувати увагу культуру математичного мовлення кмітливість. В історії розвитку математичних софізмі зіграли суттєву роль. Корекція вмінь та навичок учнів з теми через розв’язування рівнянь.
52141. Квадратные уравнения. Решение квадратных уравнений 325 KB
  Тема урока: Решение квадратных уравнений. Квадратные уравнения находят широкое применение при решении тригонометрических показательных иррациональных уравнений и неравенств используются при решении задач по химии и физике. Мы изучили с вами формулы корней квадратных уравнений с помощью которых можно решить любое квадратное уравнение. Однако имеются и другие приемы решения квадратных уравнений которые позволяют очень быстро и рационально решать их.
52142. Найпростіші перетворення графіків функцій 61.5 KB
  Учні самі розподіляються хто яку роботу виконує. Один учень виконує роботу на листі А4. Один учень виконує роботу на листі А4. Один учень виконує роботу на листі А4.
52143. Квадратична функція 1.85 MB
  Вони повинні розглядатися у наступному тематичному блоці адже розв’язування більшості цих вправ не потребує знань властивостей та графіка квадратичної функції. Властивості функції. Елементарні функції. Властивості функції.
52144. Построение графиков с помощью геометрических преобразований 2.47 MB
  Найти область определения функции: ученик работает у доски у= . Перед учащимися карточки с изображением графиков функции у=fx. Для построения графика функции у=2 необходимо выполнить: А параллельный перенос графика функции у= на 2 единицы влево; Б параллельный перенос графика функции у= на 2 единицы вверх; В сжатие графика функции у= вдоль оси ОУ в 2 раза; Г параллельный перенос графика функции у= на 2 единицы вниз;...
52145. Многочлен від однієї змінної та його корені 30.5 KB
  Поділивши куточком многочлен Ах на многочлен Вх знайдіть неповну частку й остачу: Ах = 2х5 5х3 6х – 7 Вх = х3 х. Методом невизначених коефіцієнтів знайдіть значення параметра а якщо при діленні многочлена х4 ах3 – 2х2 х – 1 на тричлен х2 х – 1 остача дорівнює – 6х 2. Знайдіть корені многочлена 2х3 7х2 7х 2. Поділивши куточком многочлен Ах на многочлен Вх знайдіть неповну частку й остачу: Ах = х4 х 1 Вх = х2 х 1.
52146. Застосування похідної до дослідження функції та побудова графіків 51 KB
  Перш ніж побудувати графік функції її необхідно дослідити а схему дослідження оформимо у вигляді алгоритму. Алгоритм дослідження функції: Знайти область визначення функції. Знайти точки перетину з осями координат Дослідити функцію на парність непарність періодичність Знайти інтервали зростання і спадання функції Знайти точки екстремуму функції.
52147. Использование интеграла для вычисления площадей плоских фигур и объемов тел вращения 302.5 KB
  Начнем нашу совместную работу, с таких слов, которые будут напутствием. У математиков существует свой язык – язык формул. Расшифруйте математические записи. Переходя из одной кабины в другую в чертовом колесе обозрения.
52148. Формування та розвиток критичного мислення під час розвязування рівнянь вищих ступенів, розвязки яких зводяться до розвязування квадратних рівнянь 413.5 KB
  Мета уроку : Навчити учнів застосовувати формули під час розвязування рівнянь вищих степенів. Очікувані результати : Навчити розуміти формули за якими розвязуються рівняння вищих степенів.