Dizileri yığınlardan istifadə edərək çeşidləmək

Çətinlik səviyyəsi Mühit
Tez-tez soruşulur Amazon Goldman Sachs IBM Kuliza Yahoo
çeşidləyici QalaqBaxılıb 40

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.

Dizileri yığınlardan istifadə edərək çeşidləməkPin

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

  1. N ölçülü bir [] massivi başladın.
  2. 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.
  3. Eynilə, başqa bir müvəqqəti yığın yaradın.
  4. 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.
  5. 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.
  6. Tmp dəyişənini müvəqqəti yığında itələyin.
  7. 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.
  8. 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.

Translate »