Insertion Sort เป็นอัลกอริทึมการจัดเรียงที่เป็น in-place comparison-based algorithm
อัลกอริทึมนี้ทำงานโดยการวางองค์ประกอบในตำแหน่งที่ถูกต้องในสับอาร์เรย์ที่จัดเรียงแล้ว คือ สับอาร์เรย์ก่อนหน้าองค์ประกอบที่เป็นสับอาร์เรย์ที่จัดเรียงแล้ว
อัลกอริทึม
ขั้นตอนที่ 1 − วนลูปจาก 1 ถึง n-1 และทำดังนี้
ขั้นตอนที่ 2.1 − เลือกองค์ประกอบที่ตำแหน่ง i คือ array[i]
ขั้นตอนที่ 2.2 − แทรกองค์ประกอบในตำแหน่งของมันในสับอาร์เรย์ที่จัดเรียงแล้ว array[0] ถึง arr[i]
มาดูตัวอย่างเพื่อเข้าใจอัลกอริทึม
อาร์เรย์ = [34, 7, 12, 90, 51]
สำหรับ i = 1, arr[1] = 7, วางในตำแหน่งของมันในสับอาร์เรย์ arr[0] - arr[1]
[7, 34, 12, 90, 51]
สำหรับ i = 2, arr[2] = 12, วางในตำแหน่งของมันในสับอาร์เรย์ arr[0] - arr[2]
[7, 12, 34, 90, 51]
สำหรับ i = 3, arr[3] = 90, วางในตำแหน่งของมันในสับอาร์เรย์ arr[0] - arr[3]
[7, 12, 34, 90, 51]
สำหรับ i = 4, arr[4] = 51, วางในตำแหน่งของมันในสับอาร์เรย์ arr[0] - arr[4]
[7, 12, 34, 54, 90]
ที่นี่ เราจะดูว่า Recursive Insertion Sort ทำงานอย่างไร มันทำงานแบบย้อนกลับ คือ เราจะเรียกฟังก์ชัน recursiveInsertionSort() แบบเรียกซ้ำเพื่อจัดเรียงอาร์เรย์ n-1 องค์ประกอบเทียบกับการวนรอบปัจจุบัน จากนั้นในอาร์เรย์ที่จัดเรียงแล้วซึ่งจะถูกคืนค่ากลับโดยฟังก์ชัน เราจะแทรกองค์ประกอบที่ n ไว้ที่ตำแหน่งของมันในอาร์เรย์ที่จัดเรียงแล้ว
โปรแกรมสำหรับ Recursive Insertion Sort −
ตัวอย่าง
#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
