Sortowanie przez wstawianie

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.

szpilka

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 (n²)
• Zajmuje O (n²) 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