Əlavə yer problemi olmadan növbə sıralamasında a queue, əlavə yer olmadan standart növbə əməliyyatları istifadə edərək sıralayın.
Mündəricat
Nümunələr
Input
növbə = 10 -> 7 -> 2 -> 8 -> 6
Buraxılış
növbə = 2 -> 6 -> 7 -> 8 -> 10
Input
növbə = 56 -> 66 -> 1 -> 18 -> 23 -> 39
Buraxılış
növbə = 1 -> 18 -> 23 -> 39 -> 56 -> 66
Input
növbə = 5 -> 4 -> 3 -> 2 -> 1
Buraxılış
növbə = 1 -> 2 -> 3 -> 4 -> 5
Əlavə boşluq olmadan növbəni çeşidləmək üçün alqoritm
İki hissədən ibarət növbəni nəzərdən keçirək, biri sıralanır, digəri sıralanmır. Başlanğıcda, bütün elementlər sıralanmamış hissədə mövcuddur.
Hər addımda, sıralanmamış növbədən minimum elementin indeksini tapın və növbənin sonuna, yəni sıralanmış hissəyə aparın.
Bütün elementlər sıralanmış növbədə olmayana qədər bu addımı təkrarlayın.
- N-nin növbənin ölçüsü olduğu i = 0-dan n-ə (daxil deyil) bir döngə işlədin.
- Hər təkrarlamada minIndex-i -1 və minValue -infinity olaraq başladın.
- Minimum element indeksini çeşidlənməmiş növbədən tapan j dəyişən ilə başqa bir döngə işlədin. Sıralanmamış növbə, müəyyən bir i dəyəri üçün indeks 0-dan indeksə (n - i) qədərdir. Hər təkrarlamada, cari element minValue-dan azdırsa, minValue-nu cari element və minIndex-i j kimi yeniləyin.
- Növbədə keçin və elementi minIndex mövqeyində çıxarın və növbənin sonunda itələyin.
- Sıra sıralanır, elementlərini çap edin.
Əlavə Yer olmadan Sıranın Çeşidlənməsi üçün İzahat
Bir nümunəyə baxaq,
növbə = 10 -> 7 -> 2 -> 8 -> 6
Başlanğıcda, bütün elementlər çeşidlənməmiş hissədə mövcuddur, yəni
Hər addımda, çeşidlənməmiş hissədə minimum elementin indeksini tapın və növbənin sonuna, yəni sıralanmış hissəyə aparın.
Bütün elementlər sıralanmış hissədə mövcuddur, buna görə dayanırıq.
Əlavə Yer olmadan Sıranı Çeşidləmək üçün JAVA Kodu
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
Əlavə Yer olmadan Sıranı Çeşidləmək üçün C ++ Kodu
#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
Mürəkkəblik təhlili
Zaman Mürəkkəbliyi = O (n)2)
Kosmik Mürəkkəblik = O (1)
burada n növbədəki elementlərin sayıdır.
