Дәріс №5. Шелл іріктеуі.

Дә рістің мақ саты – студенттерді берілген ә діспен таныстыру жә не сұ рыптаудың негізгі амалдарымен таныстыру.

Шелл ә дісі қ осулар ә дісінің жақ сартылғ ан нұ сқ асы.

Шелл ә дісінің алгоритмі екі негізгі амалдың кө п рет қ айталанудан тұ рады:

 бір ереже бойынша массивтің кейбір элементтерін біріктіру

 біріктірілген элементтер арасында ә деттегідей қ осу ә дісімен сұ рыптау

Бірінші кезең де жеткілікті улкен қ адамды кіріс жиынның элементтері топталады. Мысалы, барлық 1000-ші элементтер, яғ ни топтар қ ұ растырылады:

Топ 1: 1, 1001, 2001, 3001 жә не т.б.

Топ 2: 2, 1002, 2002, 3002 жә не т.б.

Топ 3: 3, 1003, 2003, 3003 жә не т.б.

.....................

Топ 1000: 1000, 2000, 3000 жә не т.б.

Ә р топтың ішінде ә деттегідей қ осу сұ рыптауы орындалады, бұ л топтағ ы элементтер саны аз болғ андық тан тиімді болады.

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

..........

Соң ғ ы кезең де басында топтасы 1 қ адаммен орындалады, бұ л n ө лшемді тек бір жиынды қ ұ растырады, содан кейін – практикалық тү рде сұ рыпталғ ан жиын іріктіріледі.

Мысалы. Берілген жиын: 15 – 33 – 42 – 07 – 12 - 19

3 санына тең қ адаммен бө леміз, бізде 2 элементтен тұ ратын і топ бар, ә рқ айссысын жеке жеке сұ рыптаймыз:

топ 1: 15 – 07 => 07 – 15 (1 салыстыру, 1 ауыстыру)

топ 2: 33 – 12 => 12 – 33 (1 салыстыру, 1 ауыстыру)

топ 3: 42 – 19 => 19 – 42 (1 салыстыру, 1 ауыстыру)

сандардың жаң а жиыны: 07 – 15 – 12 – 33 – 19 – 42

2 санғ а тең 3 элементтен бө леміз, олар жеке сұ рыпталады:

топ 1: 07 – 12 – 19 => реттелген (2 салыстыру, 0 ауыстыру)

топ 2: 15 – 33 – 42 => реттелген (2 салыстыру, 0 ауыстыру)

сандардың жаң а жиыны: 07 – 12 – 19 – 15 – 33 – 42

Соң ғ ы қ адамы 1 тең бө лу сандардың керекті жиынын береді; оғ ан 5 салыстырулары бар қ осу іріктеуі қ олданылады жә не тек бір орын ауыстыру орындалады, сонымен біз нә тижеге ие боламыз.

Сонымен – 12 салыстыру жә не 4 ауыстыру, алдында қ арастырылғ ан ә дістерден жақ сырақ емес. Бірақ мұ нда екі факторды ескеру керек.

1, 3, 5, 9, 17, 33,... (жалпы формула: t_k = (2* t_k-1) –1)

1, 3, 7, 15, 31, 63, 127, 255, 511, 1023, 2047, 4095, 8191, 16383, 32767... (жалпы формула: t_k = (2* t_k-1) +1, ал қ арапайымы – (2^k – 1)).

Бағ дарламалық тү рде іске асыру

for m: = 1 to t do {t – топтасудың қ адамдарының саны, m – қ адамның номірі}

Begin

k: = h [m]; {берілген массивте қ адамның ө лшемін таң дау }

for i: = k + 1 to n do {қ осу сұ рыптауы ә р топтың ішінде }

Begin

temp: = a [i]; j: = i – k;

While (j > 0) and (temp < a [j]) do

Begin

a [j + k]: = a [j]; j: = j – k;

end;

a [j + k]: = temp;

end;

end;

Шелла ә дісінің кү рделілігі O(n^{1, 2}) сә йкестікпен бағ аланады, бұ л қ арапайым ә дістерге қ арағ анда ә лде қ айда жақ сы.

№5 дә рістің бақ ылау сұ рақ тары

1. Шелл ә дісі неде негізделеді?

2. Бұ л ә діс ө зінің атын неден алды?

3. Берілген ә діс сқ рыптау ә дістерінің қ ай классына жатады?

4. Берілген ә дістің кү рделілігі қ алай бағ аланады?

5. Шелл ә дісінің тиімділігі неге тә уелді?

Дә ріс №6. Бө луі бар сұ рыптау (жылдам сұ рыптау)

Дә рістің мақ саты- студенттерді жақ сартылғ ан ә дістердің біоеуң мен таныстыру, негізгі терминдермен жә не тү сініктермен таныстыру.

Бө луі бар ә діс Чарльзом Хоаром деген ғ алыммен 1962 жылы ұ сынылды.

Кесте 6. Жылдам сұ рыптаудың мысалысы

Алгоритм тектен тек жылдам деп атамағ ан, ө йткені, оның салыстырулар жә не алмасулар саны O(n? log n) жазбасымен бағ аланады.

№6 дә рістің бақ ылау сұ рақ тары

1. Жылдам сұ рыптаудың негізгі идеясы неде?

2. Бұ л ә діс кіммен ұ сынылды?

3. Негі бұ л ә діс жылдам сұ рыптау деп аталады?

4. Жылдам сұ рыптау алгоритмімен қ олданып бір мысал келтірің із?