අමතර ඉඩක් නොමැතිව පෝලිමක් වර්ග කිරීම  


දුෂ්කරතා මට්ටම පහසු
නිතර අසනු ලැබේ බෙල්සබාර් GE සෞඛ්යාරක්ෂණය මහින්ද්‍රා කොම්විවා MAQ Nvidia Qualcomm සර්විස්නව්
පෝලිමේ වර්ග කිරීම

අමතර අවකාශ ගැටලුවක් නොමැතිව පෝලිමක් වර්ග කිරීමේදී අපි ලබා දී ඇත්තේ a පෝලිමේ, අමතර ඉඩක් නොමැතිව සම්මත පෝලිම් මෙහෙයුම් භාවිතයෙන් එය වර්ග කරන්න.

උදාහරණ  

ආදාන
queue = 10 -> 7 -> 2 -> 8 -> 6
ප්රතිදාන
queue = 2 -> 6 -> 7 -> 8 -> 10

ආදාන
queue = 56 -> 66 -> 1 -> 18 -> 23 -> 39
ප්රතිදාන
queue = 1 -> 18 -> 23 -> 39 -> 56 -> 66

ආදාන
queue = 5 -> 4 -> 3 -> 2 -> 1
ප්රතිදාන
queue = 1 -> 2 -> 3 -> 4 -> 5

අමතර ඉඩක් නොමැතිව පෝලිමක් වර්ග කිරීම සඳහා ඇල්ගොරිතම  

කොටස් දෙකකින් සෑදී ඇති පෝලිම් සලකා බලන්න, එකක් වර්ග කර ඇති අතර අනෙක වර්ග කර නොමැත. මුලදී, සියලුම මූලද්රව්ය වර්ගීකරණය නොකළ කොටසක පවතී.
සෑම පියවරකදීම, වර්ග නොකළ පෝලිමේ සිට අවම මූලද්‍රව්‍යයේ දර්ශකය සොයාගෙන එය පෝලිමේ අවසානයට, එනම් වර්ග කළ කොටස වෙත ගෙන යන්න.
වර්ග කළ පෝලිමේ සියලුම අංග නොපවතින තෙක් මෙම පියවර නැවත කරන්න.

  1. I = 0 සිට n දක්වා ලූපයක් ධාවනය කරන්න (ඇතුළත් කර නැත), මෙහි n යනු පෝලිමේ ප්‍රමාණයයි.
  2. සෑම පුනරාවර්තනයකදීම minIndex -1 ලෙසත් minValue -infinity ලෙසත් ආරම්භ කරන්න.
  3. වර්ගීකරණය නොකළ පෝලිමේ සිට අවම මූලද්‍රව්‍ය දර්ශකය සොයා ගන්නා විචල්‍ය j සමඟ තවත් පුඩුවක් ධාවනය කරන්න. I හි නිශ්චිත අගයක් සඳහා වර්ගීකරණය නොකළ පෝලිම් දර්ශකයේ 0 සිට දර්ශකය (n - i) දක්වා පවතී. සෑම ක්‍රියාවලියකදීම, වත්මන් මූලද්‍රව්‍යය minValue ට වඩා අඩු නම්, minValue වත්මන් මූලද්‍රව්‍යය ලෙසද minIndex j ලෙසද යාවත්කාලීන කරන්න.
  4. පෝලිමේ ගමන් කර minIndex ස්ථානයේ ඇති මූලද්‍රව්‍යය ඉවත් කර පෝලිමේ අවසානයේ එය තල්ලු කරන්න.
  5. පෝලිම් වර්ග කර ඇත, එහි මූලද්රව්ය මුද්රණය කරන්න.
මෙයද බලන්න
දී ඇති අගය x ට සමාන වන වර්ග කළ අරා දෙකකින් යුගල ගණන් කරන්න

අමතර ඉඩක් නොමැතිව පෝලිමක් වර්ග කිරීම සඳහා පැහැදිලි කිරීම  

උදාහරණයක් සලකා බලන්න,
queue = 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 යනු පෝලිමේ ඇති මූලද්‍රව්‍ය ගණන වේ.

මෙයද බලන්න
දී ඇති අරාවක කිසිදු උප කුලකයක එකතුවක් ලෙස නිරූපණය කළ නොහැකි කුඩාම ධන නිඛිල අගය සොයා ගන්න

ආශ්රිත