|
Біз осы бөлімде массив элементтерін сұрыптаудың тек екі әдісінің алгоритмдерін және бағдарламалақ жүзеге асырылуын қарастырамыз.
6.2.1 Таңдау әдісімен сұрыптау алгоритмі. Массив элементтерін таңдау әдісімен, кему тәртібінде сұрыптау алгоритмі келесі амалдардың орындалуын болжайды.
Массивтің бірінші элементін қарастырамыз, оның мәнін массивтің қалған басқа элементтерімен кезекпен салыстырамыз (2-ден соңғы элементке дейін). Егер мәні үлкен элемент кезіксе, онда ол бірінші элементпен орын ауыстырады. Массивті бірінші рет тексерудің нәтижесінде бірінші элемент ең жоғары мәніне ие болады.
Содан кейін екінші элементті қарастырамыз, оның мәнін массивтің қалған басқа элементтерімен кезекпен салыстырамыз (3-ден соңғы элементке дейін). Массивті екінші рет тексерудің нәтижесінде біз сұрыпталған массивтің екінші элементінің мәнін анықтаймыз. Тексеру массивтегі соңғының алдында тұрған элементіне дейін осылай қайталанады, соңғы тексеруде массивтің алдынғы элементі массивтің соңғы элементімен ғана салыстырылады.
Алынған массив элементтерінің мәні кему тәртібінде реттеледі.
Массив элементтерінің саны N-ге тең болса, алгоритмде орындалатын салыстыру операцияларының саны (О.С.) келесі түрде есептеледі:
К.О. = (N-1)+(N-2)+(N-3)+ . . . + 2 +1=N·(N-1)/2 (7)
Осы өрнек алгоритмнің есептеу тиімділігін сипаттайды.
6.1-есеп. 11 кездейсоқ бүтін сандардан тұратын, минус 50-ден 50-ге дейінгі аралықта a массивін құр. Оны шығару керек. Массив элементтерін кему тәртібінде сұрыптауды орындау және жаңа массивті шығару.
Массив элементтерін кему тәртібінде сұрыптау алгоритмінің бағдарламалық іске асырылуын қарастырайық.
Бағдарламаның коды:
using System;
namespace ConsoleApplication1
{
class Program
{
static void Main()
{ int i, j, b;
int[] a = new int[11];
Random rnd = new Random();
// массивті құру және экранға шығару
Console.Write("Massivti syriptaganga dein: ");
for (i = 0; i <= 10; i++)
{
a[i] = rnd.Next() % 101 - 50;
Console.Write(" {0}", a[i]);
}
Console.WriteLine();
//таңдау әдісі арқылы массив элементтерін сұрыптау
for (i = 0; i <= 9; i++)
for (j = i + 1; j <= 10; j++)
if (a[i] < a[j])
{ b = a[i]; a[i] = a[j]; a[j] = b; }
//сұрыптаудан кейін массивті экранға шығару
Console.Write("Massivti syriptagannan kein: ");
for (i = 0; i <= 10; i++)
Console.Write(" {0}", a[i]);
Console.WriteLine();
Console.ReadLine();
}
}
}
Бағдарлама жұмысы:
Massivti syriptaganga dein: 11 16 47 9 5 14 41 18 -2 -31 49
Massivti syriptagannan kein: 49 47 41 18 16 14 11 9 5 -2 -31
6.2.2 «Көпіршікті» әдіспен сұрыптау алгоритмі. Массив элементтерін өсу тәртібінде «көпіршікті» әдіспен сұрыптау алгоритмі келесі әрекеттердің орындалуын қарастырады.
Массивтің бірінші элементін екіншісімен салыстырамыз және егер біріншісі үлкен болса, онда олар орындарын алмастырады. Одан кейін массивтің екінші элементі үшіншісімен салыстырылады, егер екінші элемент үлкен болса, онда олар орындарын алмастырады және т.с.
Массивті бірінші рет «қарап шығудың» нәтижесінде массив элементінің ең үлкен мәні ең соңына жазылады.
Массивтің бірінші элементін қайтадан аламыз және оны екінші элементпен салыстырамыз – барлық процесті массивтің соңғы тұрған элементтің алдындағы элементке дейін қайталаймыз - оның мәнін құрамыз.
Соңғы салыстыру операциясына дейін осылай қайталанады.
Сонымен массив элементерінің мәні өсу ретімен сұрыпталады.
«Көпіршікті» және таңдау әдістері алгоритмдерінің есептеу тиімділіктері бірдей.
Мысал ретінде алдынғы 6.1-есебін қарастырайық.
Массив элементтерін кему тәртібінде «Көпіршікті» әдіспен сұрыптау алгоритмінің бағдарламалық жүзеге асырылуын қарастырайық.
Бағдарламаның коды:
using System;
namespace ConsoleApplication1
{
class Program
{
static void Main()
{
int i,j,b;
int[] a = new int[11];
Random rnd = new Random();
// массивті құру және экранға шығару
Console.Write("Massivti syriptaganga dein: ");
for (i = 0; i <= 10; i++)
{
a[i] = rnd.Next()%101 - 50;
Console.Write(" {0}", a[i]);
}
Console.WriteLine();
// «көпіршікті» әдісі арқылы массив элементтерін сұрыптау
for (i=0; i<=9; i++)
for (j=0; j<=9-i; j++)
if (a[j]
{ b=a[j];a[j]=a[j+1];a[j+1]=b;}
// сұрыптаудан кейін массивті экранға шығару
Console.Write("Massivti syriptagannan kein: ");
for (i=0; i<=10; i++)
Console.Write(" {0}", a[i]);
Console.WriteLine();
Console.ReadLine();
}
}
}
Бағдарлама жұмысы:
Massivti syriptaganga dein: -26 -19 32 35 -19 -44 -35 36 10 -49 -5
Massivti syriptagannan kein: 36 35 32 10 -5 -19 -19 -26 -35 -44 -49
Әлбетте әрбір қарастырылған алгоритмді массив элементтерін өсу немесе кему бойынша сұрыптау үшін қолдануға болады.
Егер басқа сұрыптау алгоритмдерімен танысқыңыз келсе, Д.Кнуттың «Искусство программирования для ЭВМ» кітабын ұсынамыз, «сұрыптау мен іздеу» сұрақтарына арналған 3-том, көлемі 843 бет.
Достарыңызбен бөлісу: | 
