26-блог: “Дигирман” - Merge Sort дегенимиз не? / "Digirman" - Merge Sort degenimiz ne?

"Дигирман" рубрикасы астында программаластырыўға байланыслы кеңейтилген, жоқары басқыштағы темалар ҳаққында жазыўға ҳәрекет етемен. "Дигирман" рубрикасындағы блогларды оқып түсиниў ушын сизде бағдарлама жазыў ҳәм информациялық технологиялар бойынша аз болса да дәслепки билим болыўы керек.

Программаластырыўда "саралаў, сортлаў, ретлестириў, тәртипке салыў" деген түсиник жүдә әҳмийетли. Сортлаўшы алгоритмлер компьютердиң өнимдарлы ислеп, керекли мағлыўматты тез таўып, тез тәртипке салыўына жәрдем береди. Сондай сортлаўшы алгоритмлердиң ең кең тарқалғаны ҳәм бираз қыйыны бул merge sort болады. Қарақалпақшасына "биригиўши сортлаў" деп алсақ болады.

"Биригиўши сортлаў" (merge sort) дегенимиз не?

Биригиўши сортлаў ҳаққында түсиндириўден алдын, бир-еки қосымша темаларды түртип өткен пайдалы.

1. "Бөлип тасла ҳәм басқар"

Бул классикалық стратегия ҳаққында мектепте тарийх сабағында бир-еки рет үйренген шығарсыз деп ойлайман. Ол әййемги дәўирлерден берли бир неше император ҳәм басқарыўшылар менен байланыстырылып айтылатуғын "бойсындырыў" стратегиясы болады.

Ал, компьютер илиминде қандай да бир мәселени шешиў ушын қолланылатуғын усыл/жантасыў есапланып, ол берилген мәселени кишкене мәселелерге бөлип, биримлеп шешип, соңында улыўмалық шешимге келиў деген мәнисти билдиреди. Бир қанша сортлаўшы алгоритмлер "бөлип тасла ҳәм басқар" усылынан пайдаланады.

Бул тактика компьютер илиминде қурамалы ҳәм қыйын сораўларды әпиўайыластырып, системалы түрде шешиў барысын аңсатластырып береди.

2. Рекурсия

Рекурсия ҳаққында басқа блогымда кең түрде түсиндирип жазаман. Бирақ, "Дигирман" рубрикасын арнайы оқыўшылар рекурсия не екенин жақсы биледи деп ойлайман.

Рекурсия бул компьютер илиминде әҳмийетли структуралардың бири болып, ол берилген мәселени кишкене бөлимлерге бөлип шешиў ушын функцияның өзин-өзи тәкирарлап иске қосыў процесин билдиреди.

Демек, "биригиўши сортлаў" дегенимиз не?

"Биригиўши сортлаў" бул "бөлип тасла ҳәм басқар" усылынан пайдаланып, салыстырыўға тийкарланып, берилген дизимди (array, list) сортлайтуғын алгоритм есапланады.

Ол дизимди ең соңғы кишкене бөлегине шекем бөлип, салыстырып, сортлап, қайтадан сол сортланған бөлеклерди бириктиреди.

Ҳәр дайым айтқанымдай, мысал менен аңсат уғып алғанға ҳеш нәрсе жетпейди.

Карта ойнап көргенсиз бе? Жаслықта қоңсы балалар менен карта да ойнайтуғын едик. Базыда берилген картаны ең кишкенесинен баслап тузға шекем биримлеп тақлайтуғын едик.

Картаны сортлаўдың да бир қанша усылы бар. Мәселен, картаның ҳәммесин жерге жайып, биримлеп қарап, салыстырып, кишкенесинен баслап терип сортлаў. Ўақыт көп кетеди.

Яки "биригиўши сортлаў" алгоритминен пайдалансақ болады. Сиз де бул усылды қолланып көргенсиз. Бирақ атын билмеўиңиз мүмкин.

Карта ойнаўға келген 3 достыңыз бар деп алайық. Араластырылған 36 дана картаны ортасынан екиге бөлейик. Ҳәр еки бөлекти ярымынан және екиге бөлсек, 9 дана картадан ибарат 4 бөлек пайда болады. Енди сол төрт бөлекти 4 адам өз-ара бөлисип алайық.

36 дана картаны бирден сортлағаннан көре тоғыз дана картаны сортлаған аңсатлаў. Бирақ, тоғыз дана картаны сортлағаннан көре 4 дана картаны сортлаған әдеўир жеңил келеди. Демек, енди өзимиз сол 9 картаны алып, және еки бөлекке бөлейик.

Бир қолымызда 4 дана карта, бир қолымызда 5 дана карта бар.

Биринши 4 дана картаны сортлайық. Сортлаў ушын карталардың мәнисин бир-бири менен салыстырамыз. Мәселен, қолымызда дама, король, десятка, шестёрка бар деп елестетип көрейик.

Сол төрт картаны шестёрка, десятка, дама, король деп сортлаўымыз мүмкин.

Черви, пики, крест яки бубни деген мәнисти қәлегенимизше сортлаўға болады.

Екинши қолымыздағы қалған бес картаны да солай сортлайық.

Семёрка екеў, девятка биреў, десятка биреў, валет биреў.

Енди қолымыздағы еки бөлек картаны бирге бириктирейик. Оның ушын еки бөлектеги карталарды бир-бири менен салыстырамыз.

