• Поиск

    Введите ваш запрос для начала поиска.

  • Об авторах

    Курс разработан на кафедре Компьютерных технологий и систем Кубанского государственного аграрного унивеситета. Авторами являются заведующий кафедрой, доктор технических наук, профессор Лойко Валерий Иванович и доцент кафедры, кандидат физико-математических наук Лаптев Сергей Владимирович.

    Основные цели сайта

      Сайт предназанчен для максимально эффективного и быстрого доступа ко всем материалам курса "Алгоритмы и структуры данных", имеющимся на кафедре компьютерных технологий и систем КубГАУ. Основной задачей его создания является повышения эффективности освоения дисциплины студентами и всеми желающими.

Алгоритм сортировки методом прямого включения:

for i = 2 to n

   x = a(i)

   a(0) = x   {a(0) - барьер}

   j = i - 1

   while  x < a(j )  do

         a( j +1) = a(j )

         j = j - 1

   endwhile 

   a( j +1) = x

next i

return 

 

Для внутреннего цикла, организованного как цикл while , необходима постановка «барьера», без которого при отрицательных значениях ключей происходит потеря значимости и «зависание» компьютера.

Эффективность алгоритма:

Наилучшие оценки числа сравнений Cmin и перемещений Mmin встречаются в случае уже упорядоченной исходной последовательности элементов, наихудшие же оценки Сmax и Mmax - когда они первоначально расположены в обратном порядке.

Количество сравнений в худшем случае, когда массив отсортированпротивоположным образом, Сmax=n(n-1)/2, то есть порядок  О(n2).  Количество перестановок  Mmax=Cmax+3(n-1), то есть порядок  О (n2).

 

Алгоритм сортировки прямым выбором:

for i = 1 to n - 1

  x = a(i)

  k = i

  for j = i + 1 to n

    if a(j)<x  then

      k = j

      x = a(k)

    endif

  next j

  a(k) = a(i)

  a(i) = x

next i

return

 

Эффективность алгоритма:

  • Количество сравнений в худшем случае, когда массив отсортирован противоположным образом

Сmax=n(n-1)/2,

  • Количество перемещений когда массив обратно отсортирован

Mmax=Сmax+3(n-1),

 

  • Количество перемещений, когда массив упорядочен

 Mmin=3(n-1),     Cmin=(n-1)

 В худшем случае сортировка прямым выбором дает порядок n2, как и для числа сравнений, так и для числа перемещений.