C++의 삽입 정렬 시간 복잡도 질문

삽입 정렬의 시간 복잡도는 얼마입니까?

시간 복잡도 코드 또는 알고리즘 세트가 입력량의 함수로 처리하거나 실행하는 데 걸리는 시간입니다.

삽입 정렬의 경우 시간 복잡도는 O(n), 즉 최상의 시나리오에서 n의 큰 O입니다. 평균 또는 최악의 시나리오에서 복잡성은 O(n ² ).

6, 5, 8, 7, 10, 9 …

위의 배열을 정렬하는 형식의 시간 복잡도는 O(n)입니다. 이 알고리즘을 주의 깊게 살펴보겠습니다. 여기에서 모든 쌍은 원래 위치에서 교체됩니다. 즉, 요소 ​​1과 요소 2의 위치가 서로 바뀌고 3과 4가 교환되는 식입니다. 따라서 알고리즘을 정렬하는 동안 이 알고리즘을 정렬하는 데 n번의 작업만 수행됩니다.

삽입 정렬을 정의하고 삽입 정렬을 위한 코드를 작성하시겠습니까?

삽입 정렬은 정렬된 배열의 해당 위치에 요소를 배치하여 데이터 구조를 정렬하는 정렬 알고리즘입니다.

아래 코드는 삽입 정렬을 위한 함수를 보여줍니다 -

예시

void insertionSort(int arr[], int n) {
   for (int i = 1; i < n; i++){
      int element = arr[i];
      int j = i-1;
      while (j >= 0 && arr[j] > element){
         arr[j+1] = arr[j];
         j = j-1;
      }
      arr[j+1] = element;
   }
}