여분의 공간 문제없이 큐를 정렬 할 때 우리는 변발, 추가 공간없이 표준 대기열 작업을 사용하여 정렬합니다.
차례
예
입력
대기열 = 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
추가 공간없이 대기열을 정렬하는 알고리즘
두 부분으로 구성된 대기열을 고려하십시오. 하나는 정렬되고 다른 하나는 정렬되지 않습니다. 처음에는 모든 요소가 정렬되지 않은 부분에 있습니다.
모든 단계에서 정렬되지 않은 대기열에서 최소 요소의 색인을 찾아 대기열의 끝, 즉 정렬 된 부분으로 이동합니다.
정렬 된 대기열에 모든 요소가 없을 때까지이 단계를 반복합니다.
- i = 0에서 n (포함되지 않음)에 대해 루프를 실행합니다. 여기서 n은 큐의 크기입니다.
- 모든 반복에서 minIndex를 -1로 초기화하고 minValue를 -infinity로 초기화합니다.
- 정렬되지 않은 큐에서 최소 요소의 인덱스를 찾는 변수 j로 다른 루프를 실행합니다. 정렬되지 않은 큐는 i의 특정 값에 대해 인덱스 0부터 인덱스 (n – i)까지 존재합니다. 반복 할 때마다 현재 요소가 minValue보다 작 으면 minValue를 현재 요소로 업데이트하고 minIndex를 j로 업데이트합니다.
- 큐를 순회하고 minIndex 위치에서 요소를 제거하고 큐의 끝에 푸시하십시오.
- 대기열이 정렬되고 해당 요소를 인쇄합니다.
추가 공간없이 대기열 정렬에 대한 설명
예를 들어,
대기열 = 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은 큐의 요소 수입니다.
