โปรแกรม C สำหรับ Recursive Bubble Sort

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

อัลกอริธึมการเรียงบับเบิ้ล

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

• int i, j;

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

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

  • ถ้า arr[i]>arr[j] สลับ arr[i] กับ arr[j]

• สิ้นสุด

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

• หากความยาวอาร์เรย์เป็น 1 ให้ส่งคืน

• ข้ามอาร์เรย์หนึ่งครั้งและแก้ไของค์ประกอบที่ใหญ่ที่สุดที่ส่วนท้าย

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

ตัวอย่าง

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

ผลผลิต − เรียงลำดับอาร์เรย์:1 2 3 4 5 7

คำอธิบาย −

รอบแรก5 7 2 3 1 4 → สลับ → 5 2 7 3 1 45 2 7 3 1 4 → สลับ → 5 2 3 7 1 45 2 3 7 1 4 → สลับ → 5 2 3 1 7 45 2 3 1 7 4 → สลับ → 5 2 3 1 4 7 วินาทีผ่าน5 2 3 1 4 7 → สลับ → 2 5 3 1 4 72 5 3 1 4 7 → สลับ → 2 3 5 1 4 72 3 5 1 4 7 → สลับ → 2 3 1 5 4 72 3 1 5 4 7 → สลับ → 2 3 1 4 5 7 รอบที่สาม2 3 1 4 5 7 → สลับ → 2 1 3 4 5 72 1 3 4 5 7 ไม่สลับสี่รอบ 2 1 3 4 5 7 → สลับ → 1 2 3 4 5 71 2 3 4 5 7 ไม่มีการแลกเปลี่ยนในการทำซ้ำเพิ่มเติม

ป้อนข้อมูล − Arr[] ={ 1, 2, 3, 3, 2 };

ผลผลิต − เรียงลำดับอาร์เรย์:1 2 2 3 3

คำอธิบาย −

First Pass1 2 3 3 2 → swap → 1 2 3 2 31 2 3 2 3 → swap → 1 2 2 3 31 2 2 3 3 ไม่มีการสลับในการวนซ้ำเพิ่มเติม Pass ที่สอง 1 2 2 3 3 ไม่มีการสลับในการทำซ้ำเพิ่มเติม 
แนวทางที่ใช้ในโปรแกรมด้านล่างมีดังนี้
 

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

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

 ฟังก์ชัน recurbublSort(int arr[], int len) ใช้อาร์เรย์และความยาวของอาร์เรย์ และจัดเรียงอาร์เรย์แบบเรียกซ้ำโดยใช้การเรียงลำดับแบบฟอง
 
 
 

 ใช้อุณหภูมิแปรผัน
 
 
 

 หากความยาวอาร์เรย์เป็น 1 ให้คืนค่าเป็นโมฆะ
 
 
 

 อย่างอื่นสำรวจอาร์เรย์โดยใช้ single for loop และสำหรับแต่ละองค์ประกอบ arr[i]>arr[i+1] ให้สลับองค์ประกอบเหล่านั้น
 
 
 

 ตั้งค่า temp=arr[i], arr[i]=arr[i+1] และ arr[i+1]=temp.
 
 
 

 ตอนนี้ลดความยาวลง 1 เนื่องจากลูปก่อนหน้าวางองค์ประกอบที่ใหญ่ที่สุดที่ตำแหน่งสุดท้าย
 
 
 

 โทรซ้ำเพื่อ recurbublSort(arr,len)
 
 
 

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

 พิมพ์อาร์เรย์ที่เรียงลำดับภายใน main.
 
 
 
ตัวอย่าง
 
#include void recurbublSort(int arr[], int len){ int temp; ถ้า (len ==1){ return; } for (int i=0; i arr[i+1]){ temp=arr[i]; arr[i]=arr[i+1]; arr[i+1]=อุณหภูมิ; } } len=len-1; recurbublSort(arr, len);}int main(){ int Arr[] ={21, 34, 20, 31, 78, 43, 66}; ความยาว int =sizeof(Arr)/sizeof(Arr[0]); recurbublSort(อวน, ความยาว); printf("เรียงอาร์เรย์ :"); สำหรับ(int i=0;i<ความยาว;i++){ printf("%d ",Arr[i]); } return 0;}
 
ผลลัพธ์
 

 หากเรารันโค้ดด้านบน มันจะสร้างผลลัพธ์ต่อไปนี้
 
เรียงลำดับอาร์เรย์:20 21 31 34 43 66 78