Сұрыптау. Информатика, 9 сынып, презентация.

Массивтер

Сұрыптау

Блиц сауалнама

Ретке келтіру, сұрыптау сөздерін калай түсінесіз?

Масив элементері немесе ретке келтірілген айнымалылар қалай орналасуы мүмкін?

Текстік ақпараттар қалай ретке келтірілетінін түсіндіріп беріңіз?

Массивтерді декларациялау

Бірөлшемді массив:

int a[5] = { 3, 45, 11, -8, 74};

double q[4] = {1.7, 4.53};

Екінші жағдайда, массивтің x алғашқы екі элементі тек инициализацияланады, қалған екі элементтер нөлдік мәндер алады.

Егер инициализация тізімі бар болса, алаптың өлшемін шығаруға болмайды, ол инициализация мәндерінің санымен анықталады :

int a[ ] = { 3, 45, 11, -8, 74};

Массив элементтеріне өтініш

Нөлден бастап индекстеу арқылыжүзеге асады, сандық индекстерді шығарады

Массив жағдайында экстракция операциясы «тік жақшалар» екілік операция болып табылады,

Бірінші операнд - массивтің атауы, екіншісі - тік жақшаға салынған бүтіндік өрнек

a[0] = a[i] + a[2 * i +1];

Назар аударыңыз, операция [] коммутативті, яғни, айырбасталатын операндалар :

0[a] = i[a] + (2 * i +1)[a];

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

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

Үш қарапайым сұрыптау алгоритмін қарастырайық:

іріктеу бойынша сұрыптау,

қосу арқылы сұрыптау,

биржалық сұрыптау

Іріктеу бойынша сұрыптау

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

Бағдарлама тексті

const int N = 10;

void main()

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

// здесь нужно ввести массив A

for ( i = 0; i < N-1; i ++ ) // 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]);

}

Қосымшалар бойынша сұрыптау

Массивтің сұрыпталған бөлігі, сонымен қатар элементтердің дәйекті бөлігінен дәйекті түрде қосылады.

Дегенмен, қазір бөлісілмеген бөліктің бірінші элементі келесі түрде қабылданады.

Сұрыпталған бөлікте орналастыру оның сұрыпталым тәртібін сақтау үшін таңдалады

Бағдарлама тексті

const int N = 10;

void main()

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

// здесь нужно ввести массив A

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]);

}

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

Бұл сұрыптау әдісі «көпіршікті әдіс» деп аталады және көрші элементтердің жұптарын қайталану тәртібінде тұрады.

Бағдарлама тексті

const int N = 10;

void main()

{

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

// здесь надо ввести массив A

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; // переставить A[j] и A[j+1]

}

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

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

}

Әдістрді салыстыру

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

Жұптық жұмыс (5 мин)

Бағдарламаның үзінділерін құрастыру

Бағалау критерийлерін алдын ала анықтау

Бағдарламаларды көрсету

Бағалау критерийлері негізінде бір-бірінің өзара бағалау

Әртүрлі алгоритмдердің артықшылықтары туралы пікірталас

Құрастырылған бағдарламаларды компьютерге енгізу және тестілеу

Мұғалімге хат.