โปรแกรม C++ เรียกซ้ำ Insertion Sort (จริงๆ คือ Bubble Sort)

ภาพรวม

Insertion Sort จัดเรียงโดยแทรกอิลิเมนต์เหมือนการจัดไพ่ เรียงจากซ้ายไปขวา ถือว่าตัวแรกจัดเรียงแล้ว แทรกตัวถัดไปเข้าไปในรายการที่จัดเรียงแล้วทางซ้าย เปรียบเทียบกับทุกตัวในรายการซ้ายจนวางได้ที่ถูกต้อง

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

อัลกอริทึม Insertion Sort

int arr[5] = {5,4,2,1,3};
วน j=i+1 ถึง size-1
เปรียบเทียบ arr[j] กับอิลิเมนต์ใน arr[0..i] หาตำแหน่งที่ arr[i] < arr[j] และ arr[i+1] >= arr[j]
วาง arr[j] และเลื่อนอิลิเมนต์ที่มากกว่าทีละตำแหน่ง

Recursive Insertion Sort (ที่ถูกต้อง)

หากความยาวอาร์เรย์ = 1 คืนค่า
เรียกซ้ำจัดเรียงอิลิเมนต์ดัชนี 0 ถึง size-2
แทรกอิลิเมนต์ตัวสุดท้ายเข้าไปในอาร์เรย์ที่จัดเรียงแล้ว

ตัวอย่าง

อินพุต − Arr[] = {5,7,2,3,1,4}, length=6

เอาต์พุต − Sorted array: 1 2 3 4 5 7

คำอธิบาย −

5 7 2 3 1 4 → 5 จัดเรียงแล้ว
5 7 2 3 1 4 → 7 อยู่ที่ถูกต้อง
2 5 7 3 1 4 → 2 เปรียบเทียบ 5,7 แทรก
2 3 5 7 1 4 → 3 เปรียบเทียบ 5,7 แทรก
1 2 3 5 7 4 → 1 เปรียบเทียบ 2,3,5,7 แทรก
1 2 3 4 5 7 → 4 เปรียบเทียบ 5,7 แทรก

อินพุต − Arr[] = {1, 2, 3, 3, 2}

เอาต์พุต − Sorted array: 1 2 2 3 3

แนวทางโค้ดตัวอย่าง (Recursive Bubble Sort)

Base case: ความยาวอาร์เรย์ = 1 มิฉะนั้น วนลูปเดียวสลับอิลิเมนต์ติดกันที่เรียงผิด ลดความยาวลง 1 เรียกซ้ำ

รับอาร์เรย์ Arr[] และ length
ฟังก์ชัน recurbublSort(int arr[], int len) จัดเรียงแบบเรียกซ้ำ
ตัวแปร temp
หาก len == 1 คืนค่า
วน for (int i=0; i หาก arr[i] > arr[i+1] สลับ


len = len - 1 เรียก recurbublSort(arr, len)
พิมพ์อาร์เรย์ที่จัดเรียงแล้วใน main



ตัวอย่างโค้ด C++
#include <bits/stdc++.h> 
using namespace std; 

void recurbublSort(int arr[], int len){ 
    int temp; 
    if (len == 1){ 
        return; 
    } 
    for (int i = 0; i < len - 1; i++){ 
        if (arr[i] > arr[i + 1]){ 
            temp = arr[i]; 
            arr[i] = arr[i + 1]; 
            arr[i + 1] = temp; 
        } 
    } 
    len = len - 1; 
    recurbublSort(arr, len); 
} 

int main(){ 
    int Arr[] = {21, 34, 20, 31, 78, 43, 66}; 
    int length = sizeof(Arr)/sizeof(Arr[0]); 
    recurbublSort(Arr, length); 
    cout << "Sorted array: "; 
    for(int i = 0; i < length; i++){ 
        cout << Arr[i] << " "; 
    } 
    return 0; 
}

ผลลัพธ์
Sorted array: 20 21 31 34 43 66 78