តម្រៀបដោយប្រើមុខងារ hash មិនសំខាន់


កម្រិតលំបាក មធ្យម
សួរញឹកញាប់ Cadence ឥណ្ឌា Capgemini រោងចក្រ MAQ យូអេសជីអុបទិក
អារេ ហាស់ តម្រៀប

បញ្ហា“ ការតម្រៀបដោយប្រើមុខងារតូចតាច” បញ្ជាក់ថាអ្នកត្រូវបានផ្តល់ឱ្យ integer អារេ។ អារេអាចមានទាំងលេខអវិជ្ជមាននិងវិជ្ជមាន។ សេចក្តីថ្លែងការណ៍បញ្ហាស្នើឱ្យតម្រៀបអារេដោយប្រើ មុខងារហាសដែលមិនសំខាន់។

ឧទាហរណ៍

តម្រៀបដោយប្រើមុខងារ hash មិនសំខាន់

arr[] = {5,2,1,3,6}
{1, 2, 3, 5, 6}
arr[] = {-3, -1, 4, 3, -2, 1, 2, 0}
{-3, -2,-1, 0, 1, 2, 3, 4}

ការពន្យល់

ធាតុទាំងអស់ត្រូវបានតម្រៀបតាមលទ្ធផលទាំងពីរ។ ដូច្នេះលទ្ធផលគឺត្រឹមត្រូវ។

ក្បួនដោះស្រាយ

  1. ស្វែងយល់ពីធាតុអតិបរិមានិងអប្បបរមានៃអារេមួយ (ធាតុអប្បបរមាប៉ុន្តែជាមួយនឹងតម្លៃដាច់ខាត) ។
  2. បង្កើតអារេនៃធាតុអតិបរមាទំហំនិងធាតុអប្បបរមា។
  3. បង្កើនចំនួនអារេទាំងពីរដោយ ១ សំរាប់ធាតុនីមួយៗស្របតាមនោះប្រសិនបើវាធំជាង ០ រឺតិចជាង ០ ហើយទុកវានៅអារេទាំងពីររៀងៗខ្លួន។
  4. ព្រីនធ័រដែលមានចំនួនធាតុអវិជ្ជមានដូចជាមិនមានពេលវេលាដូចដែលវាកើតឡើងទេ។ ធ្វើដូចគ្នាជាមួយធាតុវិជ្ជមាន។
  5. យើងនឹងមាន តម្រៀប អារេ។

ការពន្យល់

យើងត្រូវបានផ្តល់ឱ្យ អារេវាអាចមានចំនួនគត់វិជ្ជមាននិងអវិជ្ជមាន។ ភារកិច្ចរបស់យើងគឺដើម្បីតម្រៀបអារេដោយប្រើមុខងារ Trivial Hash ។ ដើម្បីដោះស្រាយបញ្ហានេះយើងនឹងប្រើការធ្វើឱ្យមានសូរស័ព្ទនិងចាប់ផ្តើមអារេពីរ។ ស្វែងរកធាតុអតិបរិមានិងអប្បបរមា (ធាតុអប្បបរមាដែលមានតម្លៃដាច់ខាត) ។ មួយគឺសម្រាប់ធាតុអវិជ្ជមានហើយមួយទៀតគឺសម្រាប់ធាតុវិជ្ជមាន។ ទំហំនៃអារេទាំងពីរគួរតែស្មើនឹងធាតុអតិបរិមានៃធាតុបញ្ចូលនិងធាតុអវិជ្ជមាននៃធាតុបញ្ចូលប៉ុន្តែមានតម្លៃដាច់ខាត។

យើងនឹងឆ្លងកាត់អារេដែលបានផ្តល់ហើយពិនិត្យមើលលក្ខន្តិកៈប្រសិនបើធាតុអារេធំជាង ០ យើងនឹងបង្កើនការកើតឡើងរបស់វាដោយ ១ នៅក្នុងអារេនៃធាតុវិជ្ជមានហើយប្រសិនបើវាតិចជាង ០ វាមានន័យថាលេខគឺអវិជ្ជមានយើង នឹងបង្កើនការកើតឡើងរបស់វាដោយ ១ នៅក្នុងអារេធាតុអវិជ្ជមាន។ បន្ទាប់ពីការឆ្លងកាត់យើងមានចំនួនធាតុដែលបានផ្តល់ឱ្យនីមួយៗនៅក្នុងអារេទាំងពីរដែលយើងបានបង្កើត។

ឥឡូវយើងត្រូវបោះពុម្ពធាតុទាំងនោះតាមលំដាប់លំដោយ។ ដូច្នេះយើងនឹងយកអារេធាតុអវិជ្ជមានដំបូងយើងត្រូវចាប់ផ្តើមពីធាតុអប្បបរមាប៉ុន្តែមានសញ្ញាអវិជ្ជមានហើយព្រីនជាចំនួនដងនៅពេលវាកើតឡើងនិងបន្ថយតម្លៃរហូតដល់យើងបញ្ចប់ការបោះពុម្ពតម្លៃអវិជ្ជមានទាំងអស់។

