การเรียงลำดับการแทรกเป็นหนึ่งในอัลกอริธึมการเรียงลำดับที่ใช้ในการจัดเรียงข้อมูลโดยการแทรกองค์ประกอบต่างๆ เช่น สำรับไพ่ องค์ประกอบทั้งหมดถูกจัดเรียงจากซ้ายไปขวา จากนั้นพิจารณาองค์ประกอบแรกตามที่จัดเรียงแล้ว แทรกส่วนที่เหลือลงในรายการที่จัดเรียงทางด้านซ้าย แต่ละองค์ประกอบจะถูกเปรียบเทียบกับแต่ละองค์ประกอบในรายการด้านซ้ายจนกว่าจะถูกแทรกในตำแหน่งที่ถูกต้อง
อัลกอริทึมการเรียงลำดับการแทรก
-
int arr[5]={ 5,4,2,1,3 };
-
int i, j;
-
ข้ามจากดัชนี j=i+1 ถึง j<ขนาดอาร์เรย์
-
สำหรับแต่ละองค์ประกอบ arr[j] เปรียบเทียบกับองค์ประกอบในรายการ arr[0 ถึง i] จนกระทั่งพบองค์ประกอบดังกล่าว arr[i]
-
วาง arr[j] ในรายการและย้ายองค์ประกอบที่ใหญ่กว่าทั้งหมดไปทางขวาหนึ่งตำแหน่ง
-
สิ้นสุด
การเรียงลำดับการแทรกแบบเรียกซ้ำ
-
หากความยาวอาร์เรย์เป็น 1 ให้ส่งคืน
-
จัดเรียงองค์ประกอบซ้ำที่ดัชนี 0 ถึงขนาดอาร์เรย์ -1
-
แทรกองค์ประกอบสุดท้ายในอาร์เรย์ที่เรียงลำดับ
ตัวอย่าง
ป้อนข้อมูล − Arr[] ={ 5,7,2,3,1,4 }; ความยาว=6
ผลผลิต − เรียงลำดับอาร์เรย์:1 2 3 4 5 7
คำอธิบาย −
5 7 2 3 1 4 → 5 already sorted 5 7 2 3 1 4 → 7 at correct place 2 5 7 3 1 4 → 2 compared with 5,7 and inserted 2 3 5 7 1 4 → 3 compared with 5,7 and inserted 1 2 3 5 7 4 → 1 compared with 2,3,5,7 and inserted 1 2 3 4 5 7 → 4 compared with 5,7 and inserted
ป้อนข้อมูล − Arr[] ={ 1, 2, 3, 3, 2 };
ผลผลิต − เรียงลำดับอาร์เรย์:1 2 2 3 3
คำอธิบาย −
1, 2, 3, 3, 2 → 1 already sorted 1, 2, 3, 3, 2 → 2 at correct place 1, 2, 3, 3, 2 → 3 at correct place 1, 2, 3, 3, 2 → 3 at correct place 1, 2, 2, 3, 3 → 2 compared with 3,3 and inserted
แนวทางที่ใช้ในโปรแกรมด้านล่างมีดังนี้
ในแนวทางแบบเรียกซ้ำของการเรียงลำดับ 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 <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
