삽입 정렬

난이도 중급
자주 묻는 질문 Accenture 시스코 작은 골짜기 그루퍼 주니퍼 네트웍스 MAQ 베리타스
배열 정렬조회수 411

시스템 설계 면접 질문 너무 개방적이어서 올바른 준비 방법을 알기가 너무 어렵습니다. 이제 구매 후 Amazon, Microsoft 및 Adobe의 디자인 라운드를 해독할 수 있습니다. 이 책은. 매일 수정 하나 디자인 질문 그리고 나는 당신이 디자인 라운드를 깨뜨릴 수 있다고 약속합니다.

삽입 정렬 알고리즘을 사용하여 지정된 정렬되지 않은 배열을 정렬합니다.

입력: 9,5,1,6,11,8,4 {{}}

출력: 1,4,5,6,8,9,11 {{}}

이론

  • 삽입 정렬은 인간이 일련의 번호가 매겨진 개체 (ex 카드)를 정렬하는 것과 동일한 방식으로 번호를 정렬합니다.
  • 정렬되지 않은 배열 (오른쪽 하위 배열)에서 왼쪽 하위 배열이 정렬 된 상태로 유지되도록 정렬 된 배열 (왼쪽 하위 배열)의 위치로 숫자를 가져옵니다.
  • 점진적 접근 기반 방법입니다.

삽입 정렬 알고리즘

  1. 정렬되지 않은 배열의 첫 번째 요소를 선택 / 표시하고 정렬 된 배열의 올바른 위치로 이동합니다.
  2. 정렬되지 않은 배열의 다음 요소로 마커를 이동합니다.

삽입 정렬

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;
}

산출

1 4 5 6 8 9 11

자바 프로그램

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] +" ");   
    }
}

산출

1 4 5 6 8 9 11

복잡성 분석

  • 시간 복잡성 : T (n) = O (n2)
  • O (n2) 배열이 역으로 정렬되는 시간과 배열이 정렬 된 O (n) 시간.
  • 공간 복잡성 : A (n) = O (1)

추가 정보

  • 삽입 정렬은 내부 정렬 알고리즘입니다.
  • 안정된 성격입니다.
  • 삽입 정렬은 입력 배열이 거의 정렬되었을 때 유용하며, 소수의 요소 만 불완전한 큰 배열로 잘못 배치됩니다.
  • 정렬 할 배열의 크기가 더 작은 경우에도 유용합니다.

참고  면접 질문

균열 시스템 설계 인터뷰
Translate »