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;

}

}


 

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

22921. Однорідні системи лінійних рівнянь 49 KB
  Будемо розглядати однорідну систему лінійних рівнянь з змінними 1 Зрозуміло що така система рівнянь сумісна оскільки існує ненульовий розвязок x1=0 x2=0xn=0. Цей розвязок будемо називати тривіальним. Можна зробити висновок що якщо однорідна система лінійних рівнянь має єдиний розвязок то цей розвязок тривіальний. Однорідна система лінійних рівнянь має нетривіальний розвязок тоді і тільки тоді коли її ранг менше числа невідомих.
22922. Поняття фундаментальної (базисної) системи розв’язків 55.5 KB
  Як показано вище множина M всіх розвязків однорідної системи лінійних рівнянь утворює підпростір. Фундаментальною базисною системою розвязків однорідної системи лінійних рівнянь називається базис підпростору всіх її розвязків. Теорема про фундаментальну систему розвязків.
22923. Теорема про розв’язки неоднорідної системи лінійних рівнянь 43 KB
  Теорема про розвязки неоднорідної системи лінійних рівнянь. Нехай дана сумісна неоднорідна система лінійних рівнянь 3 L множина всіх її розвязків а деякий частковий розвязок M множина всіх розвязків відповідної однорідної системи 4. Нехай a=γ1γ2γn і припустимо що b=λ1λ2λn довільний розвязок системи 3 тобто b є L.
22924. ЛЕМА ПРО ДВІ СИСТЕМИ 37.5 KB
  bk дві системи векторів кожен вектор першої системи лінійно визначається через другу систему. Якщо m k то перша система лінійно залежна. Нехай а1 а2 аm і b1 b2 bk дві системи векторів кожен вектор першої системи лінійно виражається через другу систему. Якщо перша система лінійно незалежна то m≤k.
22925. Поняття базису 25.5 KB
  aik лінійно незалежна; Всі вектори системи a1 a2 am лінійно виражаються через ai1ai2. Базисом простору Rn називається система векторів a1 a2 an є Rn така що система a1 a2 an лінійно незалежна; Кожний вектор простору Rn лінійно виражається через a1 a2 an. Звідси α1= α2==αn=0 лінійна коомбінація тривіальна і система лінійно незалежна. Будьякий вектор простору лінійно виражається через e1e2en .
22926. Властивості базисів 33.5 KB
  Оскільки при m n система з m векторів лінійно залежна то m≤n. Якщо m n то за означенням базису всі вектори простору а тому і вектори системи e1e2en лінійно виражаються через базис a1 a2 am .Тоді за лемою про дві системи вектори e1e2en лінійно залежні. Отже В просторі Rn будьяка лінійно незалежна система з n векторів утворює базис простору.
22927. Поняття рангу 47.5 KB
  В довільній системі векторів a1a2am візьмемо всі лінійно незалежні підсистеми. Число векторів в цій фіксованій підсистемі будемо називати рангом системи векторів a1 a2 am . Таким чином рангом системи векторів називається максимальна кількість лінійно незалежних векторів в системі. Зрозуміло що ранг лінійно незалежної системи дорівнює числу всіх векторів в системі.
22928. Поняття рангу матриці 28 KB
  Ранг системи векторів a1 a2 am називається горизонтальним рангом матриці або рангом матриці за рядками і позначається . Стовпчики матриці A можна розглядати як m вимірні вектори b1 b2bn з дійсними координатами елементи простору Rm. Ранг системи векторів b1 b2bn називається вертикальним рангом матриці A або рангом матриці A за стовпчиками і позначається rbA.
22929. Поняття базисного мінору 15.5 KB
  Припустимо Поняття базисного мінору. Припустимо Δr деякий мінор порядку r матриці A r≤mr≤n. Мінор порядку r1 матриці називається оточуючим для мінора Δr якщо його матриця містить в собі матрицю мінору Δr .