โปรแกรม C++ อัลกอริทึม Insertion Sort

Insertion Sort

เทคนิคการจัดเรียงนี้คล้ายกับการจัดเรียงไพ่ กล่าวคือ เราจัดเรียงไพ่โดยใช้กลไก Insertion Sort สำหรับเทคนิคนี้ เราเลือกองค์ประกอบหนึ่งจากชุดข้อมูล และเลื่อนองค์ประกอบข้อมูลเพื่อสร้างที่ว่างเพื่อแทรกองค์ประกอบที่เลือกกลับเข้าไปในชุดข้อมูล

ความซับซ้อนของ Insertion Sort

• Time Complexity: O(n) สำหรับกรณีดีที่สุด, O(n²) สำหรับกรณีเฉลี่ยและแย่ที่สุด

• Space Complexity: O(1)

Input - รายการที่ไม่ได้จัดเรียง: 9 45 23 71 80 55
Output - Array after Sorting: 9 23 45 55 71 80

อัลกอริทึม

insertionSort(array, size)

Input: อาร์เรย์ข้อมูล, และจำนวนรวมในอาร์เรย์

Output: อาร์เรย์ที่จัดเรียงแล้ว

เริ่มต้น
  for i := 1 ถึง size-1
    key := array[i]
    j := i
    while j > 0 AND array[j-1] > key
      array[j] := array[j-1]
      j := j - 1
    array[j] := key
สิ้นสุด

โค้ดตัวอย่าง

#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];
        j = i;
        while(j > 0 && array[j-1] > key) {
            array[j] = array[j-1];
            j--;
        }
        array[j] = key;
    }
}

int main() {
    int n;
    cout << "Enter the number of elements: ";
    cin >> n;
    int arr[n];
    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