Selection Sort แบบเรียกซ้ำใน C++

ภาพรวม

Selection Sort เป็นอัลกอริทึมจัดเรียงที่วนลูปผ่านอาร์เรย์ตั้งแต่ต้น แทนที่แต่ละอิลิเมนต์ด้วยค่าน้อยที่สุดในส่วนที่ยังไม่จัดเรียง ขณะเคลื่อนไปทางขวา ส่วนซ้ายจะจัดเรียงแล้ว ส่วนขวายังไม่ได้จัดเรียง ทุกขั้นตอนจะสลับค่าน้อยที่สุดถัดไปมาวางที่ตำแหน่งดัชนีปัจจุบัน

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

• int arr[5] = {5,4,2,1,3};
• วน i=0 ถึง size-2
• วน j=i+1 ถึง size-1 หาค่าน้อยที่สุด เก็บดัชนี pos
• สลับ arr[i] กับ arr[pos]

Selection Sort แบบเรียกซ้ำ

• หาดัชนีของค่าน้อยที่สุด
• หากดัชนีน้อยที่สุดเท่ากับขนาดอาร์เรย์ ให้คืนค่า
• มิฉะนั้น สลับอิลิเมนต์ปัจจุบันกับค่าน้อยที่สุด
• เรียกซ้ำสำหรับส่วนที่เหลือ (ข้ามส่วนที่จัดเรียงแล้ว)

ตัวอย่าง

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

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

คำอธิบาย −

First Pass: 5 7 2 3 1 4 → swap → 1 2 7 3 5 4
1 2 7 3 5 4 → no swap
1 2 7 3 5 4 → swap → 1 2 3 7 5 4
1 2 3 7 5 4 → swap → 1 2 3 4 5 7
1 2 3 4 5 7 → no swap

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

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

คำอธิบาย −

1 2 3 3 2 → no swap
1 2 3 2 3 → no swap
1 2 3 2 3 → swap → 1 2 2 3 3
1 2 2 3 3 → no swap

แนวทางการแก้ปัญหา

กรณีฐาน (Base case): ดัชนีน้อยที่สุด = ขนาดอาร์เรย์-1 มิฉะนั้น หาค่าน้อยที่สุดจากอาร์เรย์ สลับกับดัชนีปัจจุบัน เรียกซ้ำจัดเรียงส่วนขวาที่ยังไม่ได้จัดเรียง

• รับอาร์เรย์ Arr[] และ length
• ฟังก์ชัน findMin(int arr[], int i, int j) คืนดัชนีค่าน้อยที่สุดระหว่าง arr[i+1] ถึง arr[j]
• หาก i==j คืน i
• มิฉะนั้น เรียกซ้ำ minpos = findMin(arr, i+1, j)
• หาก arr[i] < arr[minpos] ตั้ง minpos = i คืน minpos
• ฟังก์ชัน recurselectSort(int arr1[], int len1, int pos1) จัดเรียงอาร์เรย์แบบเรียกซ้ำ
• หาก pos1 == len1 คืนค่า
• มิฉะนั้น หา minpos1 = findMin(arr1, pos1, len1-1)
• หาก minpos1 != pos1 สลับด้วยตัวแปร temp
• เรียกซ้ำ recurselectSort(arr1, len1, pos1+1)
• เมื่อ len กลายเป็น 1 จะออกจากการเรียกซ้ำ อาร์เรย์จัดเรียงแล้ว
• พิมพ์อาร์เรย์ที่จัดเรียงแล้วใน main

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

#include <iostream> 
using namespace std; 

int findMin(int arr[], int i, int j){ 
    int minpos; 
    if (i == j){ 
        return i; 
    } 
    minpos = findMin(arr, i + 1, j); 
    if(arr[i] < arr[minpos]){ 
        minpos = i; 
    } 
    return (minpos); 
} 

void recurselectSort(int arr1[], int len1, int pos1){ 
    int temp; 
    int minpos1; 
    if (pos1 == len1){ 
        return; 
    } 
    minpos1 = findMin(arr1, pos1, len1-1); 
    if (minpos1 != pos1){ 
        temp = arr1[pos1]; 
        arr1[pos1] = arr1[minpos1]; 
        arr1[minpos1] = temp; 
    } 
    recurselectSort(arr1, len1, pos1 + 1); 
} 

int main(){ 
    int Arr[] = {1,5,3,0,9,3,5}; 
    int length = sizeof(Arr)/sizeof(Arr[0]); 
    recurselectSort(Arr, length, 0); 
    cout << "Sorted Array using recursive Selection sort: " << endl; 
    for (int i = 0; i < length; i++){ 
        cout << Arr[i] << " "; 
    } 
    return 0; 
}

ผลลัพธ์

Sorted Array using recursive Selection sort: 0 1 3 3 5 5 9