Дӯкони Sort


Сатҳи душворӣ миёна
Аксар вақт пурсида мешавад 24 * 7 Озмоишгоҳҳои инноватсионӣ Amazon себ Белзабар Шабака Oracle Samsung SAP Лабораторияҳои SAP Visa
тартиботи ҳарбӣ Sorting

Hap sort - ин як усули ҷобаҷогузории дар муқоиса асосёфта мебошад, ки ба сохтори маълумотҳои Dual Heap асос ёфтааст. HeapSort ба як навъ интихоб монанд аст, ки дар он элементи ҳадди аксарро пайдо мекунем ва пас он элементро дар охири он ҷойгир мекунем. Мо ин равандро барои унсурҳои боқимонда такрор мекунем.

Бо назардошти як массиви номураттаб, онро бо ёрии Heap Sort ҷудо кунед

Дар ин ҷо вуруди додашуда массиви номураттаб аст ва мо бояд массивро бо ёрии heap sort ба тартиб дарорем.

вуруди: 9,5,1,6,11,8,4

Натиҷаи: 1,4,5,6,8,9,11

Алгоритми решакан кардани навъҳо

  • HeapSort як алгоритми муқоисавӣ мебошад, ки дар охири массив унсури максимумро мегузорад ва раванди унсурҳои боқимондаи массивро то ба тартиб даровардани тамоми массив такрор мекунад.
  • Heap Sort аз массиви max-heap дуӣ месозад. Max heap сохтори маълумоти дарахт аст ки дар он ҳар як гиреҳи волидайн аз гиреҳи фарзанди худ бузургтар аст.
  • Array arr [] метавонад ҳамчун як дарахти дуӣ нишон дода шавад,
    1. arr [0] гиреҳи реша аст.
    2. Индекси кӯдакони чап = 2 * i + 1
    3. Индекси кӯдакони рост = 2 * i + 2

Дар куҷо i индекси гиреҳи волидайн мебошад.

  • Дарахти дуӣ бо истифода аз a ба теппаи дуӣ табдил дода мешавад Хап кардан амалиёт, ин амал арзиши гиреҳи волидайнро нигоҳ медорад, ки аз гиреҳи кӯдак бузургтар аст (Макс нурӣ). Агар гиреҳи волидайн аз гиреҳи кӯдак камтар бошад, он гоҳ волидро бо гиреҳи фарзанд бо арзиши аз ҳама калон иваз мекунад.

Намунаи амалиёти Max Heap

Дар зер амалиёти максималии дарахте оварда шудааст, ки арзиши решаи он 0, кӯдаки чап 5 ва фарзанди рост 4 мебошад.

Дӯкони Sort

Алгоритм

Мо асосан ду функсияро дар алгоритми ҷобаҷогузорӣ истифода мебарем.

  1. heapServe (arr, i, n) - мезанад ith гиреҳи arr []
  2. партовгоҳ (arr, n) -
    1. он аввал тамоми массивро heapizes (бо heapifying гиреҳҳои барге).
    2. элементи калонтаринро дар реша ҷудо мекунад.
    3. онро бо унсури охирини массив иваз мекунад.
    4. то раванди ба даст овардани массиви комилан мураттаб раванди a, b, c -ро (ба тартиб) такрор мекунад. Дар куҷо a heapServe аст (функсияи хидматрасонӣ барои тартиб додани теппа), b heapSort аст ва c решаи иқтибос аст.

Дӯкони Sort

Дӯкони Sort

Дӯкони Sort

Барномаи C ++ барои Sort Heap

#include <iostream>
using namespace std;

// service function to heapify array
void heapServe(int arr[],int i,int n)
{
    int large = i;
    // index of left and right child
    int left = 2*i+1;
    int right = 2*i+2;

    // find largest amongst parent ,left and right children
    if(left < n && arr[left] > arr[large])
    large = left;
    if(right < n && arr[right] > arr[large])
    large = right;

    // swap if parent node is not largest
    // recursiveley heapify swapped nodes
    if(large != i)
    {
        swap(arr[i],arr[large]);
        heapServe(arr,large,n);
    }
}

// function to sort the array
// Parent node is node that has atleast one children
void heapSort(int arr[],int n)
{
    // Index of last/right most parent node
    int last_non_leaf = n/2 - 1;

    // heapify the array beginning from right most parent node
    for(;last_non_leaf >= 0;last_non_leaf--)
    heapServe(arr,last_non_leaf,n);
    
    // start sorting from rightmost of the array
    for(int i=n-1;i >= 0;i--)
    {
        // Extract root (largest) element,swap with last array element
        swap(arr[0],arr[i]);
        // heapify the leftover array (obtained after extracting largest element)
        heapServe(arr,0,i);
    }
}

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

    heapSort(arr,n);

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

Натиҷаи

1 4 5 6 7 8 9

Барномаи Java барои Sort Heap

class heap
{
    // service function to heapify array
    public static void heapServe(int arr[],int i,int n)
    {
        int large = i;
        // index of left and right child
        int left = 2*i+1;
        int right = 2*i+2;

        // find largest amongst parent ,left and right children
        if(left < n && arr[left] > arr[large])
        large = left;
        if(right < n && arr[right] > arr[large])
        large = right;

        // swap if parent node is not largest
        // recursiveley heapify swapped nodes
        if(large != i)
        {
            int temp = arr[large];
            arr[large] = arr[i];
            arr[i] = temp;
            heapServe(arr,large,n);
        }
    }
    // function to sort the array
    // Parent node is node that has atleast one children
    public static void heapSort(int arr[],int n) 
    {
        // Index of last/right most parent node
        int last_non_leaf = n/2 - 1;
        
        // heapify the array beginning from right most parent node
        for(;last_non_leaf >= 0;last_non_leaf--)
        heapServe(arr,last_non_leaf,n);

        // start sorting from rightmost of the array
        for(int i=n-1;i >= 0;i--)
        {
            // Extract root (largest) element,swap with last array element
            int temp = arr[0];
            arr[0] = arr[i];
            arr[i] = temp;
            
            // heapify the leftover array (obtained after extracting largest element)
            heapServe(arr,0,i);
        }
    }

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

        heapSort(arr,n);

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

Натиҷаи

1 4 5 6 7 8 9

Таҳлили мураккабии HeapSort

  • Мураккабии heapification O (logn) аст, истихроҷи ҳар як элемент O (n) вақтро мегирад, мураккабии умумӣ T (n) = O (nlogn).
  • Беҳтарин ҳолат: T (n) = O (nlogn)
  • Бадтарин ҳолат: T (n) = O (nlogn)
  • Ҳолати миёна: T (n) = O (nlogn)
  • Фазои ёрирасон, A (n) = O (1)

Маълумоти иловагӣ дар бораи HeapSort

  • HeapSort алгоритми ҷобаҷогузории дохилӣ аст.
  • Hort Sort алгоритми устувор нест.
  • Quicksort ва Merge Sort аксар вақт нисбат ба HeapSort беҳтар кор мекунанд, зеро он аз ҳисоби зангҳои рекурсивӣ якбора вақти доимӣ дорад.

ишора

https://en.wikipedia.org/wiki/Heapsort

Мақолаи алоқаманд

Якҷоя кардани навъҳо беҳтар аз навъҳои зуд барои рӯйхати алоқаманд