دوبارہ ترتیب دیں اس طرح کہ ارر [i]> = ارر [ج] اگر میں مساوی بھی ہو اور میں بھی ہوں [i] <= ارر [ج] اگر میں عجیب ہوں اور جے <i  


مشکل سطح درمیانہ
اکثر پوچھا جاتا ہے ایکسینچر ایڈوب ایمیزون حقیقت Zoho
لڑی

فرض کریں کہ آپ کے پاس کوئی عدد عدد ہے صف. مسئلے کا بیان اس طرح صف کو دوبارہ ترتیب دینے کے لئے کہتا ہے کہ کسی صف میں یکساں پوزیشن پر موجود عناصر اس سے پہلے کے تمام عناصر سے زیادہ ہونا چاہئے اور عجیب پوزیشن پر موجود عناصر اس سے پہلے کے عناصر سے کم ہونا چاہئے۔

مثال کے طور پر  

ان پٹ

ارر [] = {1، 4، 6، 2، 4، 8، 9}

آؤٹ پٹ

4 6 4 8 2 9 1

وضاحت

مساوی عہدوں پر موجود تمام عناصر اس سے پہلے کے تمام عناصر سے زیادہ ہوتے ہیں اور عجیب پوزیشنوں پر موجود عناصر پچھلے عناصر سے کم ہوتے ہیں۔

الگورتھم  

  1. یہاں تک کہ مقام کو N / 2 پر سیٹ کریں۔
  2. oddPosition کو n - evenPosition پر سیٹ کریں۔
  3. ایک صف (عارضی) بنائیں۔
  4. دیئے ہوئے صفوں کے تمام عناصر کو اس عارضی صف میں محفوظ کریں۔
  5. عارضی سرنی کو ترتیب دیں۔
  6. جیڈ کو اوز پوزیشن -1 کے برابر رکھیں۔
  7. دیئے گئے صف کی عارضی پوزیشن (اشاریہ سازی پر مبنی) پر عارضی طور پر اصلی سرنی [j] کاپی کریں اور j کی قدر میں 1 کی کمی کریں۔
  8. جیڈ کو اوڈ پوزیشن پر سیٹ کریں۔
  9. دیئے گئے صف کی عجیب پوزیشن (اشاریہ سازی پر مبنی) پر عارضی کو اصل سرنی [j] میں کاپی کریں اور j کی قدر میں 1 اضافہ کریں۔
  10. اصل صف کو چھاپیں کیونکہ تازہ کاری اصل صف میں کی گئی ہے۔

وضاحت  

انٹریجر کی ایک صف کو دیکھتے ہوئے ، ہمارا کام سرے کو اس انداز میں دوبارہ ترتیب دینا ہے کہ یہاں تک کہ عہدوں کی تعداد میں موجود عناصر اس سے پہلے کے سبھی عناصر سے زیادہ ہوں۔ اور عجیب تعداد میں موجود عوامل کو اس سے پہلے موجود تمام تعداد سے کم ہونا چاہئے۔ ہم مثال میں دیکھ سکتے ہیں کیوں کہ عہدوں پر موجود عناصر اس سے پہلے کی تمام تعداد سے زیادہ ہیں۔ یہاں ہم اسے انڈیکس پر مبنی نمبر کی حیثیت سے نہیں لے رہے ہیں۔ 0 پوزیشنوں پر عنصر کو 1 پوزیشن سمجھنا چاہئے جو عجیب ہے۔ 1st کسی صف کی پوزیشن 2 پوزیشن ہوتی ہے جو کہ یکساں ہوتی ہے ، یہاں ہم اپنے نتیجے میں سرنی پر مبنی انڈیکسنگ پر غور نہیں کررہے ہیں ، ہم 1 سے عجیب عدد کے طور پر شروع کرتے ہیں۔

یہ بھی دیکھتے ہیں
زیادہ سے زیادہ سبری

اصل صف کی ایک کاپی عارضی سرنی میں بنائیں ، گنیں کہ دیئے جانے والے صف میں کتنے بھی عجیب و غریب پوزیشن ہوسکتے ہیں۔ پھر ، ہم بڑھتے ہوئے ترتیب میں صف کو ترتیب دینے جارہے ہیں۔ عارضی پوزیشن (عارضی پر مبنی اشاریہ سازی) پر سرنی کے عناصر کو عارضی سرنی سے عجیب پوزیشن - 1 سے 0 کی کم ہوتی ہوئی اقدار کے طور پر تازہ کاری کریں۔

عارضی سرنی کے نصف حصے سے تمام عناصر کو اصل صف کی عجیب پوزیشن پر محفوظ کیا جائے گا۔ اسی طرح ، ہم عارضی صف کے دوسرے نصف حصے کی باقی اقدار کو اصل صف کے برابر مقام پر اسٹور کریں گے ، اس انداز میں ، ہم سرنی کو دوبارہ ترتیب دے سکتے ہیں تاکہ حتی کہ عناصر زیادہ سے زیادہ پوزیشن پر اور عجیب و غریب مقام پر عجیب عناصر کی پوزیشنیں اس سے پہلے بالترتیب اس سے پہلے کے سبھی عناصر سے چھوٹی ہوں گی۔

دوبارہ ترتیب دیں اس طرح کہ ارر [i]> = ارر [ج] اگر میں مساوی بھی ہو اور میں بھی ہوں [i] <= ارر [ج] اگر میں عجیب ہوں اور جے <i

عمل  

C ++ پروگرام

#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

پیچیدگی کا تجزیہ  

وقت کی پیچیدگی

O (n لاگ این) کہاں "این" صف میں عناصر کی تعداد ہے۔

یہ بھی دیکھتے ہیں
وہ تمام انوکھی ٹرپلٹس جو ایک دیئے گئے قدر کے برابر ہیں

خلائی پیچیدگی

اے (ن)  کہاں "این"  صف میں عناصر کی تعداد ہے۔