Tez Sortlaşdırmanın təkrarlanan tətbiqi

Çətinlik səviyyəsi Mühit
Tez-tez soruşulur Amazon alma Bloomberg
Geyim çeşidləyiciBaxılıb 735

Sistem dizaynı ilə bağlı müsahibə sualları o qədər açıq ola bilər ki, düzgün hazırlaşmağı bilmək çox çətindir. İndi satın aldıqdan sonra Amazon, Microsoft və Adobe-nin dizayn dövrlərini sındıra bilirəm Bu kitabı. Gündəlik bir yenidən nəzərdən keçirin dizayn sualı və söz verirəm ki, dizayn dövrünü sındıra bilərsiniz.

Problem bəyanat

“Tez Sortlaşdırmanın təkrarlanan tətbiqi” problemində bir array a []. Tez sıralamadan istifadə edərək sıra sıralamalıyıq. Burada sürətli sort rekursiv şəkildə həyata keçirilmir, təkrarlanan bir şəkildə həyata keçirilir.

Giriş Formatı

Bir n tam ədədi olan ilk sətir.

N boşluqla ayrılmış tam ədədi olan ikinci sətir

Çıxış formatı

N boşluqla ayrılmış tam ədədi ehtiva edən ilk və yalnız bir sətir.

Məhdudiyyətlər

  • 1 <= n <= 10 ^ 5
  • -10 ^ 6 <= a [i] <= 10 ^ 6

misal

5
4 1 10 23 5
1 4 5 10 23

Tez Sortlaşdırmanın təkrar tətbiqetmə alqoritmi

Bölmə alqoritmi:

1. Pivot olaraq ən sağ elementi götürün

2. Başlanğıc indeksindən son indeksə qədər bir dəyişən pIndex götürün və başlanğıc indeksinə yönəldin. Element pivotdan azdırsa, elementlə pindex və artım pindex ilə dəyişdirin. Əks təqdirdə, heç bir şey etməyin. yəni, dönmədən az olan bütün elementləri sola, daha böyük elementləri sağa itələmək.

3. Ən sağdakı elementi pIndex ilə elementlə dəyişdirin

4. PIndex qayıdın

Təkrar Quicksort Alqoritmi:

Dizinin ölçüsünə malik bir yığın yaradın

1. Yığıncaqdakı başlanğıc və bitmə başlanğıc dəyərlərini basın, yəni ana sıra (tam sıra) başlanğıc və bitmə indeksləri

2. Yığın boş olana qədər

3.  Yığındakı başlanğıc və bitiş indekslərini açın

4. bölmə funksiyasını çağırın və qaytarma dəyərini pivot_index-də saxlayın

5. İndi pivotdan az olan sol subarray indekslərini yığına itələyin, yəni start, pivot_index -1

6. pivotdan daha böyük olan sağ alt dizi indekslərini yığına, yəni pivot + 1, sonuna itələyin

Həyata keçirilməsi

Sürətli Sortlaşdırmanın təkrarən tətbiqi üçün C ++ Proqramı

#include <bits/stdc++.h> 
using namespace std; 

int partition(int arr[], int l, int h) 
{ 
  int x = arr[h]; 
  int i = (l - 1); 

  for (int j = l; j <= h - 1; j++) { 
    if (arr[j] <= x) { 
      i++; 
      swap(arr[i], arr[j]); 
    } 
  } 
  swap(arr[i + 1], arr[h]); 
  return (i + 1); 
} 

void quick_sort(int arr[], int l, int h) 
{ 
  int stack[h-l+1]; 
  int top = -1; 
  stack[++top]=l; 
  stack[++top]=h; 
  while(top >= 0) 
  { 
    h = stack[top--]; 
    l = stack[top--]; 
    int p = partition(arr, l, h); 
    if(p-1>l) 
    { 
      stack[++top] = l; 
      stack[++top] = p - 1; 
    } 
    if(p+1<h) 
    { 
      stack[++top] = p + 1; 
      stack[++top] = h; 
    } 
  } 
} 

int main() 
{ 
  int n;
  cin>>n;
  int a[n];
  for(int i=0;i<n;i++)
  {
      cin>>a[i];
  }
  quick_sort(a,0,n-1); 
  for(int i=0;i<n;i++)
  {
      cout<<a[i]<<" ";
  }
  cout<<endl;
  return 0; 
}

Sadə Sıralamanın Təkrarlı tətbiqi üçün Java Progeam

import java.util.Collections;
import java.util.Comparator;
import java.util.Iterator;
import java.util.Scanner;
import java.util.Vector;
class sum
{
    static int partition(int arr[], int low, int high) 
    { 
        int pivot = arr[high];
        int i = (low - 1); 
        for (int j = low; j <= high - 1; j++) { 
            if (arr[j] <= pivot) { 
                i++; 
                int temp = arr[i]; 
                arr[i] = arr[j]; 
                arr[j] = temp; 
            } 
        } 
        int temp = arr[i + 1]; 
        arr[i + 1] = arr[high]; 
        arr[high] = temp; 
  
        return i + 1; 
    } 
    static void quick_sort(int arr[], int l, int h) 
    { 
        int[] stack = new int[h - l + 1]; 
        int top = -1; 
        stack[++top] = l; 
        stack[++top] = h; 
        while (top >= 0) { 
            h = stack[top--]; 
            l = stack[top--]; 
            int p = partition(arr, l, h); 
            if (p - 1 > l) { 
                stack[++top] = l; 
                stack[++top] = p - 1; 
            } 
            if (p + 1 < h) { 
                stack[++top] = p + 1; 
                stack[++top] = h; 
            } 
        } 
    }
    public static void main(String[] args)  
    { 
        Scanner sr = new Scanner(System.in);
        int n = sr.nextInt();
        int a[] = new int[n];
        for(int i=0;i<n;i++)
        {
            a[i] = sr.nextInt();
        }
        quick_sort(a,0,n-1);
        for(int i=0;i<n;i++)
        {
            System.out.print(a[i]+" ");
        }
    }
}
5
3 -2 7 4 17
-2 3 4 7 17

Tez Sortlaşdırmanın təkrarən tətbiqi üçün mürəkkəblik analizi

Zamanın mürəkkəbliyi

O (n * logn) hara n verilmiş a [] massivinin ölçüsüdür. Burada bizi n * logn vaxt mürəkkəbliyinə aparan sürətli çeşidləmə alqoritmindən istifadə edərək sıra sıralayırıq.

Kosmik Mürəkkəblik

O (n) hara n verilmiş a [] massivinin ölçüsüdür. Burada dizini sıralamaq üçün yığından istifadə edirik və yığının maksimum ölçüsü n olacaqdır.

Crack Sistemi Dizayn Müsahibələri
Translate »