Дәслеп шестёрка менен семёрканы салыстырамыз. Себеби усы еки карта жоқарыда сортланған еки карта бөлегинде биринши келеди. Шестёрканы аламыз. Себеби ол жетиден киши.

Енди, десятка менен семёрканы салыстырамыз. Еки дана семёрканы алып, оны шестёрканың изине тиркеймиз.

Кейин десятка менен девятканы салыстырамыз. Девятканы аламыз ҳәм оны семёрканың изине тиркеймиз.

Одан кейин, десятка, десятка, валет, дама, король деп биримлеп тиркеп бириктиремиз.

Бизлер тоғыз дана картаны усылай сортлап болдық:

Шестёрка, семёрка екеў, девятка, десятка, десятка, валет, дама, король.

Енди тап усы тәризде досларымыздың сортлаған карталарын бирге салыстырып, бириктиремиз.

"Биригиўши сортлаў" алгоритми де тап усы барыста әмелге асады.

1. Берилген дизимди ең кишкене бөлеклерге бөлип таслаймыз.
2. Кишкене бөлеклерди сортлаймыз.
3. Сортланған бөлеклерди бириктиремиз.

Енди нағыз array (дизим, массив) жәрдеминде мысал келтирейик. Java бағдарлама тили жәрдеминде код (коуд) пенен қалай жазылатуғынын көрсетемен.

Төмендеги санлы дизимди сортлаўымыз керек деп алайық:

[2, 27, 43, 3, 9, 82, 10]

A. Жоқарыдағы дизимди еки бөлекке бөлемиз

• Шеп тәреп: [2, 27, 43]
• Оң тәреп: [3, 9, 82, 10]

B. Оң ҳәм шеп тәрепти және өз алдына еки тәрепке бөлемиз

• Шеп тәреп: [2] ҳәм [27, 43]
• Оң тәреп: [3, 9] ҳәм [82, 10]

C. Бөлинген бөлеклерди ең ақырына шекем және бөлемиз

• Шеп тәреп: [2], [27], [43]
• Оң тәреп: [3], [9], [82], [10]

D. Пайда болған бөлеклерди сортлаймыз

Бир бөлек санларды салыстырамыз ҳәм бириктиремиз.

• Шеп тәреп: [2, 27], [43]
• Оң тәреп: [3, 9], [10, 82]

E. Салыстырып, бириниң изине бирин тиркеўди даўам етемиз

• Шеп тәреп: [2, 27, 43]
• Оң тәреп: [3, 9, 10, 82]

F. Енди оң ҳәм шеп тәрепти салыстырып, бириниң изине бирин тиркеўди даўам етемиз

[2, 3, 9, 10, 27, 43, 82]

Енди, биригиўши алгоритмди Java тилинде жазып көрейик

import java.util.Arrays;
 
public class MergeSort {
 
  public static void main(String[] args) {
    int[] array = {2, 27, 43, 3, 9, 82, 10};
 
    System.out.println("Сортланбаған дизим:");
    System.out.println(Arrays.toString(array));
 
    mergeSort(array, 0, array.length - 1);
 
    System.out.println("Сортланған дизим:");
    System.out.println(Arrays.toString(array));
  }
 
  public static void mergeSort(int[] array, int left, int right) {
    if (left < right) {
      int middle = (left + right) / 2;
 
      mergeSort(array, left, middle);
      mergeSort(array, middle + 1, right);
      merge(array, left, middle, right);
    }
  }
 
  public static void merge(int[] array, int left, int middle, int right) {
    // Ярымына бөлинген бөлектиң узынлығын таўып аламыз
    int n1 = middle - left + 1;
    int n2 = right - middle;
 
    // Бөлинген бөлеклерден ўақытша дизим жаратамыз
    int[] leftArray = new int[n1];
    int[] rightArray = new int[n2];
 
    // Ўақытша дизимлерди оригинал дизимдеги дурыс мәнислер менен толтырамыз
    for (int i = 0; i < n1; i++) {
      leftArray[i] = array[left + i];
    }
 
    for (int j = 0; j < n2; j++) {
      rightArray[j] = array[middle + 1 + j];
    }
 
    // Бириктириў жумысын баслаймыз
    int i = 0; // Шеп тәреп ушын көрсеткиш
    int j = 0; // Оң тәреп ушын көрсеткиш
    int k = left; // Оригинал дизим ушын көрсеткиш
 
    // Еки мәнисти салыстырып, киши мәнисти биринши терип алып, бириктиремиз
    while (i < n1 && j < n2) {
      if (leftArray[i] <= rightArray[j]) {
        array[k] = leftArray[i];
        i++;
      } else {
        array[k] = rightArray[j];
        j++;
      }
      k++;
    }
 
    // Аўысып қалған мәнислерди солай көширемиз
    while (i < n1) {
      array[k] = leftArray[i];
      k++;
      i++;
    }
 
    while (j < n2) {
      array[k] = rightArray[j];
      j++;
      k++;
    }
  }
}

Жоқарыдағы код бул биригиўши сортлаў алгоритминиң Java тилинде жазылған көриниси. Бул кодта рекурсиядан пайдаланылған. mergeSort() функциясы берилген дизимди ең кишкене бөлекке шекем бөлиў ушын өзин-өзи "иске қосады". Ҳәм ең соңында ең кишкене бөлектен баслап салыстырып, сортлап, бириктирип баслайды.