การเลือกแบบเรียกซ้ำเรียงใน C ++

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

อัลกอริธึมการเรียงลำดับการเลือก

• int arr[5]={ 5,4,2,1,3 };

• int i, j;

• ข้ามจากดัชนี i=0 ถึง i<ขนาดอาร์เรย์ -1

  • ข้ามจากดัชนี j=i+1 ไปยังขนาดอาร์เรย์ - 1

  • ค้นหาที่เล็กที่สุดและเก็บ index.pos

• สลับองค์ประกอบที่ pos ดัชนีที่พบด้วย arr[i]

• สิ้นสุด

การเรียงลำดับการเลือกแบบเรียกซ้ำ

• ค้นหาดัชนีองค์ประกอบขั้นต่ำ

• หากพบว่าดัชนีองค์ประกอบที่เล็กที่สุดเท่ากับขนาดอาร์เรย์ ให้ส่งคืน

• มิฉะนั้น สลับองค์ประกอบปัจจุบันด้วยองค์ประกอบที่เล็กที่สุด

• ทำซ้ำขั้นตอนข้างต้นสำหรับส่วนที่เหลือของอาร์เรย์โดยไม่รวมองค์ประกอบที่จัดเรียง

ตัวอย่าง

ป้อนข้อมูล − Arr[] ={ 5,7,2,3,1,4 }; ความยาว=6

ผลผลิต − เรียงลำดับอาร์เรย์: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 };

ผลผลิต − เรียงลำดับอาร์เรย์: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

แนวทางที่ใช้ในโปรแกรมด้านล่างมีดังนี้

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

• ใช้อาร์เรย์อินพุต Arr[] และความยาวเป็นจำนวนองค์ประกอบในนั้น

• ฟังก์ชัน findMin(int arr[], int i, int j) รับอาร์เรย์และดัชนีและส่งคืนดัชนีขององค์ประกอบขั้นต่ำระหว่าง arr[i+1] ถึง arr[j]

• ใช้ค่าต่ำสุดของตัวแปร

• หากทั้ง i และ j เหมือนกัน ให้คืนค่า i เป็นดัชนีขององค์ประกอบขั้นต่ำเนื่องจากทั้งคู่เหมือนกัน

• มิฉะนั้น recursivley ให้มองหาตำแหน่ง i+1 ถึง j โดยใช้ minpos =findMin(arr, i + 1, j)

• if(arr[i]

• ฟังก์ชัน recurselectSort(int arr1[], int len1, int pos1) รับอาร์เรย์อินพุตและเรียงลำดับจากน้อยไปมากโดยใช้การเรียกซ้ำในการเรียงลำดับการเลือก

• ถ้า pos1 ==len1 แล้วไม่พบขั้นต่ำ ให้ส่งคืน

• ตั้งค่าอื่น minpos1 =findMin(arr1, pos1, len1-1)

• หากดัชนี pos1 ปัจจุบันและดัชนีองค์ประกอบขั้นต่ำ minpos1 ไม่เหมือนกัน ให้สลับองค์ประกอบในดัชนีเหล่านี้โดยใช้ temp

• เรียกซ้ำสำหรับส่วนที่เหลือของอาร์เรย์โดยใช้ recurselectSort(arr1, len1, pos1 + 1)

• ในตอนท้ายของการโทรทั้งหมด เมื่อ len กลายเป็น 1 เราจะออกจากการเรียกซ้ำและอาร์เรย์จะถูกจัดเรียง

• พิมพ์อาร์เรย์ที่เรียงลำดับภายใน main.

ตัวอย่าง

#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