વધારાની જગ્યા વિના કતાર ગોઠવી રહ્યા છીએ  


મુશ્કેલી સ્તર સરળ
વારંવાર પૂછવામાં આવે છે બેલ્ઝાબાર જીઇ હેલ્થકેર મહિન્દ્રા કોમ્વિવા MAQ Nvidia ક્યુઅલકોમ સેવા હવે
કતાર સોર્ટિંગ

વધારાની જગ્યાની સમસ્યા વિના કતારને સingર્ટ કરવામાં આપણે આપેલ એક કતાર, વધારાની જગ્યા વિના પ્રમાણભૂત કતાર કામગીરીનો ઉપયોગ કરીને તેને સ sortર્ટ કરો.

ઉદાહરણો  

ઇનપુટ
કતાર = 10 -> 7 -> 2 -> 8 -> 6
આઉટપુટ
કતાર = 2 -> 6 -> 7 -> 8 -> 10

ઇનપુટ
કતાર = 56 -> 66 -> 1 -> 18 -> 23 -> 39
આઉટપુટ
કતાર = 1 -> 18 -> 23 -> 39 -> 56 -> 66

ઇનપુટ
કતાર = 5 -> 4 -> 3 -> 2 -> 1
આઉટપુટ
કતાર = 1 -> 2 -> 3 -> 4 -> 5

વધારાની જગ્યા વિના કતારને સingર્ટ કરવા માટે એલ્ગોરિધમ  

બે ભાગોથી બનેલી કતારને ધ્યાનમાં લો, એકને સortedર્ટ કરવામાં આવે છે અને બીજો સortedર્ટ કરવામાં આવતો નથી. શરૂઆતમાં, બધા તત્વો સ notર્ટ કરેલા ભાગમાં હાજર છે.
દરેક પગલા પર, સ unsર્ટ કરેલા કતારમાંથી લઘુત્તમ તત્વની અનુક્રમણિકા શોધો અને તેને કતારના અંતમાં, એટલે કે સortedર્ટ કરેલા ભાગ પર ખસેડો.
સ stepર્ટ કતારમાં બધા તત્વો હાજર ન થાય ત્યાં સુધી આ પગલાંને પુનરાવર્તિત કરો.

  1. I = 0 થી n (સમાવેલ નથી) માટે લૂપ ચલાવો, જ્યાં n એ કતારનું કદ છે.
  2. દરેક પુનરાવર્તન પર minIndex -1 તરીકે પ્રારંભ કરો અને minValue -infinity તરીકે.
  3. વેરીએબલ જે સાથે બીજું લૂપ ચલાવો કે જે સ unsર્ટ કરેલા કતારમાંથી ન્યૂનતમ તત્વનું અનુક્રમણિકા શોધે છે. I ની ચોક્કસ કિંમત માટે અનુક્રમિત કતાર અનુક્રમણિકા 0 થી અનુક્રમણિકા (n - i) માટે હાજર છે. દરેક પુનરાવૃત્તિ પર, જો વર્તમાન તત્વ minValue કરતા ઓછું હોય, તો minValue ને વર્તમાન તત્વ તરીકે અને minIndex ને j તરીકે અપડેટ કરો.
  4. કતારમાં પસાર થવું અને મીનીડેક્સ પોઝિશન પર તત્વને દૂર કરો અને કતારના અંતે દબાણ કરો.
  5. કતારને સortedર્ટ કરવામાં આવે છે, તેના તત્વો છાપો.
આ પણ જુઓ
બે સ .ર્ટ કરેલી એરેની જોડીઓ ગણતરી કરો જેનો સરવાળો આપેલ મૂલ્ય x જેટલો છે

વધારાની જગ્યા વિના કતારને ગોઠવવા માટેનો ખુલાસો  

એક ઉદાહરણ ધ્યાનમાં લો,
કતાર = 10 -> 7 -> 2 -> 8 -> 6

શરૂઆતમાં, બધા તત્વો વણઉકેલી ભાગમાં હાજર હોય છે, એટલે કે

વધારાની જગ્યા વિના કતાર ગોઠવી રહ્યા છીએ