ឥឡូវចាប់ផ្តើមពីលេខ ០ យើងនឹងបោះពុម្ពរាល់ធាតុវិជ្ជមាននៃអារេដូចជាមិនមានពេលវេលាដូចដែលវាកើតឡើងរហូតដល់ធាតុអតិបរមានៅក្នុងអារេ។ ប៉ុន្តែយើងត្រូវធ្វើឱ្យប្រាកដថាយើងបានរកឃើញតម្លៃត្រឹមត្រូវបំផុតនិងអប្បបរមានៅក្នុងអារេមួយហើយបោះពុម្ពតម្លៃអារេអវិជ្ជមានធាតុដែលមានសញ្ញាអវិជ្ជមានឬបន្ទាប់ពីគុណវាជាមួយ -0 ។ បន្ទាប់ពីបញ្ចប់យើងបានបោះពុម្ពអារេតម្រៀប។

កូដ C ++ ដើម្បីអនុវត្តការតម្រៀបដោយប្រើមុខងារ hash មិនសំខាន់

#include<iostream>
#include<unordered_map>
#include<algorithm>

using namespace std;

void sortUsingHash(int arr[], int n)
{
    int max = *std::max_element(arr, arr + n);
    int min = abs(*std::min_element(arr, arr + n));

    int positiveNum[max + 1] = { 0 };
    int negativeNum[min + 1] = { 0 };

    for (int i = 0; i < n; i++)
    {
        if (arr[i] >= 0)
            positiveNum[arr[i]] += 1;
        else
            negativeNum[abs(arr[i])] += 1;
    }
    for (int i = min; i > 0; i--)
    {
        if (negativeNum[i])
        {
            for (int j = 0; j < negativeNum[i]; j++)
            {
                cout << (-1) * i << " ";
            }
        }
    }
    for (int i = 0; i <= max; i++)
    {
        if (positiveNum[i])
        {
            for (int j = 0; j < positiveNum[i]; j++)
            {
                cout << i << " ";
            }
        }
    }
}
int main()
{
    int a[] = {7, 5, -4, -3, 2, 4, 1, -2, -1, 0, 6, 3 };

    int n = sizeof(a) / sizeof(a[0]);
    sortUsingHash(a, n);
    return 0;
}
-4 -3 -2 -1 0 1 2 3 4 5 6 7

កូដចាវ៉ាដើម្បីអនុវត្តការតម្រៀបដោយប្រើមុខងារ hash មិនសំខាន់

import java.util.Arrays;
class HashingSorting
{
    public static void sortUsingHash(int arr[], int n)
    {
        int max = Arrays.stream(arr).max().getAsInt();
        int min = Math.abs(Arrays.stream(arr).min().getAsInt());

        int positiveNum[] = new int[max + 1];
        int negativeNum[] = new int[min + 1];

        for (int i = 0; i < n; i++)
        {
            if (arr[i] >= 0)
                positiveNum[arr[i]] += 1;
            else
                negativeNum[Math.abs(arr[i])] += 1;
        }
        for (int i = min; i > 0; i--)
        {
            if (negativeNum[i] > 0)
            {
                for (int j = 0; j < negativeNum[i]; j++)
                {
                    System.out.print((-1)*i+" ");
                }
            }
        }
        for (int i = 0; i <= max; i++)
        {
            if (positiveNum[i] > 0)
            {
                for (int j = 0; j < positiveNum[i]; j++)
                {
                    System.out.print(i+" ");
                }
            }
        }
    }
    public static void main(String[] args)
    {
        int a[] = { 7, 5, -4, -3, 2, 4, 1, -2, -1, 0, 6, 3 };
        int n = a.length;
        sortUsingHash(a, n);
    }
}
-4 -3 -2 -1 0 1 2 3 4 5 6 7

ការវិភាគស្មុគស្មាញ

ស្មុគស្មាញពេលវេលា

O (អតិបរមា + នាទី), នៅទីនេះអតិបរមាគឺជាធាតុអតិបរមានិងអប្បបរមានៅក្នុងការបញ្ចូល។ ដូច្នេះភាពស្មុគស្មាញនៃពេលវេលាមិនអាស្រ័យលើទំហំនៃការបញ្ចូលទេប៉ុន្តែអាស្រ័យលើធាតុរបស់វា។

ភាពស្មុគស្មាញនៃលំហ

O (អតិបរមា + នាទី), នៅទីនេះអតិបរមាគឺជាធាតុអតិបរមានិងអប្បបរមានៅក្នុងការបញ្ចូល។ ភាពស្មុគស្មាញនៃលំហក៏ដូចគ្នានឹងភាពស្មុគស្មាញនៃពេលវេលាដែរវាក៏មិនអាស្រ័យលើទំហំនៃធាតុបញ្ចូលដែរ។ វាអាស្រ័យលើទំហំនៃធាតុ។