บ้านช่วยเหลือรายชื่อสมาชิกกลุ่มผู้ใช้สมัครสมาชิก(Register)เข้าสู่ระบบ(Log in)

Share | 
 

 INSERTION SORT

อ่านหัวข้อก่อนหน้า อ่านหัวข้อถัดไป Go down 
ผู้ตั้งข้อความ
Angel-beats
ﻬ௫ﻬAdminﻬ௫ﻬ
ﻬ௫ﻬAdminﻬ௫ﻬ
avatar

ชื่อในเกม : Novas
ค่าขยัน : 35
ค่าขนม : -2196
คะแนน : 0

ตั้งหัวข้อเรื่อง: INSERTION SORT   25/7/2012, 19:14

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]
ขึ้นไปข้างบน Go down
ดูข้อมูลส่วนตัว http://virgin.wow3.info
Angel-beats
ﻬ௫ﻬAdminﻬ௫ﻬ
ﻬ௫ﻬAdminﻬ௫ﻬ
avatar

ชื่อในเกม : Novas
ค่าขยัน : 35
ค่าขนม : -2196
คะแนน : 0

ตั้งหัวข้อเรื่อง: ทำได้แล้ว   29/7/2012, 22:57

#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;
}
}
ขึ้นไปข้างบน Go down
ดูข้อมูลส่วนตัว http://virgin.wow3.info
 
INSERTION SORT
อ่านหัวข้อก่อนหน้า อ่านหัวข้อถัดไป ขึ้นไปข้างบน 
หน้า 1 จาก 1

Permissions in this forum:คุณไม่สามารถพิมพ์ตอบ
Vїяġїи Ĝϋί£Ð :: General Zone :: Dev C++-
ไปที่: