מיון באמצעות פונקציית חשיש טריוויאלית  


רמת קושי בינוני
נשאל לעתים קרובות קדנס הודו קאפ ג'מיני סט עובדות מאק UHG אופטום
מערך בליל מִיוּן

הבעיה "מיון באמצעות פונקציית חשיש טריוויאלית" קובעת כי ניתנת לך מספר שלם מערך. מערך יכול להכיל מספרים שליליים וחיוביים כאחד. הצהרת הבעיה מבקשת למיין את המערך באמצעות פונקציה Hash Trivial.

דוגמה  

מיון באמצעות פונקציית חשיש טריוויאלית

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. הגדל את ספירת שני המערכים ב- 1 עבור כל אלמנט בהתאם אם הוא גדול מ- 0 או פחות מ- 0 ושמור אותו בשני המערכים בהתאמה.
  4. הדפס את המערך שיש בו ספירת אלמנטים שלילית, כמספר הפעמים שהוא מתרחש. עשו את אותו הדבר עם האלמנט החיובי.
  5. יהיה לנו את מיון מערך.

הסבר

נותנים לנו מערך, זה יכול להכיל מספרים שלמים חיוביים ושליליים. המשימה שלנו היא למיין את המערך באמצעות הפונקציה Trivial Hash. כדי לפתור זאת נשתמש בגיבוב ונאתחל שני מערכים. מצא את האלמנט המקסימלי והמינימלי (האלמנט המינימלי עם הערך המוחלט). האחד מיועד לאלמנטים שליליים והשני נועד לאלמנטים החיוביים. הגודל של שני המערכים צריך להיות שווה לאלמנט הקלט המרבי ולאלמנטים השליליים של הקלט אך עם הערך המוחלט.

ראה גם
שיטה איטרטיבית למציאת גובה העץ הבינארי

נעבור את המערך הנתון, ונבדוק תנאי אם אלמנט מערך גדול מ- 0, נגדיל את הופעתו ב- 1 במערך אלמנטים חיובי ואם הוא קטן מ- 0, המשמעות היא שהמספר שלילי, אנחנו יגדיל את הופעתה ב- 1 במערך אלמנטים שלילי. לאחר המעבר, יש לנו את הספירה של כל אלמנט מערך נתון בשני המערכים שיצרנו.

כעת עלינו להדפיס את האלמנטים האלה בצורה ממוינת. אז ניקח תחילה את מערך האלמנטים השליליים, עלינו להתחיל מהאלמנט המינימלי אך עם הסימן השלילי והדפסה כמספר הפעמים בהתרחשות וירידת הערך עד שסיימנו להדפיס את כל הערכים השליליים.

כעת החל מ- 0, נדפיס את כל האלמנטים החיוביים של המערך, כמספר הפעמים שהוא מתרחש עד האלמנט המרבי במערך. אך עלינו לוודא שמצאנו את הערך הנכון כמקסימום ומינימלי במערך ולהדפיס ערך מערך אלמנטים שליליים עם הסימן השלילי או לאחר הכפלתו ב- -1. לאחר ההשלמה הדפסנו מערך ממוין.

קוד 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

קוד Java לביצוע מיון באמצעות פונקציית 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 (מקסימום + דקות), כאן מקסימום הוא האלמנט המקסימלי והמינימלי בקלט. מורכבות החלל זהה גם לזו של מורכבות הזמן, היא גם לא תלויה בגודל הקלט. זה תלוי בגודל האלמנטים.