ИНЖЕНЕРЛІК ЕСЕПТЕРДЕ БАҒДАРЛАМАЛАУ ТЕХНОЛОГИЯСЫ
Дәріс: Искакова Г.Т.

g.iskakova@aues.kz
Дәріс – 6: Сұрыптау алгоритмдерін ұйымдастыру

Массивті сұрыптау

• 
  Массивті сұрыптау - бұл оның элементтерінің мәндерін өсу немесе кему бойынша реттеу
  
• 
  Бірнеше сұрыптау алгоритмдерін қарастырайық
  

Таңдау әдісімен сұрыптау - Selection sort

• 
  Алдымен массивтің ішкі жиынын қарастырып, ондағы максималды (немесе минимумды) табу керек.
  
• 
  Содан кейін таңдалған мән бірінші сұрыпталмаған элементтің мәні бар орындармен ауыстырылады. Бұл қадам массивте сұрыпталмаған қосалқы массивтер таусылғанша қайталануы керек.
  

Таңдау әдісімен сұрыптау - Selection sort

• 
  Бұл әдістің негізгі идеясы массивтің сұрыпталған бөлігін оның сұрыпталмаған бөлігінде таңдалған келесі элементті қосу арқылы дәйекті түрде қалыптастыру болып табылады
  

Бағдарлама мәтіні

const int N = 10;

void main()

{ int i, j, nMin, A[N], c;

for ( i = 0; i < N-1; i ++ )

{ nMin = i;

for ( j = i+1; j < N; j ++ ) ;

if ( A[j] < A[nMin] ) nMin = j;

if ( nMin != i )

{ c = A[i]; A[i] = A[nMin]; A[nMin] = c; }

}

printf("\n Отсортированный массив:\n");

for ( i = 0; i < N; i ++ )

printf("%d ", A[i]);

}
Кірістіру әдісімен сұрыптау - Insertion sort

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

Бағдарлама мәтіні

const int N = 10;

void main()

{ int i, j, nMin, A[N], c;

for ( i = 1; i < N; i ++ )

{ c = A[i];

j = i -1;

while (j > =0 && A[j] > c) A[j+1] = A[j--];

A[j+1] = c;

}

printf("\n Отсортированный массив:\n");

for ( i = 0; i < N; i ++ )

printf("%d ", A[i]);

}
Алмасу әдісімен сұрыптау - Bubble sort

• 
  Бұл сұрыптау әдісі "көпіршік әдісі" деп аталады және көрші элементтердің жұптарын бірнеше рет ретке келтіруден тұрады
  

Бағдарлама мәтіні

const int N = 10;

void main()

{

int i, j, A[N], c;

for ( i = 0; i < N-1; i ++ )

for ( j = N-2; j >= i; j -- )

if ( A[j] > A[j+1] )

{

---

c = A[j]; A[j] = A[j+1]; A[j+1] = c;

}

printf("\n Отсортированный массив:\n");

for ( i = 0; i < N; i ++ ) printf("%d ", A[i]);

}
Араластыру арқылы сұрыптау (шейкер арқылы сұрыптау)

Шейкер сұрыптау көпіршікті сұрыптаудан ерекшеленеді, өйткені ол екі бағытты: алгоритм қатаң солдан оңға емес, алдымен солдан оңға, содан кейін оңнан солға жылжиды.
Тарақты сұрыптау- Comb sort

Тарақты сұрыптау-көпіршікті сұрыптауды жақсарту. Оның идеясы алгоритмді баяулататын массивтің соңында шамалы мәндері бар элементтерді "жою" болып табылады. Егер массивті сұрыптау кезінде көпіршікті және шайқауды сұрыптау көрші элементтерді салыстырса, онда" тарақпен " алдымен салыстырылатын мәндер арасында жеткілікті үлкен қашықтық алынады, содан кейін ол минимумға дейін созылады. Бастапқы алшақтық кездейсоқ таңдалмауы керек, бірақ арнайы шаманы ескере отырып — оңтайлы мәні 1,247 болатын азайту факторы.
Сұрыптау бірігуі - Merge sorting

Біріктіру арқылы сұрыптау элементтерге қол жетімділік дәйекті түрде жүзеге асырылатын деректер құрылымдары үшін пайдалы (мысалы, ағындар үшін).

Мұнда массив шамамен екі тең бөлікке бөлінеді және олардың әрқайсысы бөлек сұрыпталады. Содан кейін сұрыпталған екі массив біреуіне біріктіріледі.

Шелл сұрыптау- Shell sort

Шелл сұрыптау кезінде алдымен бір-бірінен d қашықтықта тұрған мәндер салыстырылады және сұрыпталады.

Осыдан кейін процедура кейбір кіші d мәндері үшін қайталанады және Shell сұрыптау d=1 элементтерін ретке келтіру арқылы аяқталады (яғни, кірістірулермен әдеттегі сұрыптау). Тиімділігі сұрыптау Шелла белгілі бір жағдайларда қамтамасыз етіледі, бұл элементтер" тезірек " өз орындары турады

Тез сұрыптау (Хоар әдісі)- Quiсk sort

• 
  Тірек элементі таңдалады (мысалы, массивтің ортасында).
  
• 
  Массив солдан оңға қарай қарастырылады және тірекке қарағанда жақын элементті іздейді.
  
• 
  Массив оңнан солға қарай қарастырылады және тіректен Кіші ең жақын элементті іздейді.
  

Табылған элементтердің орындары ауыстырылады.

---

Смотрите также файлы

• Программа производственной практики (по профилю специальности) по пм. 03.pdf

• Генная и генетическая инженерия.docx

• 1. Устройство для чтения мыслей.ppt

• реферат на тему титанизм.docx

• 1 теоретические аспекты закупочной деятельности 12.doc