โปรแกรม C สำหรับการเรียงลำดับฟอง: การเรียงลำดับฟองในC

บทนำ

การจัดเรียงอาร์เรย์มีความสำคัญอย่างมากในด้านวิทยาการคอมพิวเตอร์ ยูทิลิตี้จะสังเกตเห็นเมื่อจำเป็นต้องจัดเรียงข้อมูลตามลำดับเฉพาะ มีอัลกอริธึมการเรียงลำดับประเภทต่างๆ อัลกอริธึมการเรียงลำดับที่ใช้กันทั่วไปและแพร่หลายที่สุดคือ Bubble Sort

เรียงบับเบิ้ลในภาษา C

เทคนิคที่ใช้ในการจัดเรียงแบบ Bubble sort นั้นง่ายและเข้าใจง่าย ทั้งหมดที่ทำได้คือเปรียบเทียบองค์ประกอบปัจจุบันกับองค์ประกอบถัดไปและสลับกันหากองค์ประกอบนั้นมากหรือน้อยกว่าตามที่กำหนดโดยเงื่อนไข อัลกอริทึมมีความแม่นยำมาก ทุกครั้งที่มีการเปรียบเทียบองค์ประกอบกับองค์ประกอบอื่น ๆ จนกว่าจะพบตำแหน่งจะเรียกว่าผ่าน

อัลกอริธึมนี้เปรียบได้กับฟองสบู่ในน้ำเนื่องจากกรองฟองอากาศที่มีลักษณะคล้ายอาร์เรย์ ในบรรดาอัลกอริธึมที่ใช้สำหรับการเรียงลำดับ Bubble sort เป็นวิธีที่ง่ายที่สุดและช้าที่สุดด้วยความซับซ้อนของเวลาของ O(n^2) อย่างไรก็ตาม อัลกอริทึมสามารถปรับให้เหมาะสมได้โดยใช้ตัวแปรแฟล็กที่ออกจากลูปเมื่อการแลกเปลี่ยนเสร็จสิ้น กรณีที่ดีที่สุดสำหรับการจัดเรียงแบบบับเบิ้ลอาจเป็น O(n) เมื่ออาร์เรย์ถูกจัดเรียง

ตัวอย่างเช่น ให้เราหาอาร์เรย์ของตัวเลขห้าตัวที่ไม่เรียงลำดับตามที่ระบุด้านล่าง

13, 32,26, 34,9

การเรียงลำดับบับเบิ้ลจะเริ่มพิจารณาสององค์ประกอบแรก และมันจะเปรียบเทียบเพื่อตรวจสอบว่าองค์ประกอบใดมีค่ามากกว่า ในกรณีนี้ 32 มากกว่า 13 ดังนั้นส่วนนี้จึงถูกจัดเรียงแล้ว ต่อไป เราเปรียบเทียบ 32 กับ 26 เราจึงพบว่า 32 มากกว่า 26 ดังนั้นจึงต้องสลับกัน อาร์เรย์ใหม่จะมีลักษณะดังนี้

13, 26, 32,34,9

ต่อไป เราเปรียบเทียบ 32 กับ 34 เรารู้ว่าพวกมันถูกจัดเรียงแล้ว ดังนั้นเราจึงย้ายไปยังตัวแปรสองตัวสุดท้าย 34 และ 9 เนื่องจาก 34 มากกว่า 9 จึงต้องสลับกัน

เราสลับค่าและมาที่จุดสิ้นสุดของอาร์เรย์หลังจากการวนซ้ำครั้งแรก ตอนนี้อาร์เรย์จะมีลักษณะดังนี้

13, 26. 32,9,34

หลังจากการวนซ้ำครั้งที่สอง อาร์เรย์จะมีลักษณะดังนี้

13, 26, 9,32,34

หลังจากการวนซ้ำครั้งที่สาม อาร์เรย์จะกลายเป็น

13,9,26,32,34

หลังจากการวนซ้ำครั้งที่สี่ อาร์เรย์จะถูกจัดเรียงอย่างสมบูรณ์

9, 13,26,32,34

ต้องอ่าน: แนวคิดโครงการในC

อัลกอริทึม

สมมติว่าอาร์เรย์มีองค์ประกอบ n รายการ นอกจากนี้ เราคิดว่าฟังก์ชันค่าแลกเปลี่ยนกำลังสลับค่าทั้งหมดเพื่อให้หมายเลขอาร์เรย์เรียงตามลำดับ

