ထည့်သွင်းမှုအမျိုးအစား


ခက်ခဲအဆင့် အလယ်အလတ်
မကြာခဏမေးတယ် Accenture Cisco သည် Dell က မြဝတီ သမ်ကွန်ယက် MAQ Veritas
အခင်းအကျင်း sorting

insertion sort algorithm ကို အသုံးပြု၍ ပေးထားသော unsorted array ကို sort လုပ်ပါ။

input: {9,5,1,6,11,8,4}

output: {1,4,5,6,8,9,11}

သဘောတရား

  • Insertion Sort သည်နံပါတ်များကိုလူသားများကဲ့သို့တူညီသောနည်းဖြင့်နံပါတ်ခွဲသည် (ကဒ်ပြားဟောင်း) ။
  • နံပါတ်ကို unsorted array (right subarray) မှ sorted array (left subarray) ထဲကဘယ်ဘက် subarray ကို sort လုပ်ထားတယ်။
  • ၎င်းသည်ချဉ်းကပ်မှုအခြေခံသည့်နည်းလမ်းဖြစ်သည်။

ထည့်သွင်းအမျိုးအစား Algorithm

  1. unsorted ခင်းကျင်းထဲမှပထမဆုံး element ကိုရွေးချယ် / မှတ်သားပါ၊ ၎င်းကို sorted array ရှိမှန်ကန်သောနေရာသို့ရွှေ့ပါ။
  2. unsorted ခင်းကျင်းထားသည့်နောက် element တစ်ခုသို့ marker ကိုတိုးပါ။

ထည့်သွင်းမှုအမျိုးအစား

C ++ အစီအစဉ်

#include <iostream>
using namespace std;

void insertSort(int arr[],int n)
{
    int i,j,save;

    for(int i=1;i<n;i++)
    {
        j = i-1;
        save = arr[i];
        
        // look for correct position of arr[i]
        while(j>=0 && arr[j] > save)
        {
            // shifting array elements towards the right
            arr[j+1] = arr[j];
            j--;
        }
        // place arr[i] at the correct position
        arr[j+1] = save;
    }
}

int main()
{
    
    int arr[] = {9,5,1,6,11,8,4};
    int n = sizeof(arr)/sizeof(arr[0]);

    insertSort(arr,n);

    for(int i=0;i<n;i++)
    cout<<arr[i]<<" ";
    
    return 0;
}

output

1 4 5 6 8 9 11

Java အစီအစဉ်

class iSort
{
    static void insertSort(int arr[])
    {
        int n = arr.length;
        int i,j,save;

        for(i=1;i<n;i++)
        {
            j = i-1;
            save = arr[i];

            // look for correct position of arr[i]
            while(j >= 0 && arr[j] > save)
            {
                // shifting array elements towards the right
                arr[j+1] = arr[j];
                j--;
            }
            // place arr[i] at the correct position
            arr[j+1] = save;
        }
    }

    public static void main(String args[]) 
    {
        int arr[] = {9,5,1,6,11,8,4};
        insertSort(arr);

        for(int i=0;i<arr.length;i++)
        System.out.print(arr[i] +" ");   
    }
}

output

1 4 5 6 8 9 11

ရှုပ်ထွေးဆန်းစစ်ခြင်း

  • အချိန်ရှုပ်ထွေးမှု: T က ()) = အို (။2)
  • ဒါဟာအို (။2) ခင်းကျင်းမှုအားပြောင်းပြန်စီစဉ်နှင့် O (time) အချိန်ကိုခင်းပေးသည်။
  • အာကာသရှုပ်ထွေးမှု: A (n) = အို (၁)

နောက်ဆက်တွဲသတင်းအချက်အလက်

  • Insertion Sort သည်နေရာခွဲခြင်း algorithm ဖြစ်သည်။
  • ၎င်းသည်တည်ငြိမ်သောသဘောသဘာဝဖြစ်သည်။
  • Insertion Sort သည် input ခင်းခြင်းနီးပါးကိုစီစဉ်တွင်အသုံးဝင်သည်။ အနည်းငယ်သောအစိတ်အပိုင်းများသာမပြည့်စုံသောကြီးမားသောခင်းကျင်းမှုကိုနေရာချထားသည်။
  • Sort လုပ်ရန်ခင်းကျင်းထားသည့်အရွယ်အစားသေးငယ်သည့်အခါ၎င်းသည်အသုံးဝင်သည်။

အညွှန်း  အင်တာဗျူးမေးခွန်းများ။