අරාව නැවත සකසන්න. Ar [i]> = arr [j] මම ඉරට්ටේ නම් සහ arr [i] <= arr [j] මම අමුතු නම් සහ j <i


දුෂ්කරතා මට්ටම මධ්යම
නිතර අසනු ලැබේ ඇක්සෙන්චර් ඇෙබෝ ඇමේසන් ෆැක්ට්සෙට් Zoho
අරා

ඔබට පූර්ණ සංඛ්‍යාවක් ඇතැයි සිතමු අරාව. ගැටළු ප්‍රකාශය මඟින් අරාව නැවත සකස් කිරීමට ඉල්ලා සිටින්නේ අරාවෙහි ඉරට්ටේ පිහිටුමේ ඇති මූලද්‍රව්‍ය ඊට පෙර ඇති සියලුම මූලද්‍රව්‍යයන්ට වඩා විශාල විය යුතු අතර අමුතු ස්ථානවල ඇති මූලද්‍රව්‍ය ඊට පෙර ඇති මූලද්‍රව්‍යයන්ට වඩා අඩු විය යුතුය.

උදාහරණයක්

ආදාන

arr [] = {1, 4, 6, 2, 4, 8, 9}

ප්රතිදාන

4 6 4 8 2 9 1

පැහැදිලි කිරීම

ඉරට්ටේ ඇති සියලුම මූලද්‍රව්‍ය එයට පෙර ඇති සියලුම මූලද්‍රව්‍යයන්ට වඩා විශාල වන අතර අමුතු ස්ථානවල ඇති මූලද්‍රව්‍ය පෙර පැවති මූලද්‍රව්‍යයන්ට වඩා අඩුය.

ඇල්ගොරිතම

  1. ඉරට්ටේ පිහිටීම n / 2 ලෙස සකසන්න.
  2. OdPosition n - evenPosition ලෙස සකසන්න.
  3. අරාවක් සාදන්න (තාවකාලික).
  4. දී ඇති අරාවේ සියලුම අංග මෙම තාවකාලික අරාව තුළ ගබඩා කරන්න.
  5. තාවකාලික අරාව වර්ග කරන්න.
  6. J එක odPosition -1 ට සමාන කරන්න.
  7. දී ඇති අරාවෙහි ඒකාකාර ස්ථානයේ (සුචිගත කිරීම පදනම් කරගත්) තාවකාලික සිට මුල් අරාව [j] පිටපත් කර j හි අගය 1 කින් අඩු කරන්න.
  8. J අමුතු ස්ථානයට සකසන්න.
  9. ලබා දී ඇති අරාවේ අමුතු ස්ථානයේ (සුචිගත කිරීම පදනම් කරගත්) තාවකාලික මුල් අරාව [j] වෙත පිටපත් කර j හි අගය 1 කින් වැඩි කරන්න.
  10. යාවත්කාලීන කිරීම මුල් අරාව තුළ සිදු කර ඇති බැවින් මුල් අරාව මුද්‍රණය කරන්න.

පැහැදිලි කිරීම

නිඛිල සංඛ්‍යාවක් ලබා දී ඇති විට, අපගේ කර්තව්‍යය වන්නේ අරාව ප්‍රතිසංවිධානය කිරීම, ඊටත් වඩා ස්ථාන ගණනක මූලද්‍රව්‍ය ඊට පෙර ඇති සියලුම මූලද්‍රව්‍යයන්ට වඩා විශාල විය යුතුය. අමුතු ස්ථාන ගණනක මූලද්‍රව්‍ය එයට පෙර ඇති සියලුම සංඛ්‍යා වලට වඩා අඩු විය යුතුය. ඉරට්ටේ ඇති මූලද්‍රව්‍ය ඊට පෙර ඇති සියලුම සංඛ්‍යා වලට වඩා වැඩි බැවින් අපට උදාහරණයෙන් දැකිය හැකිය. මෙන්න අපි එය දර්ශක පාදක අංකයක් ලෙස නොසලකමු. ස්ථාන 0 ක මූලද්‍රව්‍යය අමුතු 1 ස්ථානයක් ලෙස සැලකිය යුතුය. 1st අරාවෙහි පිහිටීම 2 පිහිටුම වන අතර, මෙහි දී අපි අපේ ප්‍රති result ලය තුළ අරාව මත පදනම් වූ සුචිගත කිරීමක් සලකා බලන්නේ නැත, අපි 1 සිට අමුතු සංඛ්‍යා දක්වා ආරම්භ කරමු.

