logo

TechCodeview

삽입 정렬 – 데이터 구조 및 알고리즘 자습서

삽입 정렬 정렬되지 않은 목록의 각 요소를 목록의 정렬된 부분에 있는 올바른 위치에 반복적으로 삽입하여 작동하는 간단한 정렬 알고리즘입니다. 이것은 안정적인 정렬 알고리즘은 동일한 값을 가진 요소가 정렬된 출력에서 ​​상대적 순서를 유지함을 의미합니다.

삽입 정렬 손에 있는 카드 놀이를 분류하는 것과 같습니다. 카드를 정렬된 카드와 정렬되지 않은 카드의 두 그룹으로 나눕니다. 그런 다음 정렬되지 않은 그룹에서 카드를 선택하여 정렬된 그룹의 올바른 위치에 놓습니다.



삽입 정렬 알고리즘:

삽입 정렬 한 번에 한 요소씩 정렬된 배열을 작성하여 작동하는 간단한 정렬 알고리즘입니다. 그것은 간주됩니다 제자리에 정렬 알고리즘은 원래 배열 외에 추가 메모리 공간이 필요하지 않음을 의미합니다.

하위 문자열 java가 포함되어 있습니다.

연산:

삽입 정렬을 수행하려면 다음 단계를 따르세요.



  • 배열의 첫 번째 요소가 정렬된 것으로 가정하므로 배열의 두 번째 요소부터 시작해야 합니다.
  • 두 번째 요소를 첫 번째 요소와 비교하고 두 번째 요소가 더 작은지 확인한 다음 교체합니다.
  • 세 번째 요소로 이동하여 두 번째 요소와 비교한 다음 필요에 따라 첫 번째 요소를 교체하여 처음 세 요소 중 올바른 위치에 배치합니다.
  • 이 프로세스를 계속하여 각 요소를 이전 요소와 비교하고 필요에 따라 교체하여 정렬된 요소 중 올바른 위치에 배치합니다.
  • 전체 배열이 정렬될 때까지 반복합니다.

삽입 정렬 알고리즘의 작동:

요소가 있는 배열을 고려해보세요. : {23, 1, 10, 5, 2}

첫 번째 패스:



  • 현재 요소는 23
  • 배열의 첫 번째 요소는 정렬된 것으로 간주됩니다.
  • 까지 정렬된 부분 0번째 인덱스는 다음과 같습니다 [23]

두 번째 패스:

  • 비교하다 1 ~와 함께 23 (정렬된 부분이 있는 현재 요소).
  • 부터 1 더 작으니 삽입하세요 1 ~ 전에 23 .
  • 까지 정렬된 부분 1위 인덱스는 다음과 같습니다 [1, 23]

세 번째 패스:

int를 더블 자바로 변환
  • 비교하다 10 ~와 함께 1 그리고 23 (정렬된 부분이 있는 현재 요소).
  • 부터 10 보다 크다 1 그리고 보다 작다 23 , 삽입 10 ~ 사이 1 그리고 23 .
  • 까지 정렬된 부분 2위 인덱스는 다음과 같습니다 [1, 10, 23]

네 번째 패스:

  • 비교하다 5 ~와 함께 1 , 10 , 그리고 23 (정렬된 부분이 있는 현재 요소).
  • 부터 5 보다 크다 1 그리고 보다 작다 10 , 삽입 5 ~ 사이 1 그리고 10 .
  • 까지 정렬된 부분 3번째 지수는 : [1, 5, 10, 23]

다섯 번째 패스:

  • 비교하다 2 ~와 함께 1, 5, 10 , 그리고 23 (정렬된 부분이 있는 현재 요소).
  • 부터 2 보다 크다 1 그리고 보다 작다 5 끼워 넣다 2 ~ 사이 1 그리고 5 .
  • 까지 정렬된 부분 4번째 인덱스는 다음과 같습니다 [1, 2, 5, 10, 23]

최종 어레이:

  • 정렬된 배열은 다음과 같습니다. [1, 2, 5, 10, 23]
추천 연습 삽입정렬 시도해 보세요!

