추가 공간없이 대기열 정렬

난이도 쉽게
자주 묻는 질문 벨자바르 GE 헬스 케어 마힌 드라 콤비 바 MAQ 엔비디아 퀄컴 ServiceNow
정렬조회수 36

여분의 공간 문제없이 큐를 정렬 할 때 우리는 변발, 추가 공간없이 표준 대기열 작업을 사용하여 정렬합니다.

입력
대기열 = 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. 모든 반복에서 minIndex를 -1로 초기화하고 minValue를 -infinity로 초기화합니다.
  3. 정렬되지 않은 큐에서 최소 요소의 인덱스를 찾는 변수 j로 다른 루프를 실행합니다. 정렬되지 않은 큐는 i의 특정 값에 대해 인덱스 0부터 인덱스 (n – i)까지 존재합니다. 반복 할 때마다 현재 요소가 minValue보다 작 으면 minValue를 현재 요소로 업데이트하고 minIndex를 j로 업데이트합니다.
  4. 큐를 순회하고 minIndex 위치에서 요소를 제거하고 큐의 끝에 푸시하십시오.
  5. 대기열이 정렬되고 해당 요소를 인쇄합니다.

추가 공간없이 대기열 정렬에 대한 설명

예를 들어,
대기열 = 10-> 7-> 2-> 8-> 6

처음에는 모든 요소가 정렬되지 않은 부분에 있습니다. 즉,

추가 공간없이 대기열 정렬

모든 단계에서 정렬되지 않은 부분에서 최소 요소의 인덱스를 찾아 대기열의 끝, 즉 정렬 된 부분으로 이동합니다.

추가 공간없이 대기열 정렬

모든 요소가 정렬 된 부분에 있으므로 중지합니다.

추가 공간없이 대기열 정렬을위한 JAVA 코드

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)
공간 복잡성 = O (1)
여기서 n은 큐의 요소 수입니다.

참조

Translate »