මුල් අරාවේ පිටපතක් තාවකාලික අරාව තුළට සාදන්න, දී ඇති අරාවෙහි ඉරට්ටේ හා අමුතු ස්ථාන කීයක් තිබිය හැකිදැයි ගණන් කරන්න. ඉන්පසුව, අපි වැඩි වන අනුපිළිවෙලින් අරාව වර්ග කිරීමට යන්නෙමු. දැන් අරාවෙහි මූලද්‍රව්‍ය අමුතු ස්ථානයේ (අරාව නොවන පාදක සුචිගත කිරීම) යාවත්කාලීන කරන්න, තාවකාලික අරාවෙහි සිට ඔඩිපොසිෂන් - 1 සිට 0 දක්වා අගයන් අඩු වේ.

තාවකාලික අරාවෙහි අඩකින් ඇති සියලුම මූලද්‍රව්‍ය මුල් අරාවේ අමුතු ස්ථානයේ ගබඩා වේ. ඒ හා සමානව, අපි තාවකාලික අරාවෙහි දෙවන භාගයේ ඉතිරි අගයන් මුල් අරාවෙහි ඒකාකාර ස්ථානයක ගබඩා කරනු ඇත, මේ ආකාරයෙන්, අපට අරාව නැවත සකස් කළ හැකි අතර එමඟින් ඊටත් වඩා විශාල ස්ථානවල මූලද්‍රව්‍ය අමුතු ලෙස අමුතු මූලද්‍රව්‍යවල පිහිටීම පිළිවෙලින් ඊට පෙර ඇති සියලුම මූලද්‍රව්‍යයන්ට වඩා කුඩා වේ.

අරාව නැවත සකසන්න. Ar [i]> = arr [j] මම ඉරට්ටේ නම් සහ arr [i] <= arr [j] මම අමුතු නම් සහ j <i

ක්රියාත්මක කිරීම

සී ++ වැඩසටහන

#include<iostream>
#include<algorithm>

using namespace std;

void rearrangeArrayEvenOdd(int arr[], int n)
{
    int evenPosition = n / 2;

    int oddPosition = n - evenPosition;

    int temporaryArray[n];

    for (int i = 0; i < n; i++)
        temporaryArray[i] = arr[i];

    sort(temporaryArray, temporaryArray + n);

    int j = oddPosition - 1;

    for (int i = 0; i < n; i += 2)
    {
        arr[i] = temporaryArray[j];
        j--;
    }

    j = oddPosition;

    for (int i = 1; i < n; i += 2)
    {
        arr[i] = temporaryArray[j];
        j++;
    }
}
void printArray(int arr[], int n)
{
    for (int i = 0; i < n; i++)
        cout << arr[i] << " ";
}
int main()
{
    int arr[] = { 1,4,6,2,4,8,9};
    int n = sizeof(arr) / sizeof(arr[0]);
    rearrangeArrayEvenOdd(arr, n);
    printArray(arr,n);
    return 0;
}
4 6 4 8 2 9 1

ජාවා වැඩසටහන

import java.util.*;

class rearrangeArray
{
    public static void rearrangeArrayEvenOdd (int arr[], int n)
    {
        int evenPosition = n / 2;

        int oddPosition = n - evenPosition;

        int[] temporaryArray = new int [n];

        for (int i = 0; i < n; i++)
            temporaryArray[i] = arr[i];

        Arrays.sort(temporaryArray);
        int j = oddPosition - 1;

        for (int i = 0; i < n; i += 2)
        {
            arr[i] = temporaryArray[j];
            j--;
        }

        j = oddPosition;

        for (int i = 1; i < n; i += 2)
        {
            arr[i] = temporaryArray[j];
            j++;
        }
    }
    public static void printArray(int arr[], int n)
    {

        for (int i = 0; i < n; i++)
            System.out.print(arr[i] + " ");
    }
    public static void main(String argc[])
    {
        int[] arr = { 1,4,6,2,4,8,9};
        int size =arr.length;
        rearrangeArrayEvenOdd (arr, size);
        printArray(arr, size);

    }
}
4 6 4 8 2 9 1

සංකීර්ණ විශ්ලේෂණය

කාල සංකීර්ණත්වය

ඕ (n ලොග් එන්) එහිදී “N” යනු අරාවෙහි ඇති මූලද්‍රව්‍ය ගණන වේ.

අභ්‍යවකාශ සංකීර්ණතාව

සාමාන්ය (n)  එහිදී “N”  යනු අරාවෙහි ඇති මූලද්‍රව්‍ය ගණන වේ.