Студопедия

Главная страница Случайная страница

Разделы сайта

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника






Билет. Задача сортировки






A0a1a2…an-1 -> ai0ai1…ain-1

F(ai0)< =f(ai1)< =…< =f(ain-1) f(x) – упорядочивающая функция

Методы (прямые): выбором, включением, обменом.

Эффективность методов: С(n) – кол-во сравнений; M(n) – кол-во перемещений; временная сложность – T(n), O(f(n)).

Const int nn = 100; int a[nn];

Выбор

Идея:

1).Min{ A0a1…an-1}ó a0

2).Min{ a1…an-1}ó a1

i).Min{ ai…an-1}ó ai

n-2).Min{ an-2an-1}ó an-2

Схема:

For(i=0; i< n-1; i++)

{поиск места К мин. эл-та в совокупности {A0a1a2…an-1}

Переставить akó ai}

Void selection(int a[], int n)

{for (int i=0; i< n-1; i++)

{int min = a[i], k=I;

For (int j=i+1; j< n; j++)

If (a[j]< min)

{min =a[j]; k=j}

A[k]=a[i]; a[i]=min}

}

Характеристики: C(n) = = ; M(n)min=3*(n-1); M(n)max=3*(n-1)+[ ]; T(n)=C*n2;

Модификации.

1). Поиск max{a0a1…an-1-i}

2). {ai…an-1-i} min k, max m;

A[k] ó a[i] if(m==i) m=k; a[m]ó a[n-1-i]

Включение

Идея: S1-упорядочена S2-неупорядочена

a0a1 a2…ai-1 |ai… an-1

ß R

Схема:

For (i=1; i< n; i++)

{R=a[i]; включить R в совокупность { A0…an-1}, поиск места вставки R

в совокупность { A0a1… ak ak+1 …ai} сдвиг { Ak+1…ai-1} вставка a[k+1]=R; }

void insertion(int a[], int n)

{for (int i=1; i< n; i++)

Int R=a[i];

While(k> =0& & a[k]> R)

{a[k+1]=a[k]; k--; a[k+1]=R; }

}

Характеристики: C(n)min=n-1; C(n)max= = ; M(n)min=2(n-1); Mmax=2(n-1)+ = ; T(n)=C*n2; O(n2);

Модификации:

1).поиск линейный (слева направо) с правым барьером.

K=0;

While(a[k]< R) k++;

For(int j = i-1; j> =k; j--) a[j+1]=a[j]; a[k]=R;

2).Поиск линейный с левом барьером.

For(int i=n-1; i> 0; i--)

If (a[i]< a[i-1])

{int t = a[i]; a[i] = a[i-1]; a[i-1] = t; }

For(int i=2; i< n; i++) R=a[i];

3).Двоичное включение.

Обменом

Идея: A0a1… aj aj+1 …an-2 an-1 aj < = aj+1

à

Void Bubble(int a[], int n)

{for (int i=n-1; i> 0; i--)

For(int j=0; j< I; j++)

If (a[j]> a[j+1])

{int t=a[j]; a[j]=a[j+1]; a[j+1]=t; }

}

Характеристики: C(n) = ; M(n)min=0; M(n)max=3*

С ЗАПОМИНАНИЕМ ФАКТА ПЕРЕСТАНОВКИ.

While(true){

Bool swapped = false;

For(…){

If (…) swapped = true; //если была перестановка

}

if(! swapped) break; }

ВЕКТОРОМ ИНДЕКСА.

A – исходный массив, V[i]=i - вектор индексов(массив)

For(int i=0; i< count; i++)

{for(int j=0; j < count – I; j++)

{if (A[V[j]]> A[V[j+1]]) swap(V[j], V[j+1])}

}

 

Билет






© 2023 :: MyLektsii.ru :: Мои Лекции
Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав.
Копирование текстов разрешено только с указанием индексируемой ссылки на источник.