이 정렬 기술은 카드 정렬 기술과 유사합니다. 즉, 삽입 정렬 메커니즘을 사용하여 카드를 정렬합니다. 이 기술의 경우 데이터 세트에서 하나의 요소를 선택하고 데이터 요소를 이동하여 선택한 요소를 데이터 세트에 다시 삽입할 위치를 만듭니다.
삽입 정렬 기법의 복잡성
-
시간 복잡도:최상의 경우 O(n), 평균 및 최악의 경우 O(n2)
-
공간 복잡도:O(1)
Input − The unsorted list: 9 45 23 71 80 55 Output − Array after Sorting: 9 23 45 55 71 80
알고리즘
insertionSort(배열, 크기)
입력 :데이터 배열 및 배열의 총 개수
출력 :정렬된 배열
Begin
for i := 1 to size-1 do
key := array[i]
j := i
while j > 0 AND array[j-1] > key do
array[j] := array[j-1];
j := j – 1
done
array[j] := key
done
End 예시 코드
#include<iostream>
using namespace std;
void display(int *array, int size) {
for(int i = 0; i<size; i++)
cout << array[i] << " ";
cout << endl;
}
void insertionSort(int *array, int size) {
int key, j;
for(int i = 1; i<size; i++) {
key = array[i];//take value
j = i;
while(j > 0 && array[j-1]>key) {
array[j] = array[j-1];
j--;
}
array[j] = key; //insert in right place
}
}
int main() {
int n;
cout << "Enter the number of elements: ";
cin >> n;
int arr[n]; //create an array with given number of elements
cout << "Enter elements:" << endl;
for(int i = 0; i<n; i++) {
cin >> arr[i];
}
cout << "Array before Sorting: ";
display(arr, n);
insertionSort(arr, n);
cout << "Array after Sorting: ";
display(arr, n);
} 출력
Enter the number of elements: 6 Enter elements: 9 45 23 71 80 55 Array before Sorting: 9 45 23 71 80 55 Array after Sorting: 9 23 45 55 71 80