Студопедия

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

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

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






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






    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 :: Мои Лекции
    Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав.
    Копирование текстов разрешено только с указанием индексируемой ссылки на источник.