ഒരു നിശ്ചിത പരിധിക്കുള്ളിൽ ഒരു അറേയുടെ ത്രീ വേ പാർട്ടീഷനിംഗ്


വൈഷമ്യ നില എളുപ്പമായ
പതിവായി ചോദിക്കുന്നു ബാങ്ക്ബസാർ കറുത്ത പാറ ക്യാപിറ്റൽ വൺ കോട്ട ഫാഷ് മൂൺഫ്രോഗ് ലാബുകൾ സമന്വയിപ്പിക്കുക ട്വിలియో യാഹൂ
അറേ

പ്രശ്നം പ്രസ്താവന

നിങ്ങൾക്ക് ഒരു നൽകിയിട്ടുണ്ട് ശ്രേണി of പൂർണ്ണസംഖ്യകൾ ഒപ്പം താഴ്ന്ന മൂല്യത്തിന്റെയും ഉയർന്ന മൂല്യത്തിന്റെയും ശ്രേണി. “ഒരു ശ്രേണിക്ക് ചുറ്റുമുള്ള ഒരു അറേയുടെ ത്രീ വേ പാർട്ടീഷനിംഗ്” എന്ന പ്രശ്നം അറേയെ വിഭജിക്കാൻ ആവശ്യപ്പെടുന്നു, അതായത് അറേയെ മൂന്ന് ഭാഗങ്ങളായി വിഭജിക്കും. അറേകളുടെ പാർട്ടീഷനുകൾ ഇതായിരിക്കും:

  1. ആദ്യ പാർട്ടീഷന്റെ ഘടകങ്ങൾ താഴ്ന്ന മൂല്യത്തേക്കാൾ കുറവായിരിക്കും,
  2. തന്നിരിക്കുന്ന പരിധിക്കുള്ളിൽ ഘടകങ്ങൾ ഉൾക്കൊള്ളുന്ന അടുത്ത പാർട്ടീഷൻ ഈ പാർട്ടീഷനിലും
  3. ഉയർന്ന മൂല്യത്തേക്കാൾ വലിയ അക്കങ്ങൾ അറേയുടെ മൂന്നാം പാർട്ടീഷനായിരിക്കും.

ഉദാഹരണം

arr[]={2,5,87,56,12,4,9,23,76,1,45}

lowValue = 15

highValue = 30
2 5 1 12 4 9 23 76 56 45 87

വിശദീകരണം

lowValue 15 ആണ്, അതായത് ഇടതുവശത്തുള്ള സംഖ്യകൾ താഴ്ന്ന മൂല്യത്തേക്കാൾ കുറവായിരിക്കും.

ശ്രേണി 15 നും 30 നും ഇടയിലാണ്, 23 ഈ ശ്രേണിക്കിടയിലുള്ള സംഖ്യയാണ്

highValue 30 ആണ്, highValue നേക്കാൾ വലിയ എല്ലാ അക്കങ്ങളും വലതുവശത്തായിരിക്കും.

ഒരു നിശ്ചിത പരിധിക്കുള്ളിൽ ഒരു അറേയുടെ ത്രീ വേ പാർട്ടീഷനിംഗ്

അൽഗോരിതം

1. Set the startingValue to 0 and endingValue to n-1.
2. Traverse the array.
    1. Check if the current array element is less than the value of lowValue if true then swap the arr[i] and arr[startingValue] and increase both startingValues and i by 1.
    2. Else check if the current array is greater than the highValue, swap the arr[i] and arr[endingValue] and increase the value of i and decrease the value of endingValue by 1.
    3. Else increase the value of i by 1.
3. Print the array.

വിശദീകരണം

ഞങ്ങൾ‌ ഒരു ഇൻ‌റിജർ‌ അറേയും കുറഞ്ഞ മൂല്യവും ഉയർന്ന മൂല്യവും നൽകി. നമ്മൾ അറേ ക്രമീകരിക്കണം അല്ലെങ്കിൽ അറേ വിഭജിക്കണം. കുറഞ്ഞ മൂല്യത്തേക്കാൾ കുറവുള്ള അറേയുടെ സാധ്യമായ എല്ലാ സംഖ്യകളും അറേയുടെ ഇടതുവശത്തായിരിക്കും. അറേയുടെ ശ്രേണിയുടെ ഇടയിലുള്ള അറേയുടെ എണ്ണം അറേയിൽ അടുത്തതായിരിക്കും. അടുത്ത മൂല്യങ്ങൾ ഉയർന്ന മൂല്യത്തേക്കാൾ വലുതായ സംഖ്യകളായിരിക്കും അവസാനത്തേത്.

