INSERTION SORT

INSERTION SORT

วิธีนี้ต้องใช้พื้นที่ความจำเพิ่มขึ้นอีก N ตำแหน่งสำหรับเก็บส่วนที่เรียงแล้ว นั่นคือถ้าเรามีลิสต์ A(1 : N) ที่ยังไม่ได้เรียง เราต้องใช้ลิสต์ B(1 : N) มาช่วย โดยที่เราจะดึงแต่ละค่าในลิสต์ A ไปใส่ในตำแหน่งสัมพันธ์ที่ถูกต้องในลิสต์ B ในที่สุดลิสต์ B จะเป็นลิสต์ที่มีค่าต่าง ๆ เรียงกันตามลำดับ

อย่างไรก็ดี เราก็มีวิธีที่จะ sort - in - place นั่นคือใช้พื้นที่ความจำเพียง N ตำแหน่งเท่านั้นโดยไม่ต้องใช้พื้นที่ความจำเพิ่ม วิธีนี้เราจะนำตัวที่ I จากส่วนที่ยังไม่ได้เรียงใส่เข้าไปในส่วนที่เรียงแล้ว ซึ่งมี J ตัว

สมมติให้ชุดตัวเลขที่เรียงเป็น 5,4,2,8,8,9,6 การเรียงจะมีลำดับดังนี้

[Only admins are allowed to see this image]


*เครดิต [Only admins are allowed to see this link]



ขั้นตอนวิธี Insertion sort
Insertion sort เป็นวิธีการจัดเรียงข้อมูลที่เหมาะกับข้อมูลขนาดเล็ก เรากำหนดการเรียกใช้ ขั้นตอนวิธีดังนี้ INSERTION-SORT(A) เมื่อ A เป็น array
ข้อมูลเข้า A[1..n]
ข้อมูลออก การจัดเรียงของข้อมูลจำนวน n ตัวใน A โดยที่ A[1] A[2] A[3] . . . A[n] (sorted in place)
INSERTION-SORT(A)

1. for j = 2 to length[A]
2. (key, i) = (A[j], j-1)
3. while i > 0 and A[i] > key
4. (A[i+1], i) = (A[i], i-1)
5. endwhile
6. A[i+1] = key
7. endfor

*เครดิต [Only admins are allowed to see this link]

#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
void insersort(int *,int );
int main()
{
printf("********************\n* -insertion sort- *\n********************\n");
int i,n,*a;
printf("\nThe scope of the data.\n -> Enter the number of rows : ");
scanf("%d",&n);
a=(int*)malloc(n*2);
printf("\n Enter the number \n ");
for(i=1;i<=n;i++)
{
scanf("%d",a+i);printf(" ");
}
insersort(&a[0],n);
printf("\n\n Row in sorted order is:\n ");
for(i=1;i<=n;i++)
{
printf("%d",*(a+i));printf(" \n ");
}
getch();
}
void insersort(int *b, int s)
{
int i,j,tmp;
for(i=1;i<=s;i++)
{
tmp=*(b+i);
for(j=i-1;j>0&&tmp<*(b+j);j--)
*(b+j+1)=*(b+j);
*(b+j+1)=tmp;
}
}