Қою (орналастыру) арқылы сұрыптау

Бала кезде карта ойнайтын едік. Сол кезде картаны кішіден үлкенге қарай сұрыптау әдетіміз болатын. Ол үшін не істейсің, кішкентай карталарды солға қарай, үлкендерді оңға қарай орналастыру арқылы сұрыптайсың. Қарапайым сұрыптау алгоритмдерінің екінші түрі тура осы тәсілмен орындалады және «Орналастыру арқылы сұрыптау» деп аталады.


Айталық сізге массив берілді. Бұл массив элементтерін «Орналастыру арқылы сұрыптау» тәсілімен төменнен жоғары қарай былай сұрыптаймыз:
Массивтің екінші элементін аламыз оны бірінші элементпен салыстырамыз, егер екінші элемент бірінші элементтен кіші болса, екінші элементті біріншінің, бірінші элементті екеншінің орнына орналастырамыз. Егер екінші элемент бірінші элементтен үлкен немесе тең болса, ешнәрсе істемей процессті жалғастыра береміз. Сосын үшінші элементті алып екінші элементпен салыстырамыз, егер үшінші элемент екінші элементтен кішкентай болса, олардың орындарын ауыстырамыз, содан кейін (екіншінің орнына келген үшінші элементті) бірінші элементпен салыстырамыз. Осы процесс массив аяқталғанша жалғаса береді. Соңында элементтері сұрыпталған массивке қол жеткіземіз.

Айтқандарымызды кодпен жаза кетейік (Java тілінде):

package Alg;

import java.util.Arrays;

public class InsertionSortTest {
    
    static public void main(String[] args)
    {
        int[] a = {4,5,2,45,32,98,44,55,123}; //берілген массив
        for(int i = 1; i < a.length; i++)
        {
            for(int j = i; j > 0 && (a[j] < a[j-1]); j--)
            {
                int temp = a[j];
                a[j] = a[j-1];
                a[j-1] = temp;
            }
        }
        
        System.out.println(Arrays.toString(a));
    }
}

Бұл кодтың нәтижесінде сұрыпталған мынадай массив шығады:

[2, 4, 5, 32, 44, 45, 55, 98, 123]

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

«Орналастыру арқылы сұрыптау» алгоритмінің видеосын тамашалай отырыңыздар: