આપેલ શ્રેણીની આસપાસ એરેનું ત્રણ માર્ગીકરણ


મુશ્કેલી સ્તર સરળ
વારંવાર પૂછવામાં આવે છે બેંકબજાર બ્લેકરોક કેપિટલ વન સિટાડેલ ફેબ મૂનફ્રોગ લેબ્સ સારાંશ Twilio યાહૂ
અરે

સમસ્યા નિવેદન

તમે એક આપવામાં આવે છે એરે 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

સમજૂતી

લોવલ્યુ 15 છે, જેમ કે ડાબી બાજુની સંખ્યાઓ નીચા વેલ્યુ કરતા ઓછી હશે.

શ્રેણી 15 અને 30 ની વચ્ચે છે, 23 તે સંખ્યા છે જે આ શ્રેણીની વચ્ચે છે

હાઇવalલ્યુ 30 છે, બધી સંખ્યાઓ ઉચ્ચ મૂલ્ય કરતા વધારે છે તે જમણી બાજુ હશે.

આપેલ શ્રેણીની આસપાસ એરેનું ત્રણ માર્ગીકરણ

અલ્ગોરિધમ

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 અને એરેના છેલ્લા ઇન્ડેક્સથી પ્રારંભ કરીએ છીએ. અદલાબદલ કરતી વખતે જ્યારે પણ નીચા મૂલ્ય કરતા ઓછું મૂલ્ય મળે છે, ત્યારે ઓપરેશન સ્ટાર્ટવVલ્યુ પર કરવામાં આવશે અને જ્યારે પણ ઉચ્ચ મૂલ્ય કરતા વધુ મૂલ્ય મળશે, ત્યારે ઓપરેશન અંતિમ વalલ્યુ પર કરવામાં આવશે. આપણે એરેને પસાર કરીશું અને તપાસ કરીશું કે વર્તમાન એરે એલિમેન્ટ આપેલ લોવેલ્યુ કરતા ઓછું છે કે નહીં જો એરેનું વર્તમાન વેલ્યુ અને એરે પ્રથમ પોઝિશન મૂલ્ય સ્વેપ કરીશું. આ મૂલ્ય આપણે પ્રારંભિક બિંદુનો ટ્ર trackક રાખીશું અને અન્ય મૂલ્ય એલિમેન્ટ્સને અદલાબદલ કરવા માટે અંતિમ ઇન્ડેક્સનો ટ્રેક રાખશે, જો તત્વો વર્તમાન એરે એલિમેન્ટના મૂલ્ય કરતા વધારે જોવા મળે તો બીજું સ્વેપ કરવામાં આવશે. પછી અંત આવે છે, અનુક્રમણિકા જેમાં તત્વ વર્તમાન તત્વ સાથે અદલાબદલ થાય છે. જો કોઈ પણ સ્થિતિ સંતોષવાનો અર્થ એ નથી કે સંખ્યા આપેલ શ્રેણીમાં છે, તો આપણે તેને બદલીશું નહીં. ટ્ર theવર્સલ પૂર્ણ થયા પછી, અમારી પાસે ઇચ્છિત એરે છે. આપણે ફક્ત એરે છાપવાની જરૂર છે.

કોડ

આપેલ શ્રેણીની આસપાસ એરેના ત્રણ માર્ગી પાર્ટીશનને હલ કરવા માટે સી ++ કોડ

#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

જટિલતા વિશ્લેષણ

સમય જટિલતા

ઓ (એન) જ્યાં “એન” એરેમાં તત્વોની સંખ્યા છે. કારણ કે આપણે એરે તત્વો પર સમય પસાર કર્યો છે સમય જટિલતા રેખીય છે.

અવકાશ જટિલતા

ઓ (1) કોઈ વધારાની જગ્યા જરૂરી નથી. એલ્ગોરિધમ જાતે જ જગ્યાએ અલ્ગોરિધમનો છે અને પ્રારંભિક આપેલ એરેને અપડેટ કરી રહ્યું છે. આમ જ્યારે કાર્યક્રમ રેખીય હોય ત્યારે અલ્ગોરિધમનો અવકાશ જટિલતા સતત રહે છે.