อธิบายเทคนิคการเรียงลำดับในภาษาซี

ปัญหา

เทคนิคการเรียงลำดับต่างๆ ในภาษาซีมีอะไรบ้าง? อธิบายเทคนิคการจัดเรียงแบบใดแบบหนึ่งพร้อมตัวอย่าง

วิธีแก้ปัญหา

ภาษา C มีเทคนิคการเรียงลำดับห้าแบบ ซึ่งมีดังนี้ -

• การเรียงลำดับฟอง (หรือ) การเรียงลำดับการแลกเปลี่ยน
• การเรียงลำดับการเลือก
• การเรียงลำดับการแทรก (หรือ) การเรียงลำดับเชิงเส้น
• การเรียงลำดับด่วน (หรือ) การเรียงลำดับการแลกเปลี่ยนพาร์ติชั่น
• ผสานการเรียงลำดับ (หรือ) การเรียงลำดับภายนอก

การเรียงบับเบิ้ล

เป็นเทคนิคการเรียงลำดับที่ง่ายที่สุดซึ่งเรียกอีกอย่างว่าการเรียงลำดับการแลกเปลี่ยน

ขั้นตอน

• เปรียบเทียบองค์ประกอบแรกกับองค์ประกอบที่เหลือในรายการและแลกเปลี่ยน (สลับ) หากไม่ได้เรียงตามลำดับ

• ทำเช่นเดียวกันกับองค์ประกอบอื่นๆ ในรายการจนกว่าองค์ประกอบทั้งหมดจะถูกจัดเรียง

30 50 40 10 20

พิจารณาองค์ประกอบที่ให้ไว้ด้านล่าง −

รอบแรก

เปรียบเทียบองค์ประกอบแรกกับองค์ประกอบที่เหลือ

a[0]> a[1] $\square$ $\square$30>50 (F) $\square$ $\square$ไม่มีการแลกเปลี่ยน

a[0]> a[2] $\square$ $\square$ 30>40 (F) $\square$ $\square$ ไม่มีการแลกเปลี่ยน

a[0]> a[3] $\square$ $\square$ 30>10 (T) $\square$ $\square$ exchange

a[0]> a[4] $\square$ $\square$ 10>20 (F) $\square$ $\square$ ไม่มีการแลกเปลี่ยน

10 50 40 30 20

รอบสอง

เปรียบเทียบองค์ประกอบที่สองกับองค์ประกอบที่เหลือ

a[1]> a[2] $\square$ $\square$ 50>40 (T) $\square$ $\square$ exchange

a[1]> a[3] $\square$ $\square$ 40>30 (T) $\square$ $\square$ exchange

a[1]> a[4] $\square$ $\square$ 30>20 (T) $\square$ $\square$ exchange

10 20 50 40 30

รอบที่สาม

เปรียบเทียบองค์ประกอบที่สามกับองค์ประกอบที่เหลือ

a[2]> a[3] $\square$ $\square$ 50>40 (T) $\square$ $\square$ exchange

a[2]> a[4] $\square$ $\square$ 40>30 (T) $\square$ $\square$ exchange

10 20 30 50 40

รอบที่สี่

เปรียบเทียบองค์ประกอบที่สี่กับองค์ประกอบที่เหลือ

a[3]> a[4] $\square$ $\square$ 50>40 (T) $\square$ $\square$ exchange

10 20 30 40 50

ขั้นตอน

อ้างถึงขั้นตอนการเรียงลำดับฟองตามที่ระบุด้านล่าง -

for (i=0; i<n-1; i++){
   for (j=i+1; j<n; j++){
      if (a[i] > a[j]){
         t=a[i];
         a[i] = a[j];
         a[j] = t;
      }
   }
}

ตัวอย่าง

ต่อไปนี้เป็นโปรแกรม C สำหรับเทคนิคการเรียงลำดับฟอง -

#include<stdio.h>
int main(){
   int a[50], i,j,n,t;
   printf("enter the No: of elements in the list:\n");
   scanf("%d", &n);
   printf("enter the elements:\n");
   for(i=0; i<n; i++){
      scanf ("%d", &a[i]);
   }
   printf("Before bubble sorting the elements are:\n");
   for(i=0; i<n; i++)
      printf("%d \t\n", a[i]);
   for (i=0; i<n-1; i++){
      for (j=i+1; j<n; j++){
         if (a[i] > a[j]){
            t = a[i];
            a[i] = a[j];
            a[j] = t;
         }
      }
   }
   printf ("after bubble sorting the elements are:\n");
   for (i=0; i<n; i++)
      printf("%d\t", a[i]);
   return 0;
}

ผลลัพธ์

เมื่อโปรแกรมข้างต้นทำงาน มันจะให้ผลลัพธ์ดังต่อไปนี้ −

enter the No: of elements in the list:
5
enter the elements:
12 11 45 26 67
Before bubble sorting the elements are:
12
11
45
26
67
after bubble sorting the elements are:
11 12 26 45 67