เริ่ม BubbleSort (อาร์เรย์)

สำหรับองค์ประกอบทั้งหมดของรายการ

ถ้าอาร์เรย์[i]>อาร์เรย์[i+1]

ค่าการแลกเปลี่ยน(array[i], array[i+1] )

สิ้นสุด if

จบเพื่อ

กลับอาร์เรย์

จบการเรียงลำดับฟอง

อ่าน: การเรียงลำดับในโครงสร้างข้อมูล: หมวดหมู่ & ประเภท

รหัสเทียม

เห็นได้ชัดในอัลกอริธึมข้างต้นว่ามีการเปรียบเทียบระหว่างแต่ละคู่ขององค์ประกอบอาร์เรย์จนกว่าอาร์เรย์ทั้งหมดจะถูกเรียงลำดับจากน้อยไปมาก อาจส่งผลให้เกิดปัญหาความซับซ้อนบางประการ เช่น ผลลัพธ์ของอัลกอริทึมเมื่อจัดเรียงอาร์เรย์แล้วในลำดับจากน้อยไปมาก ในการทำให้ปัญหาคลี่คลายลง เราจะใช้ตัวแปรแฟล็กตัวเดียว ซึ่งช่วยให้เราดูว่ามีการสลับกันหรือไม่ หากไม่ต้องการสลับกันอีก เราจะออกจากวงใน

pseudocode สำหรับอัลกอริธึม BubbleSort สามารถเขียนได้ดังนี้

ขั้นตอน BubbleSort (อาร์เรย์: รายการในอาร์เรย์)

วนซ้ำ = array.count;

สำหรับ k=0 เพื่อวนซ้ำ -1 ทำ:

ธง=เท็จ

สำหรับ l=0 เพื่อวนซ้ำ -1 ทำ:

ถ้า (array[l]> array[l+1]) แล้ว

ค่าแลกเปลี่ยน(array[l], array [l+1])

ธง=จริง

สิ้นสุด if

จบเพื่อ

ถ้า (ไม่เปลี่ยน) แล้ว

หยุดพัก

สิ้นสุด if

สิ้นสุดเพื่อ

สิ้นสุดโพรซีเดอร์ส่งคืนอาร์เรย์

ให้เราลองใช้โปรแกรมตัวอย่างของการ จัดเรียงแบบฟองใน C :

# รวม<stdio.h>

โมฆะหลัก

{

int array [10], i, j, num

สำหรับ (i=0; i<=9; i++)

{

scanf(“%d”, &array[i])

}

สำหรับ(i=0;i<=9;i++)

{

สำหรับ(j=0;j<=9-i;j++)

{

if(array[j]>array[j+1])

{

num= อาร์เรย์[j];

อาร์เรย์[j]=อาร์เรย์[j+1];

อาร์เรย์[j+1]=จำนวน;

}

}

}

printf(“อาร์เรย์ที่เรียงลำดับคือ /n”);

สำหรับ(i=0;i<=9;i++)

{

printf(“%d ”,&array[i])

}

}

ตามที่แสดงในตัวอย่าง อัลกอริธึมการจัดเรียงแบบฟองนี้รับตัวเลข 10 ตัวจากผู้ใช้และจัดเก็บไว้ในอาร์เรย์ ในส่วนถัดไป มีสองลูป วงรอบนอกทำงานสำหรับค่า I เท่ากับศูนย์ถึงน้อยกว่าเท่ากับเก้า หน้าที่ของวงรอบนอกคือดูแลองค์ประกอบทั้งหมดของค่าที่ต้องเปรียบเทียบกับองค์ประกอบอื่น

มีอีกวงหนึ่งอยู่ในวงนอก เริ่มต้นจาก j=0 และวิ่งจนกว่าจะน้อยกว่าหรือเท่ากับแปด ข้างในมีเงื่อนไข if คำสั่งที่เปรียบเทียบและตรวจสอบว่า array[j] มากกว่าอาร์เรย์ [j+1] หากเงื่อนไขเป็นไปตามเงื่อนไข ค่าของ array[j] และ array [j+1] จะถูกสลับกัน

