Сортиране на опашка без допълнително пространство  


Ниво на трудност Лесно
Често задавани в Белзабар GE Healthcare Махиндра Комвива Maq Nvidia Qualcomm ServiceNow
Опашка сортиране

При сортирането на опашка без проблем с допълнително пространство ние дадохме 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. При всяка итерация инициализирайте minIndex като -1 и minValue като -infinity.
  3. Изпълнете друг цикъл с променлива j, който намира индекса на минималния елемент от несортираната опашка. Несортираната опашка присъства от индекс 0 до индекс (n - i) за определена стойност на i. При всяка итерация, ако текущият елемент е по-малък от minValue, актуализирайте minValue като текущ елемент и minIndex като j.
  4. Преминете в опашката и премахнете елемента в позиция minIndex и го натиснете в края на опашката.
  5. Опашката е сортирана, отпечатайте нейните елементи.
Вижте също
Бройте двойки от два сортирани масива, чиято сума е равна на дадена стойност x

Обяснение за сортиране на опашка без допълнително пространство  

Помислете за пример,
опашка = 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 е броят на елементите в опашката.

Вижте също
Намерете най-малката положителна целочислена стойност, която не може да бъде представена като сума от което и да е подмножество на даден масив

Препратки