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;

}

}


 

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

13720. It is sometimes said that borrowing money from a friend can harm or damage the friendship. Do you agree? Why or why not? Use reasons and specific examples to explain your answer 2.35 KB
  It is sometimes said that borrowing money from a friend can harm or damage the friendship. Do you agree Why or why not Use reasons and specific examples to explain your answer. I think that borrowing money from a friend has some negative aspects and can harm or damage the friendship in some cases. For example a person borrowed some money from his or her friend and did not return it. However I believe that borrowing money from a friend and returning it on time can not harm friendship...
13721. What are some important qualities of a good supervisor (boss)? Use specific details and examples to explain why these qualities are important 1.82 KB
  What are some important qualities of a good supervisor boss Use specific details and examples to explain why these qualities are important. Many people have to work under somebody's supervision. In most cases an employee does not choose his or her boss unless a supervisor is elected. In the following paragraphs I will list the most important qualities of my ideal boss. First of all he must be impartial. I believe that it is very important to make a technical decision think ...
13722. The government has announced that it plans to build a new university. Some people think that your community would be a good place to locate the university. Compare the advantages and disadvantages of establishing a new university in your community. Use sp 2.39 KB
  The government has announced that it plans to build a new university. Some people think that your community would be a good place to locate the university. Compare the advantages and disadvantages of establishing a new university in your community. Use specific details in your discussion. I think it is a great idea to build a new university in my community. However I think it is a controversial question whether the building of a new university will bring only benefits to our community. I...
13723. A company has announced that it wishes to build a large factory near your community. Discuss the advantages and disadvantages of this new influence on your community. Do you support or oppose the factory? Explain your position 1.98 KB
  A company has announced that it wishes to build a large factory near your community. Discuss the advantages and disadvantages of this new influence on your community. Do you support or oppose the factory Explain your position. I am from SaintPetersburg Russia. I believe that building a large factory near my community has advantages as well as disadvantages. In the following paragraphs I will list basic benefits and losses that will be brought by a new factory. For several reason...
13724. Тест биология. Вариант 1 202.45 KB
  ВАРИАНТ 1 Первая часть Назовите одноклеточную водоросль которая обитает в пресном водоеме. А фукус Б ламинария В спирогира Г хламидомонада Назовите процесс при котором растение поглощает углекислый газ и выделяет кислород. А фотосинтез
13725. Тест биология. Вариант 2 464.59 KB
  ВАРИАНТ 2 Первая часть Укажите участок корня который защищает зону роста А проводящая зона Б корневой чехлик В зона всасывания Г зона растяжения Проводящая система листовой пластинки представлена А жилками. Б прилистниками. В черешком...
13726. Тест биология. Вариант 3 ДПА 117.69 KB
  ВАРИАНТ 3 Первая часть Укажите орган который образуется в результате развития цветка. А почка Б лист В плод Г корень Назовите растение вегетативное тело которого представлено цепочкой клеток одинакового строения. А спирогира Б вольвокс ...
13727. Тест биология. Вариант 4 ДПА 507.42 KB
  1 ВАРИАНТ 4 Первая часть Назовите часть покрытосеменного растения содержащую точку роста. А листовая пластинка Б пестик В чашелистик Г кончик корня Назовите органеллу растительной клетки в которой накапливаются п
13728. Тест биология. Вариант 5 ДПА 145.03 KB
  ВАРИАНТ5 Первая часть Назовите травянистое растение с сидячими листьями. А мята Б бархатцы В кукуруза Г огурец Назовите способ размножения плауна булавовидного. А спорами или семенами Б плодами В семенами Г спорами Назовите тип...