Sắp xếp chèn

Kỹ thuật sắp xếp này tương tự với kỹ thuật sắp xếp thẻ, nói cách khác, chúng tôi sắp xếp thẻ bằng cách sử dụng cơ chế sắp xếp chèn. Đối với kỹ thuật này, chúng tôi chọn một phần tử từ tập dữ liệu và chuyển các phần tử dữ liệu để tạo vị trí chèn lại phần tử đã chọn vào tập dữ liệu.

Sự phức tạp của Kỹ thuật Sắp xếp Chèn

• Độ phức tạp về thời gian:O (n) cho trường hợp tốt nhất, O (n ^ 2) cho trường hợp trung bình và xấu nhất
• Độ phức tạp của không gian:O (1)

Đầu vào và Đầu ra

Input:
The unsorted list: 9 45 23 71 80 55
Output:
Array before Sorting: 9 45 23 71 80 55
Array after Sorting: 9 23 45 55 71 80

Thuật toán

insertionSort(array, size)

Đầu vào - Một mảng dữ liệu và tổng số trong mảng

Đầu ra &- Mảng được sắp xếp

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

Ví dụ

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

Đầu ra

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