દરેક પગલા પર, સortedર્ટ કરેલા ભાગમાં લઘુત્તમ તત્વની અનુક્રમણિકા શોધો અને તેને કતારના અંતમાં, એટલે કે સortedર્ટ કરેલા ભાગ પર ખસેડો.

વધારાની જગ્યા વિના કતાર ગોઠવી રહ્યા છીએપિન

બધા તત્વો સortedર્ટ કરેલા ભાગમાં હાજર છે, તેથી અમે બંધ કરીએ છીએ.

વધારાની જગ્યા વિના કતારને સ .ર્ટ કરવા માટે જાવા કોડ  

import java.util.LinkedList;
import java.util.Queue;

public class SortingAQueueWithoutExtraSpace {
    private static void sortQueue(Queue<Integer> queue) {
        int n = queue.size();

        for (int i = 0; i < n; i++) {
            // Find the index of smallest element from the unsorted queue
            int minIndex = -1;
            int minValue = Integer.MAX_VALUE;
            for (int j = 0; j < n; j++) {
                int currValue = queue.poll();
                // Find the minimum value index only from unsorted queue
                if (currValue < minValue && j < (n - i)) {
                    minValue = currValue;
                    minIndex = j;
                }
                queue.add(currValue);
            }

            // Remove min value from queue
            for (int j = 0; j < n; j++) {
                int currValue = queue.poll();
                if (j != minIndex) {
                    queue.add(currValue);
                }
            }
            // Add min value to the end of the queue
            queue.add(minValue);
        }

        // Print the sorted queue
        for (Integer i : queue) {
            System.out.print(i + " ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        // Example 1
        Queue<Integer> q1 = new LinkedList<>();
        q1.add(10);
        q1.add(7);
        q1.add(2);
        q1.add(8);
        q1.add(6);
        sortQueue(q1);

        // Example 2
        Queue<Integer> q2 = new LinkedList<>();
        q2.add(56);
        q2.add(66);
        q2.add(1);
        q2.add(18);
        q2.add(23);
        q2.add(39);
        sortQueue(q2);
    }
}
2 6 7 8 10 
1 18 23 39 56 66

વધારાની જગ્યા વિના કતારને સingર્ટ કરવા માટે સી ++ કોડ  

#include<bits/stdc++.h> 
using namespace std;

void sortQueue(queue<int> &queue) {
    int n = queue.size();
    
    for (int i = 0; i < n; i++) {
        // Find the index of smallest element from the unsorted queue
        int minIndex = -1;
        int minValue = INT_MAX;
        for (int j = 0; j < n; j++) {
            int currValue = queue.front();
            queue.pop();
            // Find the minimum value index only from unsorted queue
            if (currValue < minValue && j < (n - i)) {
                minValue = currValue;
                minIndex = j;
            }
            queue.push(currValue);
        }Nvidia
Belzabar
        
        // Remove min value from queue
        for (int j = 0; j < n; j++) {
            int currValue = queue.front();
            queue.pop();
            if (j != minIndex) {
                queue.push(currValue);
            }
        }
        // Add min value to the end of the queue
        queue.push(minValue);
    }
    
    // Print the sorted queue
    for (int i = 0; i < n; i++) {
        int curr = queue.front();
        queue.pop();
        cout<<curr<<" ";
        queue.push(curr);
    }
    cout<<endl;
}

int main() {
    // Example 1
    queue<int> q1;
    q1.push(10);
    q1.push(7);
    q1.push(2);
    q1.push(8);
    q1.push(6);
    sortQueue(q1);

    // Example 2
    queue<int> q2;
    q2.push(56);
    q2.push(66);
    q2.push(1);
    q2.push(18);
    q2.push(23);
    q2.push(39);
    sortQueue(q2);
}
2 6 7 8 10 
1 18 23 39 56 66

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

સમય જટિલતા = ઓ (એન2)
જગ્યા જટિલતા = ઓ (1)
જ્યાં n એ કતારમાં રહેલા તત્વોની સંખ્યા છે.

આ પણ જુઓ
નાનામાં સકારાત્મક પૂર્ણાંક મૂલ્ય શોધો કે જે આપેલા એરેના કોઈપણ સબસેટના સરવાળા તરીકે રજૂ થઈ શકશે નહીં

સંદર્ભ