நான் சமமாக இருந்தால் arr [i]> = arr [j] வரிசையை மறுசீரமைக்கவும், நான் ஒற்றைப்படை மற்றும் j <i என்றால் arr [i] <= arr [j]


சிரமம் நிலை நடுத்தர
அடிக்கடி கேட்கப்படுகிறது அக்சன்சர் அடோப் அமேசான் உண்மை ஸோகோ
அணி

உங்களிடம் ஒரு முழு எண் இருப்பதாக வைத்துக்கொள்வோம் வரிசை. சிக்கல் அறிக்கையானது வரிசையை மறுசீரமைக்கும்படி கேட்கிறது, இது ஒரு வரிசையில் சம நிலையில் இருக்கும் கூறுகள் அதற்கு முன் உள்ள அனைத்து உறுப்புகளையும் விட அதிகமாக இருக்க வேண்டும் மற்றும் ஒற்றைப்படை நிலைகளில் உள்ள கூறுகள் அதற்கு முன் உள்ள உறுப்புகளை விட குறைவாக இருக்க வேண்டும்.

உதாரணமாக

உள்ளீடு

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

வெளியீடு

4 6 4 8 2 9 1

விளக்கம்

சம நிலைகளில் உள்ள அனைத்து கூறுகளும் அதற்கு முன் உள்ள அனைத்து உறுப்புகளையும் விட அதிகமாக இருக்கும் மற்றும் ஒற்றைப்படை நிலைகளில் உள்ள கூறுகள் முந்தைய கூறுகளை விட குறைவாக இருக்கும்.

அல்காரிதம்

  1. சமநிலையை n / 2 என அமைக்கவும்.
  2. ஒற்றைப்படை நிலையை n - evenPosition என அமைக்கவும்.
  3. ஒரு வரிசையை உருவாக்கவும் (தற்காலிகமானது).
  4. கொடுக்கப்பட்ட வரிசையின் அனைத்து கூறுகளையும் இந்த தற்காலிக வரிசையில் சேமிக்கவும்.
  5. தற்காலிக வரிசையை வரிசைப்படுத்துங்கள்.
  6. ஒற்றைப்படை -1 க்கு சமமாக j ஐ அமைக்கவும்.
  7. கொடுக்கப்பட்ட வரிசையின் சம நிலையில் (குறியீட்டு அடிப்படையிலான) தற்காலிக அசல் வரிசைக்கு நகலெடுத்து j இன் மதிப்பை 1 குறைக்கவும்.
  8. J ஐ ஒற்றைப்படை நிலைக்கு அமைக்கவும்.
  9. கொடுக்கப்பட்ட வரிசையின் ஒற்றைப்படை நிலையில் (குறியீட்டு அடிப்படையிலான) தற்காலிக அசல் [j] க்கு தற்காலிகமாக நகலெடுத்து j இன் மதிப்பை 1 ஆல் அதிகரிக்கவும்.
  10. அசல் வரிசையில் புதுப்பிப்பு செய்யப்பட்டதால் அசல் வரிசையை அச்சிடுக.

விளக்கம்

முழு எண்களின் வரிசையைப் பொறுத்தவரை, வரிசையை மறுசீரமைப்பதே எங்கள் பணி, அதற்கு சமமான எண்ணிக்கையிலான நிலைகளில் உள்ள கூறுகள் அதற்கு முன் உள்ள அனைத்து உறுப்புகளையும் விட அதிகமாக இருக்க வேண்டும். ஒற்றைப்படை எண்ணிக்கையிலான நிலைகளில் உள்ள கூறுகள் அதற்கு முன் இருக்கும் எல்லா எண்களையும் விட குறைவாக இருக்க வேண்டும். சமமான நிலைகளில் உள்ள கூறுகள் அதற்கு முந்தைய எல்லா எண்களையும் விட அதிகமாக இருப்பதால் நாம் எடுத்துக்காட்டில் காணலாம். இங்கே நாம் அதை குறியீட்டு அடிப்படையிலான எண்ணாக எடுத்துக் கொள்ளவில்லை. 0 நிலைகளில் உள்ள உறுப்பு ஒற்றைப்படை 1 நிலையாக கருதப்பட வேண்டும். 1st ஒரு வரிசையின் நிலை 2 நிலை, அதாவது இங்கே, எங்கள் முடிவில் வரிசை அடிப்படையிலான குறியீட்டைக் கருத்தில் கொள்ளவில்லை, 1 முதல் ஒற்றைப்படை வரை n எண்களாகத் தொடங்குகிறோம்.

அசல் வரிசையில் அசல் வரிசையின் நகலை உருவாக்கி, கொடுக்கப்பட்ட வரிசையில் எத்தனை சமமான மற்றும் ஒற்றைப்படை நிலைகள் இருக்கக்கூடும் என்று எண்ணுங்கள். பின்னர், வரிசையை அதிகரிக்கும் வரிசையில் வரிசைப்படுத்தப் போகிறோம். இப்போது வரிசையின் கூறுகளை ஒற்றைப்படை நிலையில் (வரிசை அல்லாத அடிப்படையிலான அட்டவணைப்படுத்தல்), தற்காலிக வரிசையிலிருந்து ஒற்றைப்படை நிலை - 1 முதல் 0 வரை குறைக்கும் மதிப்புகளாக புதுப்பிக்கவும்.

தற்காலிக வரிசையின் பாதியிலிருந்து வரும் அனைத்து உறுப்புகளும் அசல் வரிசையின் ஒற்றைப்படை நிலையில் சேமிக்கப்படும். இதேபோல், தற்காலிக வரிசையின் இரண்டாம் பாதியின் மீதமுள்ள மதிப்புகளை அசல் வரிசையின் சம நிலையில் சேமித்து வைப்போம், இந்த முறையில், நாம் வரிசையை மறுசீரமைக்க முடியும், இதனால் உறுப்புகள் இன்னும் பெரிய நிலைகளிலும் உறுப்புகள் ஒற்றைப்படை ஒற்றைப்படை உறுப்புகளின் நிலைகள் முறையே அதற்கு முன் உள்ள அனைத்து உறுப்புகளையும் விட சிறியதாக இருக்கும்.

நான் சமமாக இருந்தால் arr [i]> = arr [j] வரிசையை மறுசீரமைக்கவும், நான் ஒற்றைப்படை மற்றும் j <i என்றால் arr [i] <= arr [j]

நடைமுறைப்படுத்தல்

சி ++ நிரல்

#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 log n) எங்கே “N” என்பது வரிசையில் உள்ள உறுப்புகளின் எண்ணிக்கை.

விண்வெளி சிக்கலானது

ஓ (n)  எங்கே “N”  என்பது வரிசையில் உள்ள உறுப்புகளின் எண்ணிக்கை.