0 മുതൽ ഞങ്ങൾ അറേയിലൂടെ സഞ്ചരിക്കുംth അവസാന സൂചികയിലേക്കുള്ള സൂചിക. എന്നാൽ അതിനുമുമ്പ്, ഞങ്ങൾ ചില വേരിയബിളുകൾ പ്രഖ്യാപിക്കുകയും അത് യഥാക്രമം 0 ഉം അറേയുടെ അവസാന സൂചികയും ഉപയോഗിച്ച് ആരംഭിക്കുകയും ചെയ്തു. കുറഞ്ഞ മൂല്യത്തേക്കാൾ കുറഞ്ഞ മൂല്യം കണ്ടെത്തുമ്പോഴെല്ലാം കൈമാറ്റം ചെയ്യുമ്പോൾ, ആരംഭ മൂല്യത്തിൽ പ്രവർത്തനം നടത്തുകയും ഉയർന്ന മൂല്യത്തേക്കാൾ വലിയ മൂല്യം കണ്ടെത്തുമ്പോഴെല്ലാം പ്രവർത്തനം അവസാനിക്കുന്ന മൂല്യത്തിൽ നടത്തുകയും ചെയ്യും. ഞങ്ങൾ അറേയിലൂടെ സഞ്ചരിച്ച് നിലവിലെ അറേ ഘടകം തന്നിരിക്കുന്ന കുറഞ്ഞ മൂല്യത്തേക്കാൾ കുറവാണോ എന്ന് പരിശോധിച്ച് ശരിയാണെങ്കിൽ അറേയുടെ നിലവിലെ മൂല്യവും അറേയുടെ ആദ്യ സ്ഥാന മൂല്യവും സ്വാപ്പ് ചെയ്യുക. ഈ മൂല്യം ഞങ്ങൾ ആരംഭ പോയിന്റിന്റെ ട്രാക്ക് സൂക്ഷിക്കുകയും മറ്റ് മൂല്യങ്ങൾ ഘടകങ്ങൾ കൈമാറുന്നതിനുള്ള അവസാനിക്കുന്ന സൂചികകളുടെ ട്രാക്ക് സൂക്ഷിക്കുകയും ചെയ്യും, നിലവിലെ അറേ എലമെന്റിന്റെ മൂല്യത്തേക്കാൾ വലിയ ഘടകം കണ്ടെത്തിയാൽ മറ്റൊരു സ്വാപ്പ് ചെയ്യും. അപ്പോൾ അവസാനിക്കുന്ന മൂല്യം വരുന്നു, നിലവിലെ മൂലകത്തിനൊപ്പം മൂലകം സ്വാപ്പ് ചെയ്യുന്ന സൂചിക. ഒരു നിബന്ധനയും തൃപ്തികരമല്ലെങ്കിൽ, നൽകിയ പരിധിക്കുള്ളിൽ നമ്പർ സ്ഥിതിചെയ്യുന്നുവെങ്കിൽ ഞങ്ങൾ അത് മാറ്റില്ല. ട്രാവെർസൽ പൂർത്തിയായ ശേഷം, ഞങ്ങൾക്ക് ആവശ്യമുള്ള അറേ ഉണ്ട്. ഞങ്ങൾ അറേ പ്രിന്റുചെയ്യേണ്ടതുണ്ട്.

കോഡ്

പരിഹരിക്കാനുള്ള സി ++ കോഡ് ഒരു നിശ്ചിത പരിധിക്കുള്ളിൽ ഒരു അറേയുടെ ത്രീ വേ പാർട്ടീഷനിംഗ്

#include<iostream>
using namespace std;

void getPartition(int arr[], int n, int lowValue, int highValue)
{
    int startingValue = 0, endingValue = n-1;

    for (int i=0; i<= endingValue;)
    {
        if (arr[i] < lowValue)
            swap(arr[i++], arr[startingValue++]);

        else if (arr[i] > highValue)
            swap(arr[i], arr[endingValue--]);

        else
            i++;
    }
}

int main()
{
    int arr[] = {2,5,87,56,12,4,9,23,76,1,45};
    int n = sizeof(arr)/sizeof(arr[0]);

    getPartition(arr, n, 15, 30);

    for (int i=0; i<n; i++)
        cout << arr[i] << " ";
}
2 5 1 12 4 9 23 76 56 45 87

പരിഹരിക്കാനുള്ള ജാവ കോഡ് ഒരു നിശ്ചിത പരിധിക്കുള്ളിൽ ഒരു അറേയുടെ ത്രീ വേ പാർട്ടീഷനിംഗ്

class ThreeWayPartition
{
    public static void getPartition(int[] arr, int lowValue, int highValue)
    {
        int n = arr.length;

        int startingValue = 0, endingValue = n-1;

        for(int i = 0; i <= endingValue;)
        {
            if(arr[i] < lowValue)
            {

                int temp = arr[startingValue];
                arr[startingValue] = arr[i];
                arr[i] = temp;
                startingValue++;
                i++;
            }
            else if(arr[i] > highValue)
            {

                int temp = arr[endingValue];
                arr[endingValue] = arr[i];
                arr[i] = temp;
                endingValue --;
            }
            else
                i++;
        }
    }
    public static void main (String[] args)
    {
        int arr[] = {2,5,87,56,12,4,9,23,76,1,45};

        getPartition(arr, 15, 30 );

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

        }
    }
}
2 5 1 12 4 9 23 76 56 45 87

സങ്കീർണ്ണത വിശകലനം

സമയ സങ്കീർണ്ണത

O (n) എവിടെ “N” അറേയിലെ ഘടകങ്ങളുടെ എണ്ണം. ഞങ്ങൾ അറേ ഘടകങ്ങളിലൂടെ സഞ്ചരിച്ചതിനാൽ സമയ സങ്കീർണ്ണത രേഖീയമാണ്.

ബഹിരാകാശ സങ്കീർണ്ണത

O (1) അധിക ഇടം ആവശ്യമില്ലാത്തതിനാൽ. അൽ‌ഗോരിതം തന്നെ സ്ഥലത്തുള്ള അൽ‌ഗോരിതം ആണ്, മാത്രമല്ല തുടക്കത്തിൽ‌ നൽ‌കിയ അറേ അപ്‌ഡേറ്റുചെയ്യുകയും ചെയ്യുന്നു. പ്രോഗ്രാം ലീനിയർ ആയിരിക്കുമ്പോൾ അൽഗോരിത്തിന്റെ സ്പേസ് സങ്കീർണ്ണത സ്ഥിരമായിരിക്കും.