Insertion Sort

การจัดเรียงข้อมูล (Sorting)

         ในชีวิตประจำวันเรามีการจัดเรียงข้อมูลต่างๆ อย่างมากมายหลายแบบ เช่นการจัดเรียงตัวอักษรในพจนานุกรรม การจัดเรียงหรัสของนักศึกษา การจัดเรียงคะแนนสอบของนักศึกษาที่สอบได้คะแนนมากที่สุด          เหตุที่ต้องมีการจัดเรียงข้อมูล ก็เพราะว่าจะทำให้ง่ายต่อการค้นหาและการตีความ ในคอมพิวเตอร์ก็เช่นเดียวกัน ถ้าหากมีข้อมูลมากๆ แล้วไม่ทำการเรียงข้อมูล อาจทำให้เสียเวลาในการค้นหาข้อมูลนั้นเป็นอย่างมาก จึงนิยมที่จะทำการเรียงข้อมูลก่อนที่จะนำข้อมูลนั้นมาใช้ เพื่อจะได้สะดวกต่อการดึงข้อมูลนั้นมาใช้ และ สะดวกในการเขียนโปรแกรม 
       
     วัตถุประสงค์
         1. เพื่อให้ทราบถึงการเรียงลำดับข้อมูลแบบ INSERTION SORT                 

          2. สามารถเขียนและอธิบายโปรแกรมภาษาซีได้

   การจัดเรียงลำดับ (Sorting) หมายถึง การจัดเรียงข้อมูลให้เรียงลำดับตามเงื่อนไขที่กำหนดไว้ โดยอาจเรียงจากน้อยไปมาก หรือค่ามากไปน้อยก็ได้ การเรียงลำดับข้อมูลในระบบคอมพิวเตอร์ จะแบ่งเป็น 2 ลักษณะใหญ่ ๆ คือ

1.  การเรียงลำดับข้อมูลภายใน (Internal sorting)

- ใช้กับข้อมูลที่มีจำนวนไม่ใหญ่กว่าเนื้อที่ในหน่วยความจำ (main memory)

- ไม่ต้องใช้หน่วยความจำสำรอง เช่น ดิสก์, เทป เป็นต้น

2.  การเรียงลำดับข้อมูลภายนอก (External sorting)

- ใช้กับข้อมูลที่มีจำนวนใหญ่เกินกว่าที่จะเก็บลงในหน่วยความจำได้หมดภายในครั้งเดียว
- จะใช้หน่วยความจำภายนอก เช่น  ดิสก์, เทป สำหรับเก็บข้อมูลบางส่วนที่ได้รับการเรียงลำดับข้อมูลแล้ว แล้วจึงค่อยจัดการเรียงลำดับข้อมูลในส่วนต่อไป


Insertion Sort
       
 การจัดเรียงแบบแทรก คือ การเรียงข้อมูลโดยนำข้อมูลที่จะทำการจัดเรียงนั้นๆ ไปจัดเรียงทีละตัว โดยการแทรกตัวที่จะเรียงไว้ในตำแหน่งที่เหมาะสมของข้อมูลที่มีการจัดเรียงเรียบร้อยแล้ว ณ ตำแหน่งที่ถูกต้อง

ขั้นตอน

- เปรียบเทียบค่ากับตำแหน่งถัดไปแทน

- สลับตำแหน่งให้อยู่ในตำแหน่งที่เหมาะสม

Write Program Insertion Sort

Output:

Enter total elements: 5

Enter 5 elements: 3 7 9 0 2

After sorting:  0 2 3 7 9

#include<stdio.h>

main(){

  int i,j,s,temp,a[20];

  printf("Enter total elements: ");

  scanf("%d",&s);

  printf("Enter %d elements: ",s);

  for(i=0;i<s;i++)

      scanf("%d",&a[i]);

  for(i=1;i<s;i++){

      temp=a[i];

      j=i-1;

      while((temp<a[j])&&(j>=0)){

      a[j+1]=a[j];

          j=j-1;

      }

      a[j+1]=temp;

  }

  printf("After sorting: ");

  for(i=0;i<s;i++)

      printf(" %d",a[i]);

  return 0;

}

โดย

อาจารย์ เอกราช เจริญผล

วิทยาลัยเทคโนโลยีพณิชยการราชดำเนิน