Sortowanie przez wstawianie

Poziom trudności Średni
Często zadawane pytania Accenture Cisco kotlina Groferzy Juniper Networks MAQ Veritas
Szyk Sortowanieodwiedzajacy 411

Pytania do rozmowy kwalifikacyjnej na temat projektowania systemu może być tak nieograniczona, że ​​trudno jest określić właściwy sposób przygotowania. Teraz jestem w stanie złamać rundy projektowe Amazon, Microsoft i Adobe po zakupie ta książka. Codziennie poprawiaj jeden pytanie projektowe i obiecuję, że możesz złamać cały projekt.

Sortuj podaną nieposortowaną tablicę za pomocą algorytmu sortowania przez wstawianie.

Wejście: 9,5,1,6,11,8,4 {}

Wyjście: 1,4,5,6,8,9,11 {}

Teoria

  • Sortowanie przez wstawianie sortuje liczby w taki sam sposób, w jaki my, ludzie, sortujemy zestaw ponumerowanych obiektów (np. Karty)
  • Liczba jest pobierana z niesortowanej tablicy (prawa podtablica) do pozycji w posortowanej tablicy (lewa podtablica), tak że lewa podtablica pozostaje posortowana.
  • Jest to metoda oparta na podejściu przyrostowym.

Algorytm sortowania przez wstawianie

  1. Wybierz / zaznacz pierwszy element w niesortowanej tablicy, przenieś go na właściwą pozycję w posortowanej tablicy.
  2. Przesuń znacznik do następnego elementu w niesortowanej tablicy.

Sortowanie przez wstawianieszpilka

Program w C ++

#include <iostream>
using namespace std;

void insertSort(int arr[],int n)
{
    int i,j,save;

    for(int i=1;i<n;i++)
    {
        j = i-1;
        save = arr[i];
        
        // look for correct position of arr[i]
        while(j>=0 && arr[j] > save)
        {
            // shifting array elements towards the right
            arr[j+1] = arr[j];
            j--;
        }
        // place arr[i] at the correct position
        arr[j+1] = save;
    }
}

int main()
{
    
    int arr[] = {9,5,1,6,11,8,4};
    int n = sizeof(arr)/sizeof(arr[0]);

    insertSort(arr,n);

    for(int i=0;i<n;i++)
    cout<<arr[i]<<" ";
    
    return 0;
}

Wydajność

1 4 5 6 8 9 11

Program Java

class iSort
{
    static void insertSort(int arr[])
    {
        int n = arr.length;
        int i,j,save;

        for(i=1;i<n;i++)
        {
            j = i-1;
            save = arr[i];

            // look for correct position of arr[i]
            while(j >= 0 && arr[j] > save)
            {
                // shifting array elements towards the right
                arr[j+1] = arr[j];
                j--;
            }
            // place arr[i] at the correct position
            arr[j+1] = save;
        }
    }

    public static void main(String args[]) 
    {
        int arr[] = {9,5,1,6,11,8,4};
        insertSort(arr);

        for(int i=0;i<arr.length;i++)
        System.out.print(arr[i] +" ");   
    }
}

Wydajność

1 4 5 6 8 9 11

Analiza złożoności

  • Złożoność czasowa: T (n) = O (n2)
  • Zajmuje O (n2) czas, gdy tablica jest posortowana odwrotnie i O (n) czas, gdy tablica jest posortowana.
  • Złożoność przestrzeni: A (n) = O (1)

Dodatkowa informacja

  • Sortowanie przez wstawianie to algorytm sortowania w miejscu.
  • To jest stabilna natura.
  • Sortowanie przez wstawianie jest przydatne, gdy tablica wejściowa jest prawie posortowana, tylko kilka elementów jest umieszczonych w niewłaściwym miejscu niekompletna duża tablica.
  • Jest to również przydatne, gdy sortowana tablica ma mniejszy rozmiar.

Numer Referencyjny  Wywiad Pytania

Wywiady dotyczące projektowania systemu pękania
Translate »