การเรียงลำดับการแทรกคืออัลกอริธึมการจัดเรียงซึ่งเป็น อัลกอริธึมที่ใช้การเปรียบเทียบแบบแทนที่ตำแหน่ง
อัลกอริธึมทำงานโดยวางองค์ประกอบในตำแหน่งของพวกเขาในอาร์เรย์ย่อยที่จัดเรียง เช่น อาร์เรย์ย่อยที่อยู่ข้างหน้าองค์ประกอบซึ่งเป็นอาร์เรย์ย่อยที่จัดเรียง
อัลกอริทึม
ขั้นที่ 1 − วนจาก 1 ถึง n-1 และทำ -
Step2.1 - เลือกองค์ประกอบที่ตำแหน่ง i, array[i].
Step2.2 - แทรกองค์ประกอบในตำแหน่งของอาร์เรย์ย่อยที่เรียงลำดับ[0] ไปยัง arr[i].
มาดูตัวอย่างเพื่อทำความเข้าใจอัลกอริทึมกัน
อาร์เรย์ =[34, 7, 12, 90, 51]
สำหรับฉัน =1, arr[1] =7, วางในตำแหน่งของ subarray arr[0] - arr[1].
[7, 34, 12, 90, 51]
สำหรับผม =2 , arr[2] =12, วางในตำแหน่งใน subarray arr[0] - arr[2].
[7, 12, 34, 90, 51]
สำหรับผม =3 , arr[3] =90, วางในตำแหน่งใน subarray arr[0] - arr[3].
[7, 12, 34, 90, 51]
สำหรับฉัน =4, arr[4] =51, วางในตำแหน่งของ subarray arr[0] - arr[4].
[7, 12, 34, 54, 90]
ที่นี่เราจะดูว่าการเรียงลำดับการแทรกแบบเรียกซ้ำทำงานอย่างไร มันทำงานบนพื้นฐานย้อนกลับ กล่าวคือ เราจะเรียกฟังก์ชัน recursiveInsertionSort() แบบเรียกซ้ำ สำหรับการจัดเรียงอาร์เรย์องค์ประกอบ n-1 เมื่อเทียบกับการวนซ้ำปัจจุบัน จากนั้นในอาร์เรย์ที่จัดเรียงนี้ซึ่งฟังก์ชันจะส่งคืน เราจะแทรกองค์ประกอบที่ n ที่ตำแหน่งเช่นเดียวกับในอาร์เรย์ที่จัดเรียง
โปรแกรมสำหรับการเรียงลำดับการแทรกแบบเรียกซ้ำ -
ตัวอย่าง
#include <stdio.h>
void recursiveInsertionSort(int arr[], int n){
if (n <= 1)
return;
recursiveInsertionSort( arr, n-1 );
int nth = arr[n-1];
int j = n-2;
while (j >= 0 && arr[j] > nth){
arr[j+1] = arr[j];
j--;
}
arr[j+1] = nth;
}
int main(){
int array[] = {34, 7, 12, 90, 51};
int n = sizeof(array)/sizeof(array[0]);
printf("Unsorted Array:\t");
for (int i=0; i < n; i++)
printf("%d ",array[i]);
recursiveInsertionSort(array, n);
printf("\nSorted Array:\t");
for (int i=0; i < n; i++)
printf("%d ",array[i]);
return 0;
} ผลลัพธ์
Unsorted Array: 34 7 12 90 51 Sorted Array: 7 12 34 51 90
