अतिरिक्त स्थान के बिना एक कतार छँटाई


कठिनाई स्तर आसान
में अक्सर पूछा बेलजब्बर जीई हेल्थकेयर महिंद्रा कॉमिवा MAQ Nvidia क्वालकॉम अभी मरम्मत करें
पंक्ति छंटाई

अतिरिक्त स्थान की समस्या के बिना एक कतार को छाँटने में हमने a पंक्ति, अतिरिक्त जगह के बिना मानक कतार संचालन का उपयोग करके इसे क्रमबद्ध करें।

उदाहरण

निवेश
कतार = 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

अतिरिक्त स्थान के बिना एक कतार छँटाई के लिए एल्गोरिथ्म

दो भागों से बनी कतार पर विचार करें, एक को छाँटा गया है और दूसरे को नहीं छाँटा गया है। प्रारंभ में, सभी तत्व छंटे हुए भाग में मौजूद नहीं होते हैं।
प्रत्येक चरण में, अनसुनी कतार से न्यूनतम तत्व के सूचकांक को ढूंढें और इसे कतार के अंत तक ले जाएँ, अर्थात, छाँटे गए भाग तक।
इस चरण को तब तक दोहराएं जब तक कि सभी तत्व छँटाई कतार में मौजूद न हों।

  1. I = 0 से n (शामिल नहीं) के लिए एक लूप चलाएँ, जहाँ n कतार का आकार है।
  2. प्रत्येक पुनरावृति में मिनिंडेक्स को -1 और मिनल्यू के रूप में -इनफिनिटी को इनिशियलाइज़ करता है।
  3. वेरिएबल j के साथ एक और लूप चलाएं जो कि अनसुनी कतार से न्यूनतम तत्व का इंडेक्स पाता है। बिना किसी विशेष मान के लिए अनुक्रमणिका 0 से अनुक्रमणिका (n - i) तक मौजूद है। प्रत्येक पुनरावृत्ति पर, यदि वर्तमान तत्व minValue से कम है, तो minValue को वर्तमान तत्व और minIndex के रूप में अपडेट करें।
  4. कतार में आगे बढ़ें और स्थिति minIndex पर तत्व निकालें और इसे कतार के अंत में धकेल दें।
  5. कतार को क्रमबद्ध किया गया है, इसके तत्वों को प्रिंट करें।

अतिरिक्त स्थान के बिना एक कतार को छाँटने के लिए स्पष्टीकरण

एक उदाहरण पर विचार करें,
कतार = 10 -> 7 -> 2 -> 8 -> 6

प्रारंभ में, सभी तत्व अनसोल्ड भाग में मौजूद हैं, अर्थात्।

अतिरिक्त स्थान के बिना एक कतार छँटाई

प्रत्येक चरण में, अनसर्ट किए गए भाग में न्यूनतम तत्व का इंडेक्स ढूंढें और इसे कतार के अंत में ले जाएँ, यानी सॉर्ट किया हुआ भाग।

अतिरिक्त स्थान के बिना एक कतार छँटाई

सभी तत्व सॉर्ट किए गए भाग में मौजूद हैं, इसलिए हम रोकते हैं।

अतिरिक्त स्थान के बिना कतार को छाँटने के लिए जावा कोड

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

अतिरिक्त स्थान के बिना एक कतार को छाँटने के लिए C ++ कोड

#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 कतार में तत्वों की संख्या है।

संदर्भ