삽입 정렬 구현:

C++ 
// C++ program for insertion sort #include  using namespace std; // Function to sort an array using // insertion sort void insertionSort(int arr[], int n) {  int i, key, j;  for (i = 1; i < n; i++) {  key = arr[i];  j = i - 1;  // Move elements of arr[0..i-1],  // that are greater than key,   // to one position ahead of their  // current position  while (j>= 0 && arr[j]> 키) { arr[j + 1] = arr[j];  j = j - 1;  } arr[j + 1] = 키;  } } // n 크기의 배열을 // 인쇄하는 유틸리티 함수 void printArray(int arr[], int n) { int i;  (i = 0; 나는< n; i++)  cout << arr[i] << ' ';  cout << endl; } // Driver code int main() {  int arr[] = { 12, 11, 13, 5, 6 };  int N = sizeof(arr) / sizeof(arr[0]);  insertionSort(arr, N);  printArray(arr, N);  return 0; } // This is code is contributed by rathbhupendra>
씨 
// C program for insertion sort #include  #include  /* Function to sort an array using insertion sort*/ void insertionSort(int arr[], int n) {  int i, key, j;  for (i = 1; i < n; i++) {  key = arr[i];  j = i - 1;  /* Move elements of arr[0..i-1], that are  greater than key, to one position ahead  of their current position */  while (j>= 0 && arr[j]> 키) { arr[j + 1] = arr[j];  j = j - 1;  } arr[j + 1] = 키;  } } // n 크기의 배열을 인쇄하는 유틸리티 함수 void printArray(int arr[], int n) { int i;  (i = 0; 나는< n; i++)  printf('%d ', arr[i]);  printf('
'); } /* Driver program to test insertion sort */ int main() {  int arr[] = { 12, 11, 13, 5, 6 };  int n = sizeof(arr) / sizeof(arr[0]);  insertionSort(arr, n);  printArray(arr, n);  return 0; }>
자바 
// Java program for implementation of Insertion Sort public class InsertionSort {  /*Function to sort array using insertion sort*/  void sort(int arr[])  {  int n = arr.length;  for (int i = 1; i < n; ++i) {  int key = arr[i];  int j = i - 1;  /* Move elements of arr[0..i-1], that are  greater than key, to one position ahead  of their current position */  while (j>= 0 && arr[j]> 키) { arr[j + 1] = arr[j];  j = j - 1;  } arr[j + 1] = 키;  } } /* n* 크기의 배열을 인쇄하는 유틸리티 함수 static void printArray(int arr[]) { int n = arr.length;  for (int i = 0; i< n; ++i)  System.out.print(arr[i] + ' ');  System.out.println();  }  // Driver method  public static void main(String args[])  {  int arr[] = { 12, 11, 13, 5, 6 };  InsertionSort ob = new InsertionSort();  ob.sort(arr);  printArray(arr);  } }; /* This code is contributed by Rajat Mishra. */>
파이썬 
# Python program for implementation of Insertion Sort # Function to do insertion sort def insertionSort(arr): # Traverse through 1 to len(arr) for i in range(1, len(arr)): key = arr[i] # Move elements of arr[0..i-1], that are # greater than key, to one position ahead # of their current position j = i-1 while j>= 0 및 키< arr[j] : arr[j + 1] = arr[j] j -= 1 arr[j + 1] = key # Driver code to test above arr = [12, 11, 13, 5, 6] insertionSort(arr) for i in range(len(arr)): print ('% d' % arr[i]) # This code is contributed by Mohit Kumra>
씨# 
// C# program for implementation of Insertion Sort using System; class InsertionSort {  // Function to sort array  // using insertion sort  void sort(int[] arr)  {  int n = arr.Length;  for (int i = 1; i < n; ++i) {  int key = arr[i];  int j = i - 1;  // Move elements of arr[0..i-1],  // that are greater than key,  // to one position ahead of  // their current position  while (j>= 0 && arr[j]> 키) { arr[j + 1] = arr[j];  j = j - 1;  } arr[j + 1] = 키;  } } // 인쇄하기 위한 유틸리티 함수 // n 크기의 배열 static void printArray(int[] arr) { int n = arr.Length;  for (int i = 0; i< n; ++i)  Console.Write(arr[i] + ' ');  Console.Write('
');  }  // Driver Code  public static void Main()  {  int[] arr = { 12, 11, 13, 5, 6 };  InsertionSort ob = new InsertionSort();  ob.sort(arr);  printArray(arr);  } } // This code is contributed by ChitraNayal.>
자바스크립트 
>
PHP 
 // PHP program for insertion sort // Function to sort an array // using insertion sort function insertionSort(&$arr, $n) { for ($i = 1; $i < $n; $i++) { $key = $arr[$i]; $j = $i-1; // Move elements of arr[0..i-1], // that are greater than key, to  // one position ahead of their  // current position while ($j>= 0 && $arr[$j]> $key) { $arr[$j + 1] = $arr[$j]; $j = $j - 1; } $arr[$j + 1] = $key; } } // // n 크기의 배열을 인쇄하는 유틸리티 함수 function printArray(&$arr, $n) { for ($i = 0; $i< $n; $i++) echo $arr[$i].' '; echo '
