Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:
dain algoritm dina.docx
Скачиваний:
0
Добавлен:
01.07.2025
Размер:
443 Кб
Скачать
☆
  1. Шейкер сұрыптауы

Шейкер сұрыптауы – көпіршікті сұрыптаудың модификациясы. Оның әртүрлі аты бар: шейкерлі сұрыптау, трансферттік сұрыптау, екі жаққа бағытталған көпіршікті сұрыптау. Міне осы соңғы оның аты затына сай. Оның жұмыс істеу принципі көпіршікті сұрыптаудағыдай бір ғана ерекшелікпен – алгоритмді сұрыптау көпіршіктегідей тек төменнен жоғары емес, алдымен төменнен жоғары, сосын жоғарыдан төменге қарай сұрыпталады. Сөйтіп массив екі жақтан кезек кезекпен сұрыпталады.

Жақсы жақтары:

  • Орындалу алгоритмі өте жеңіл;

  • Қарапайым көпіршікті сұрыптаудан екі есе жылдам

Жаман жақтары:

  • Үлкен емес массивтерде ғана тиімді;

  • Алгоритмнің күрделілігі – O(n^2)

  1. Шелл арқылы сұрыптау

Шелл сұрыптау алгоритмі немесе арақашықтығы кемитін кірістірулер арқылы сұрыптау. Оны 1959 жылы Дональд Шелл қарапайым кірістірулер арқылы сұрыптау алгоритмін жылдамдату үшін ұсынған. Оның идеясы тек қана жанындағы элементтер емес бір-бірінен қашықтықта орналасқан элементтерді салыстыру. Алдымен массивтегі элементтер саны есептеледі. Одан кейін n элементтер санын екіге бөледі. Сөйтіп бірінші d арақашықтығы шығады. Ол массивтердің салыстыру қашықтығы болып табылады. Сондай d арақашықтағы элементтерді салыстырып, қате орналасса орнын ауыстырамыз. Артынан екінші d арақашықтығын тауып, тағы да салыстырамыз. d=1 болғанда қарапайым кірістурулер әдісі арқылы сұрыптаймыз.

Жақсы жақтары:

  • Стекке жадының қажеттілігі жоқтығы;

  • Деректерді қате терудегі деградациялардың жоқтығы;

  • Орташа көлемді массивтерде жылдам

