ترتيب جي ترتيب کي ٻيهر ترتيب ڏيو - نن smallestو ، وڏو ، ٻيو نن smallestو ، ٻيو وڏو


تڪليف جي سطح وچولو
بار بار پڇڻ ۾ Amazon قلعي Expedia اي صحت Qualcomm قوتون Twilio ياترا
ڪيريو ترتيب ڏيڻ

مسئلي جو بيان

فرض ڪيو ته توهان وٽ هڪ انٽيگرري آرٽ آهي. مسئلو ”قطار کي ٻيهر ترتيب ڏيو- نن smallestو ، وڏو ، 2 جو نن ،و ، 2 جو وڏو ، ..“ صف کي وري ترتيب سان ترتيب ڏيڻ جو پڇي ٿو ته نن theو نمبر پهريان اچي ٿو ۽ پوءِ وڏو نمبر ، پوءِ ٻيو نن smallestو ۽ پوءِ ٻيو وغيره وغيره.

مثال

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

وضاحت: نن Theڙو نمبر 1 ۽ سڀ کان وڏو آهي 9 ، 2nd 2 ۽ 2 جيترا نناnd 8 ، 3 وانگر وڏوrd نن smallestو آهي 3 ۽ 3rd سڀ کان وڏو 7 آهي ، 4 نن smallestو نن 3و آهي 4 ۽ چوٿون تمام وڏو 7 آهي. اھڙي طرح جيترو نتيجو پيداوار ۾ ترتيب ڏنو ويو آھي.

الگورٿم لاءِ وري ترتيب سان ترتيب ڏيڻ لاءِ - نن smallestو ، وڏو ، ٻيو نن smallestو ، ٻيو وڏو

1. Sort the given array.
2. We have to use a temporary array, so declare one.
3. Set index to 0.
4. Traverse the array from left and from right, with i = 0 and j = n – 1 up the half of the array length.
    1. Store the value of arr[j] to the temporary[index] and increase the value of the index by 1.
    2. Store the value of arr[j] to the temporary[index] and increase the value of the index by 1.
5. Update the original array by storing the value of a temporary array to the original array.
6. At last, the original array should be printed.

وضاحت

ڏني وئي ترتيب ڏنل جيتريون. اسان پڇيو آهي ته صف کي وري ترتيب سان ترتيب ڏيو ته نن andن توڙي سڀني کان وڏو صف پهرين ۽ ٻئين نمبر تي اچڻ گهرجي. پوءِ 2nd نن smallestڙو ۽ 2 ايم ڊي وڏي تعداد ۾ ايندڙ نمبر تي اچڻ گهرجي ، پوءِ ان کي جاري رکو ، 3rd ننو ۽ 3rd نمبر ۾ سڀني کان وڏو اچڻ لازمي آھي انهي تسلسل ۾ ، اسان کي ترتيب سان ترتيب ڏيڻو آهي. اسان انهي ضرورت کي پورو ڪرڻ لاءِ اضافي صف استعمال ڪري سگهنداسين. ڏنل سٽ کي ترتيب ڏيو ته جيئن هر ڪو گهمڻ واري انداز ۾ اچي.

صف کي ترتيب ڏيڻ سان ، اسان ترتيب ڏنل نن halfي نمبر ۾ هڪ اڌ ۾ ۽ ٻيو وڏو نمبر صف اندر اندر. فرض ڪيو ته اسان وٽ 1 کان 10 کان عدد ، بي ترتيب سان ذخيري ۾ رکيل آھي ، ۽ جيڪڏھن انھن کي ترتيب ڏيو ، ته 1 کان 5 تائين پھريون اڌ ۾ ۽ 6 کان 10 ٻئي اڌ ۾ ھوندو.