'; } // Driver Code $arr = array(12, 11, 13, 5, 6); $n = sizeof($arr); insertionSort($arr, $n); printArray($arr, $n); // This code is contributed by ChitraNayal. ?>>
산출 
5 6 11 12 13>

시간 복잡도: 오(N^2)
보조 공간: 오(1)

삽입 정렬의 복잡성 분석 :

삽입 정렬의 시간 복잡도

  • 최선의 경우: 에) , 목록이 이미 정렬된 경우 여기서 n은 목록의 요소 수입니다.
  • 평균 사례: 에 2 ) , 목록이 무작위로 정렬된 경우
  • 최악의 경우: 에 2 ) , 목록이 역순으로 되어 있는 경우

공간 복잡도 삽입정렬

  • 보조 공간: O(1), 삽입 정렬이 필요함 오(1) 추가 공간을 제공하므로 공간 효율적인 정렬 알고리즘이 됩니다.

장점 삽입 정렬:

  • 간단하고 구현하기 쉽습니다.
  • 안정적인 정렬 알고리즘.
  • 작은 목록과 거의 정렬된 목록에 효율적입니다.
  • 공간 효율적입니다.

단점 삽입 정렬:

  • 큰 목록에는 비효율적입니다.
  • 대부분의 경우 다른 정렬 알고리즘(예: 병합 정렬, 빠른 정렬)만큼 효율적이지 않습니다.

응용 삽입 정렬:

삽입 정렬은 일반적으로 다음과 같은 상황에서 사용됩니다.

  • 목록이 작거나 거의 정렬되어 있습니다.
  • 단순성과 안정성이 중요합니다.

삽입 정렬에 대해 자주 묻는 질문

Q1. 삽입 정렬 알고리즘의 경계 사례는 무엇입니까?

개발자 모드를 비활성화하는 방법

삽입 정렬은 요소를 역순으로 정렬하는 경우 정렬하는 데 최대 시간이 걸립니다. 그리고 요소가 이미 정렬되어 있으면 최소 시간(Order of n)이 걸립니다.

Q2. 삽입 정렬 알고리즘의 알고리즘 패러다임은 무엇입니까?

삽입 정렬 알고리즘은 증분 방식을 따릅니다.

Q3. 삽입 정렬은 내부 정렬 알고리즘인가요?

예, 삽입 정렬은 내부 정렬 알고리즘입니다.

Q4. 삽입 정렬은 안정적인 알고리즘인가요?

AWS SNS

예, 삽입 정렬은 안정적인 정렬 알고리즘입니다.

Q5. 삽입정렬 알고리즘은 언제 사용되나요?

삽입 정렬은 요소의 개수가 적을 때 사용됩니다. 또한 입력 배열이 거의 정렬되어 있고 완전한 큰 배열에서 소수의 요소만 잘못 배치된 경우에도 유용할 수 있습니다.