Жаман жақтары:

  • Кіші және үлкен көлемді массивтерде баяу;

  • Бұл алгоритмнің анализі – әлі күнге дейін толық жауабы жоқ күрделі математикалық есеп, сол себепті қандай арақашықтық ең тиімді көрсеткіш беретіндігі де белгісіз.

  1. Іздеу ағашында орындалатын операциялар.(-)

  1. Іздеудің екілік ағашы

  2.  Іздеудің екілік ағашы. Iздеудің екiлiк ағашы. Iздестiру екiлiк ағашы әрбiр түйiнiне өлшенген элемент сәйкестiкке орнатылған түбiрлiк екiлiк ағашы деп аталады. Әрбiр түйiн x үшiн келесi шартты орындайды. X түбiрi бар сол ағаш астындағы барлық х түйiндерiнiң салмағынан аз немесе тең, онының оң жақ ағаш астындасының түйiндерiнiң салмағы артық немесе түйiн x салмағына тең. Келесi түрдiң түйiндерiмен мұндай ағаш өкiлдiк етедi Node = (element, key, left, right, parent)  T ағашқа рұқсат сiлтеме root көмегiмен жүзеге асырылады.  Екiлiк iздестiру ағашымен орындалатын операциялары: Search, Minimum, Maximum, Successor және Predecessor уақытқа орындауға мүмкiндiк береді (h ), ағаштың биiктiгi h.  1. (Search ) iздестiру. Iздестiрудiң процедурасы k және x iздестiрудi iстелетiн ағаш астынданың түбiрiне көрсеткiш кiре берiске iзделiп отырған кiлт алады. Ол (егер болса) k немесе (егер мұндай шың жоқ жағдайда) nil кiлтпен шыңға көрсеткiштi қайтарады.  Procedure Search (x, k);  begin if(x = nil) or (k = key [x]) then Return x;  if(k < key [x]) then Return Search (left[x], k) else  Return Search (right[x], k)  end.  Бiз iздестiрудiң процесiнде түбiрден қозғаламыз, кілтті k кiлтпен салыстыра, x ағымдағы шың сақталған қозғаймыз. Егер ол тең болса, iздестiру аяқталады. Егер k < key[x], онда iздестiру x сол ағаш астындада созылады. Егер k > key[x], онда iздестiру оң ағаш астында созылады. Iздестiру жолының ұзындығы ағаштың биiктiгiн асып түспейдi, сондықтан iздестiрудiң уақыты (h - ағаштың биiктiгi) (h ) O бар.  Іздестiру итерациясының процедурасы: Procedure IterativeSearch (x, k);  begin While (x ≠ nil) and (k ≠ key [x]) do  If k < key [x] then x:= left[x] else x:= right[x];  Return (x)  end.  Минимум және максимум. Iздестiру ағашында ең төменгi кiлтпен элемент табуға болады, көрсеткіш left түбiрден өте шыға nil-ге жеткенімізге дейін табуға болады. (x ) Minimum(x) процедура түбiрi бар ағаш астынданың табылған элементiне көрсеткiштi қайтарады. Procedure Minimum(x);  begin While left [x] ≠ nil do x:= left[x]; Return (x) end.  Алгоритм Maximum симметричен:  Procedure Maximum(x);  begin While (right [x] ≠ nil) do x:= right[x]; Return (x) end.  Екі алгоритм O(h) уақытты (ағаш бойымен тек қана төмен қозғалғандықтан) ағаштың биiктiгi талап етедi.  Келесi және алдыңғы элементтер. Егер х кейбір ағаштың көрсеткіші болса, сол Successor(x) рәсімі сілтегішті түйіншекке мен кейінгі x элемент немесе nil, егер көрсетілген элемент соңғы ағашқа қайтарады  Procedure Successor(x);  begin If (right[x] ≠ nil) then Return Minimum (right[x]);  y:= p[x];  while(y ≠ nil) and (x=right [y]) do {x:= y; y:= parent[y]};  Return y  end.  Келтiрiлген процедура екi жағдайды бөлек қарастырылады. Егер шың x оң ағаш астындағысы бос болмаса, онда келесi x элементке - бұл ағаш астындада ең төменгi элемент және ([x ] right) Minimum тең бол. Болғанша, егер шың x оң ағаш астындасы бос болса, онда x жүр өз ата-анасын сол ұл болатын шыңды үстiне таппаймыз. Бұл (егер ол барып тұр) ата-ана және iзделiп отырған элемент болады. Процедура Successor ағашындағы жұмысын уақыты биiктiгінде(h ), өйткенi бiз тек - үстiне, немесе тек қана төмен қарай қозғаламыз. Predecessor процедура симметриялық. Элементтiң қосымшасы.Процедура Insert (T, z) ағаш T қолайлы орынына элемент берiлгенге толықсытады. екі уақиғаны қарайды. x шыңының оң тармағы бос, сол кейінгі x элементті - ең төмен элемент осы тармақтағы және Minimum(right[x]) тең. x шыңының оң тармағы бос болса, x жоғары жағына барамыз, шыңды тапқанша  Procedure Insert(T, z);  begin y := nil; x := root;  while(x ≠ nil) do {y := x; if key[z] < key[x] then x := left[x] else  x := right[x]};  p [z] := y;  ify = nil then root := z else if key[z] < key[y] then left[y] := z else  right [y]:= z  end. Концептуалдық программалауды іске асырудың негізгі әдістемелік принциптері.

Программа куру кезинде есепти шешу амалдарын 2ге болип карастыруга болады:

1. Бурынгы корген адистер мен кателиктерди ескере отырып тапсырманы шешу. Ен басты максаты аз кателик жиберу аркылы жасау.

қосымша уақытты Ο (h) биіктіктің h ағашы үшін сұрайды.

Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]