Mündəricat
Problem bəyanat
"Yığınlardan istifadə edərək sıra sıralama" problemi sizə bir məlumat quruluşunun verildiyini bildirir array n ölçülü bir []. Cür verilən massivin elementlərindən istifadə olunur qalaq məlumatların quruluşu.
misal
2 30 -5 43 100
-5 2 30 43 100
İzahat: Elementlər artan sırada sıralanır.
2 3 1 8 6
1 2 3 6 8
Yığınlardan istifadə edərək sıra sıralamaq üçün yanaşma
Verilən giriş massivinin bütün elementlərini saxlamaq üçün bir yığın məlumat quruluşu yaradın a]]. Bundan sonra, orijinalını sıralamaq üçün başqa bir müvəqqəti yığın yaradın. Orijinal yığını təkrarlayın və hər element üçün yuxarı hissəni açın və müvəqqəti dəyişəndə saxlayın. Eynilə, müvəqqəti yığının üstündəki element orijinal yığının üst hissəsindən az olduqda, müvəqqəti yığının arasından təkrarlayın. Müvəqqəti yığının üst hissəsini orijinal yığına daxil edin və müvəqqəti yığından çıxarın. Orijinal yığının üst hissəsini müvəqqəti yığına itələyin. Sonda müvəqqəti yığında sıralanmış qaydada elementlər olacaqdır. Bu problem a növü üzərində cüzi bir dəyişiklikdir müvəqqəti yığını istifadə edərək yığmaq.
Alqoritm
- N ölçülü bir [] massivi başladın.
- Bir yığın məlumat strukturu yaradın. A [] massivindən keçin və yığının içindəki a [] bütün elementlərini itələyin.
- Eynilə, başqa bir müvəqqəti yığın yaradın.
- Orijinal yığının ölçüsü 0 olmadıqda keçin. Dəyişən bir tmp yaradın və elementi içindəki orijinal yığının üstündə saxlayın və orijinal yığından çıxarın.
- Müvəqqəti yığın boş deyilsə yenidən keçin və elementi müvəqqəti yığının üstündəki tmp dəyişəndən az olana qədər açın. Müvəqqəti yığından çıxarkən, müvəqqəti yığının üst hissəsini orijinal yığına itələyin.
- Tmp dəyişənini müvəqqəti yığında itələyin.
- 0-dan n-1-ə keçin və müvəqqəti yığının üst elementini cari indeksdə [] massivində saxlayın və elementi müvəqqəti yığından silin / silin.
- Nəhayət, 0-dan n-1-ə keçin və a [] dizisini çap edin.
Kodu
Yığınlardan istifadə edərək sıra sıralamaq üçün C ++ proqramı
#include <iostream>
#include <stack>
using namespace std;
stack<int> sortStack(stack<int> input){
stack<int> tmpStack;
while(!input.empty()){
int tmp = input.top();
input.pop();
while (!tmpStack.empty() && tmpStack.top() < tmp){
input.push(tmpStack.top());
tmpStack.pop();
}
tmpStack.push(tmp);
}
return tmpStack;
}
void sortUsingStack(int arr[], int n){
stack<int> input;
for(int i=0; i<n; i++){
input.push(arr[i]);
}
stack<int> tmpStack = sortStack(input);
for(int i=0; i<n; i++){
arr[i] = tmpStack.top();
tmpStack.pop();
}
}
int main(){
int a[] = {2, 30, -5, 43, 100};
int n = sizeof(a)/sizeof(a[0]);
sortUsingStack(a, n);
for(int i=0; i<n; i++)
cout << a[i] << " ";
return 0;
}
-5 2 30 43 100
Yığınlardan istifadə edərək serialın çeşidlənməsi üçün Java Proqramı
import java.io.*;
import java.util.*;
class SortArrayWithStack{
static Stack<Integer> sortStack(Stack<Integer> input){
Stack<Integer> tmpStack = new Stack<Integer>();
while(!input.empty()){
int tmp = input.peek();
input.pop();
while(!tmpStack.empty() && tmpStack.peek() < tmp){
input.push(tmpStack.peek());
tmpStack.pop();
}
tmpStack.push(tmp);
}
return tmpStack;
}
static void sortUsingStack(int []arr, int n){
Stack<Integer> input = new Stack<Integer>();
for(int i = 0; i < n; i++){
input.push(arr[i]);
}
Stack<Integer> tmpStack = sortStack(input);
for(int i = 0; i < n; i++){
arr[i] = tmpStack.peek();
tmpStack.pop();
}
}
public static void main(String args[]){
int []a = {2, 30, -5, 43, 100};
int n = a.length;
sortUsingStack(a, n);
for(int i = 0; i < n; i++){
System.out.print(a[i] + " ");
}
}
}
-5 2 30 43 100
Mürəkkəblik təhlili
Zamanın mürəkkəbliyi
O (n ^ 2) burada n yığındakı elementlərin sayıdır. Müvəqqəti yığının üstü itələyiləcək elementdən daha az olması halında elementləri müvəqqəti yığından orijinal yığına itələdiyimiz üçün. Daha yaxşı başa düşmək üçün azalan bir sıra ardıcıllığını nəzərdən keçirin və alqoritmi işləməyə çalışın.
Kosmik Mürəkkəblik
O (n) n element üçün müvəqqəti yığın yerindən istifadə etdiyimiz üçün. Orijinal yığının istifadə etdiyi boşluq alqoritm üçün sayılmır.