ساڳي طرح هتي ، اسان هاڻي کاٻي پاسي کان سفر ڪري سگھون ٿا ۽ قدرن کي پنهنجي ٺاهيل سر ۾ محفوظ ڪري سگهون ٿا. جڏهن کان اسين کاٻي پاسي کان شروع ڪريون ٿا ، اتي ئي تمام نن elementڙو عنصر هوندو تنهن ڪري اسين اهو عنصر عارضي صف ۾ داخل ڪري سگهون ٿا. تنهنڪري پهرين پوزيشن ۾ ، اتي رڳو نن smallestڙو نن elementڙو عنصر آهي. ھاڻي سا fromي طرف ھليو ، ڇاڪاڻ ته صف کي اھم ڪيو ويو آھي تنھنڪري اھڙو وڏو عنصر ھجڻ گھرجي تنھنڪري ھاڻي اسان اھو عنصر عارضي صف ۾ وجھو. اسان جو پهريون نن smallestڙو ۽ وڏو مڪمل ٿي چڪو آهي ، هاڻي اڳتي وڌندو جئين ته اسان اڳي ئي ڪيو آهي اسان کي بائیں اگني عنصر کان منتقل ڪرڻ گهرجي ۽ هڪ عارضي صف تي رکڻ گهرجي ۽ پوءِ سا rightي طرف کان ٻيو وڏو عنصر چونڊيندا آهيون ۽ ان کي اسٽور سان ترتيب ڏيو ، هن طريقي سان ، اسان نتيجو حاصل ڪري سگهون ٿا جيڪو اسان چاهيون ٿا. هاڻي بس انهي ترتيب کي پرنٽ ڪيو.

ترتيب جي ترتيب کي ٻيهر ترتيب ڏيو - نن smallestو ، وڏو ، ٻيو نن smallestو ، ٻيو وڏو

ڪوڊ

ترتيب سان ترتيب ڏيڻ لاءِ C ++ ڪوڊ نن --و ، وڏو ، ٻيو نن smallestو ، ٻيو وڏو

#include<iostream>
#include<algorithm>

using namespace std;

void rearrangeInOrderSL(int arr[], int n)
{
    sort(arr, arr + n);

    int temporaryArray[n];

    int Index = 0;

    for (int i = 0, j = n-1; i <= n / 2 ||j > n / 2; i++, j--)
    {
        temporaryArray[Index] = arr[i];
        Index++;
        temporaryArray[Index] = arr[j];
        Index++;
    }
    for (int i = 0; i < n; i++)
        arr[i] = temporaryArray[i];

    for (int i = 0; i < n; i++)
        cout << arr[i] << " ";
}
int main()
{
    int arr[] = {1,4,6,2,3,8,9,7};
    int n = sizeof(arr) / sizeof(arr[0]);

    rearrangeInOrderSL(arr, n);

    return 0;
}
1 9 2 8 3 7 4 6

جاوا ڪوڊ ترتيب سان ترتيب ڏيڻ لاءِ - نن smallestو ، وڏو ، ٻيو نن 2ndو ، ٻيو وڏو

import java.util.Arrays;
class rearrangeArraySL
{
    public static void rearrangeInOrderSL(int arr[], int n)
    {
        Arrays.sort(arr);

        int[] temporaryArray = new int[n];

        int Index = 0;

        for (int i = 0, j = n-1; i <= n / 2 || j > n / 2; i++, j--)
        {
            if(Index < n)
            {
                temporaryArray[Index] = arr[i];
                Index++;
            }

            if(Index < n)
            {
                temporaryArray[Index] = arr[j];
                Index++;
            }
        }
        for (int i = 0; i < n; i++)
            arr[i] = temporaryArray[i];
    }
    public static void main(String args[])
    {
        int arr[] = {1,4,6,2,3,8,9,7};
        int n = arr.length;
        rearrangeInOrderSL(arr, n);

        for (int i = 0; i < n; i++)
            System.out.print(arr[i]+" ");
    }
}
1 9 2 8 3 7 4 6

پيچيدگي تجزيي

وقت جي پيچيدگي

اي (اين لاگ اين) جتي "ن" صف ۾ موجود عنصرن جو تعداد آهي. اسان ان پني کي ترتيب ڏني آهي جنهن جي ڪري اسان وٽ هن وقت پيچيدگي آهي.

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

اي (اين) جتي "ن" صف ۾ موجود عنصرن جو تعداد آهي. ضم ڪريو ترتيب پاڻ اي (اين) اسپيس ورتي آهي.