ตัวแปรตามชื่อ num ใช้เพื่อจุดประสงค์นี้ array[j] แรกถูกกำหนดให้กับ num จากนั้น array[j+1] ถูกกำหนดให้กับ array[j] และสุดท้าย num ถูกกำหนดให้กับ array[j+1] กระบวนการนี้จะดำเนินต่อไปจนกว่าองค์ประกอบทั้งหมดในอาร์เรย์จะถูกจัดเรียงตามลำดับที่เพิ่มขึ้น หลังจากนั้นจะพิมพ์อาร์เรย์ที่เรียงลำดับ

การใช้งาน Bubble Sort อย่างเหมาะสมที่สุด

เรามีอัลกอริธึมที่ปรับให้เหมาะสมที่สุดสำหรับการเรียงลำดับแบบบับเบิลเพื่อปรับปรุงผลลัพธ์ การใช้ตัวแปรแฟล็กเป็นการเพิ่มประสิทธิภาพ ตัวแปรแฟล็กจะถือ 1 หากมีการแลกเปลี่ยนอย่างอื่นจะแยกออกจากลูป ด้านล่างนี้คือ โปรแกรมจัดเรียงบับเบิ้ลที่ปรับให้เหมาะสมใน C

#include<stdio.h>

โมฆะหลัก

{

int array [10], i, j, num, flag=0;

สำหรับ (i=0; i<=9; i++)

{

scanf(“%d”, &array[i])

}

สำหรับ(i=0;i<=9;i++)

{

สำหรับ(j=0;j<=9-i;j++)

{

if(array[j]>array[j+1])

{

num= อาร์เรย์[j];

อาร์เรย์[j]=อาร์เรย์[j+1];

อาร์เรย์[j+1]=จำนวน;

ธง=1;

}

if(! แฟล็ก)

{

หยุดพัก;

}

}

}

printf(“อาร์เรย์ที่เรียงลำดับคือ /n”);

สำหรับ(i=0;i<=9;i++)

{

printf(“%d ”,&array[i])

}

}

โปรแกรมที่กำหนดทำงานในลักษณะที่คล้ายกับโปรแกรมเรียงลำดับแบบฟองปกติ การเปลี่ยนแปลงเพียงอย่างเดียวคือการใช้ตัวแปรแฟล็ก เริ่มแรก แฟล็กถูกตั้งค่าเป็น 0 อย่างไรก็ตาม หากมีการแลกเปลี่ยนเกิดขึ้น แฟล็กจะกลายเป็น 1 ซึ่งหมายความว่าอาร์เรย์ยังต้องการการตรวจสอบอีกหนึ่งครั้ง ในทางกลับกัน ถ้าแฟล็กไม่ใช่ 1 หมายความว่าไม่มีการสลับสับเปลี่ยน เราจะออกจากวงใน สมมติว่าอาร์เรย์ได้รับการจัดเรียงแล้ว เมื่อดำเนินการแล้ว เราจะได้ผลลัพธ์เหมือนกับการเรียงลำดับบับเบิ้ลปกติ

ความซับซ้อนของเวลา

ความซับซ้อนของเวลากรณีที่ดีที่สุดสำหรับการเรียงลำดับแบบบับเบิ้ลคือ O(n) มันเกิดขึ้นเมื่ออาร์เรย์ถูกจัดเรียงแล้ว กรณีที่เลวร้ายที่สุดคือ O(n*n) เมื่อไม่ได้จัดเรียงอาร์เรย์

อ่าน: โปรแกรมรูปแบบ 12 อันดับแรกใน Java ที่คุณควรชำระเงินวันนี้

อะไรต่อไป?

หากคุณสนใจที่จะเรียนรู้เพิ่มเติมเกี่ยวกับ Java การพัฒนาซอฟต์แวร์แบบฟูลสแตก โปรดดูประกาศนียบัตร PG ของ upGrad & IIIT-B ด้านการพัฒนาซอฟต์แวร์แบบครบวงจร ซึ่งออกแบบมาสำหรับมืออาชีพที่ทำงานและมีการฝึกอบรมที่เข้มงวดมากกว่า 500 ชั่วโมง โครงการมากกว่า 9 โครงการ และการมอบหมายงาน สถานะศิษย์เก่า IIIT-B โครงการหลักและความช่วยเหลือด้านงานกับบริษัทชั้นนำ