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;

}

}


 

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

11741. Работа с транзакциями. Кэширование изменений при работе с транзакциями 15.39 KB
  Лабораторная работа №1415 Работа с транзакциями. Кэширование изменений при работе с транзакциями. Цель: формирование практических умений и навыков работы с операторами TransactSQL объединенных транзакцией; создания транзакций; сохранения изменений; выполнение операций
11742. Обеспечение достоверности данных и перехват исключительных ситуаций 14.27 KB
  Лабораторная работа №16 Обеспечение достоверности данных и перехват исключительных ситуаций Цель: формирование практических умений и навыков определения и назначения определенного вида блокировки при работе с транзакциями; типа объекта для осуществления синхрониз
11743. Работа с отчетами 16.13 KB
  Лабораторная работа №17 Работа с отчетами Цель: формирование практических умений и навыков построения отчетов определение и составление запросов необходимых для содержания отчета. Ход работы Задание 1: Составить 3 запроса и сделать для них отчет: В Word Со
11744. Установка привилегий доступа 15.53 KB
  Лабораторная работа №18 Установка привилегий доступа Цель: формирование практических навыков в создании пользователей полей с помощью transactSQL. Установление привилегий пользователя роли обмена и изменение привилегий указанных для пользователя. Ход работы: Зада
11745. Автоматизированное тестирование 311.5 KB
  Лабораторная работа № 7. Автоматизированное тестирование. Цель: закрепить учебные навыки по автоматизированному тестированию. Ход работы 1. procedure TForm1.Button1ClickSender: TObject; VAR a: array [1..3] of real; zssum:real; ixns1:integer; begin n:=STRTOINTedit1.Text; x:=1; z:=0; s1:=10; For i:= 1 to 3 do begin ...
11746. Использование методов защиты информации в программах 99 KB
  ЛАБОРАТОРНАЯ РАБОТА № 8. Использование методов защиты информации в программах. Цель работы: освоить на практике методы защиты информации. Ход работы 1. Написать программу которая с использованием криптосистемы RSA шифрут сообщение: Истоpия кpиптогpафии pовесница
11747. Работа в составе бригады 42 KB
  Лабораторная работа №10. Работа в составе бригады. Цель: научиться коллективно обрабатывать разрабатывать отлаживать программные продукты. Ход работы Разработать программу выполняющую вычислительные действия над комплексными числами . var Form1: TForm1; ...
11748. Научиться пользоваться системой отладки 14.07 KB
  Лабораторная работа № 7. Автоматизированное тестирование. Цель: научиться пользоваться системой отладки. Выполнил: Романов П.Н. Группа: 091ПО Преподаватель: Кашталинская И.А. Дата: 30.11.12 Ход работы: Задание № 1. Составить программу вычислени
11749. Работа с БД. Создание сложных запросов 1.04 MB
  Лабораторная работа №4 Тема: Работа с БД. Создание сложных запросов Теоретический материал Современные информационные системы основанные на концепции интеграции данных характеризуются огромными объемами хранимых данных сложной организацией необходимостью у