วิธีการเขียน Java Bubble Sort
เมื่อโปรแกรมเมอร์พูดถึงฟองสบู่ พวกเขาไม่ได้พูดถึงฟองน้ำที่คุณอาจเคยเป่ามาก่อนในชีวิต พวกเขากำลังพูดถึงอัลกอริธึมการเรียงลำดับที่ใช้ในการเรียงลำดับรายการ
ในคู่มือนี้ เราจะพูดถึงการจัดเรียงแบบฟองสบู่และวิธีการทำงาน เราจะใช้การเรียงลำดับแบบฟองต่อโดยใช้ Java เพื่อให้คุณเข้าใจว่าอัลกอริทึมนี้แปลเป็นโค้ดได้อย่างไร เพื่อไม่ให้เป็นการเสียเวลา มาดำดิ่งกับ Java bubble sort!
Java Bubble Sort คืออะไร
การเรียงลำดับแบบฟองคืออัลกอริธึมที่จัดเรียงค่าโดยการเปรียบเทียบองค์ประกอบที่อยู่ติดกันและสลับกันหากปรากฏในลำดับที่ไม่ถูกต้อง
กระบวนการนี้จะเกิดขึ้นซ้ำๆ จนกว่าทุกรายการในรายการจะได้รับการสั่งซื้ออย่างถูกต้อง การเรียงลำดับฟองสามารถใช้เพื่อเรียงลำดับรายการได้ทั้งจากน้อยไปมากหรือจากมากไปน้อย
การเรียงลำดับแบบบับเบิ้ลเป็นการเรียงลำดับครั้งแรกที่สอนในคลาสอัลกอริธึม เนื่องจากเข้าใจได้ง่ายกว่าการเรียงลำดับอื่นๆ เช่น การเรียงลำดับการแทรกหรือการเรียงลำดับการเลือก และให้การแนะนำที่ดีเกี่ยวกับอัลกอริธึมการเรียงลำดับ
การเรียงลำดับแบบบับเบิ้ลจะมีประสิทธิภาพสูงสุดเมื่อข้อมูลเกือบจะถูกจัดเรียงแล้ว อย่างไรก็ตาม หากข้อมูลของคุณไม่ได้ถูกจัดเรียงเลย การจัดเรียงประเภทอื่นอาจมีประสิทธิภาพมากกว่า
Bubble Sorts ทำงานอย่างไร
ก่อนที่เราจะเริ่มเขียนโค้ดสำหรับ Java Bubble sort เราต้องเข้าใจก่อนว่าอัลกอริธึมนี้ถูกนำไปใช้ในทางปฏิบัติอย่างไร
พิจารณารายการต่อไปนี้:
81% ของผู้เข้าร่วมกล่าวว่าพวกเขารู้สึกมั่นใจมากขึ้นเกี่ยวกับโอกาสในการทำงานด้านเทคโนโลยีหลังจากเข้าร่วม bootcamp จับคู่กับ Bootcamp วันนี้
ผู้สำเร็จการศึกษาจากหลักสูตร bootcamp โดยเฉลี่ยใช้เวลาน้อยกว่าหกเดือนในการเปลี่ยนอาชีพ ตั้งแต่เริ่มต้น bootcamp ไปจนถึงหางานแรก
| 5 | 9 | 2 | 7 |
การเรียงลำดับฟองของเราเริ่มต้นด้วยการเปรียบเทียบองค์ประกอบที่หนึ่งและที่สองในรายการของเรา
หากองค์ประกอบแรกมากกว่าองค์ประกอบที่สอง องค์ประกอบเหล่านี้จะสลับตำแหน่ง ในกรณีนี้ 5 ไม่เกิน 9 ดังนั้นองค์ประกอบจะคงอยู่ในตำแหน่งเดียวกัน
จากนั้น การเรียงลำดับของเราจะเปรียบเทียบสองรายการถัดไปในรายการของเรา 9 มากกว่า 2 ดังนั้นตัวเลขสองตัวนี้จึงสลับกัน:
| 5 | 2 | 9 | 7 |
กระบวนการนี้จะทำซ้ำจนกว่าจะมีการเปรียบเทียบทุกรายการในรายการ ในกรณีนี้ มีการเปรียบเทียบที่ต้องทำอีกอย่างหนึ่งคือ 9 มากกว่า 7 หรือไม่ 9 มากกว่า 7 ดังนั้นตัวเลขเหล่านี้จึงสลับกัน:
| 5 | 2 | 7 | 9 |
รายการของเราเกือบจะสั่งแล้ว เมื่อเปรียบเทียบทุกรายการแล้ว การเรียงลำดับฟองจะเริ่มใหม่อีกครั้งจนกว่าทุกองค์ประกอบจะถูกจัดเรียง
5 มากกว่า 2 ดังนั้นตัวเลขเหล่านี้จึงสลับกัน
| 2 | 5 | 7 | 9 |
รายการของเราได้รับการสั่งซื้ออย่างถูกต้องแล้ว การเรียงลำดับแบบฟองจะเปรียบเทียบตัวเลขไปเรื่อยๆ จนกว่าจะถึงจุดสิ้นสุดของรายการ จากนั้นจะหยุด นั่นคือทั้งหมดที่มีในการเรียงลำดับฟองสบู่ แน่นอนว่ามันเป็นอัลกอริธึมที่ใช้งานง่ายเมื่อคุณคุ้นเคยกับมันแล้ว
วิธีการเขียน Java Bubble Sort
การรู้ทฤษฎีเป็นสิ่งหนึ่ง แต่คุณมาที่นี่เพื่อเรียนรู้เกี่ยวกับการเรียงลำดับฟองสบู่ของ Java เรามาคุยกันถึงวิธีการใช้การเรียงลำดับแบบฟองสบู่ใน Java
การเรียงลำดับฟองมีสองประเภท:
- การจัดเรียงลูกโป่งมาตรฐาน
- การจัดเรียงฟองอากาศที่เหมาะสมที่สุด
การเรียงลำดับแบบฟองมาตรฐานทำให้การเปรียบเทียบที่เป็นไปได้ทั้งหมด แม้ว่าจะมีการเรียงลำดับอาร์เรย์ก็ตาม สิ่งนี้จะเพิ่มเวลาที่ใช้ในการเรียงลำดับฟอง ทำให้การเรียงลำดับมีประสิทธิภาพน้อยลง
การเรียงลำดับแบบฟองที่ปรับให้เหมาะสมจะติดตามว่ารายการถูกจัดเรียงโดยใช้ตัวแปรเพิ่มเติมหรือไม่ ซึ่งช่วยให้เราหยุดการจัดเรียงได้ทันทีที่รายการของเราได้รับการจัดเรียง
มาเริ่มด้วยการเขียนการเรียงแบบฟองสบู่มาตรฐานกัน
การเรียงลำดับบับเบิ้ลมาตรฐาน
ในการเริ่มต้น เราจะนำเข้าไลบรารี Arrays ลงในโค้ดของเรา เราจะใช้สิ่งนี้ในโค้ดของเราในภายหลังเพื่อพิมพ์รายการหมายเลขที่จัดเรียงไปยังคอนโซล:
import java.util.Arrays;
ตอนนี้หมดหนทางแล้ว เราสามารถเริ่มเขียนอัลกอริทึมของเราได้
เราจะเริ่มต้นด้วยการกำหนดคลาสที่เรียกว่า BubbleSort ซึ่งจัดเก็บโค้ดสำหรับโปรแกรม Java ของเรา และฟังก์ชันที่ดำเนินการจัดเรียงของเรา:
class BubbleSort {
void sortNumbers(int array[]) {
int size = array.length;
for (int item = 0; item < size - 1; item++) {
for (int j = 0; j < size - item - 1; j++) {
if (array[j] > array[j + 1]) {
int temporary = array[j];
array[j] = array[j + 1];
array[j + 1] = temporary;
}
}
}
}
}
เราได้ประกาศฟังก์ชันที่เรียกว่า sortNumbers ซึ่งรับตัวแปรเป็นพารามิเตอร์ ฟังก์ชันนี้เริ่มต้นด้วยการคำนวณขนาดของรายการตัวเลขที่เราระบุ
เมื่อคำนวณแล้ว ลูป for จะถูกเริ่มต้น วนรอบนี้เดินผ่านทุกรายการในอาร์เรย์ของเรา เราเริ่มต้นอีก for loop ซึ่งช่วยให้เราสามารถเปรียบเทียบแต่ละรายการในอาร์เรย์ได้
หากรายการทางด้านซ้ายของรายการมากกว่าตัวเลขทางด้านขวา ค่าจะถูกสลับ มิฉะนั้นจะไม่มีอะไรเกิดขึ้น
เราทำการแลกเปลี่ยนนี้โดยกำหนดค่าทางด้านซ้ายให้กับตัวแปรที่เรียกว่า "ชั่วคราว" เรากำหนดค่าทางด้านขวาของค่าที่อยู่ทางด้านซ้ายของการเปรียบเทียบ จากนั้น ค่าทางด้านซ้ายจะถูกกำหนดค่าของตัวแปรชั่วคราว
ถ้าเทียบกัน 6 กับ 5 จะสลับกัน ดังนั้นรายการของเราจะปรากฏเป็น:6, 5
โปรแกรมของเรายังไม่ได้ทำอะไรเลย เรายังไม่ได้เขียนโปรแกรมหลักที่เรียกใช้ฟังก์ชันของเราและให้รายการเพื่อจัดเรียง
เพิ่มโค้ดต่อไปนี้ใต้ sortNumbers ฟังก์ชันในรหัสของคุณ:
public static void main(String args[]) {
int[] toSort = { 5, 9, 2, 7 };
BubbleSort sortingAlgorithm = new BubbleSort();
sortingAlgorithm.sortNumbers(toSort);
System.out.println(Arrays.toString(toSort));
}
เราได้ประกาศตัวแปรที่เรียกว่า toSort ซึ่งเก็บรายการค่าที่เราต้องการจัดเรียง จากนั้นเราได้ประกาศอินสแตนซ์ของคลาส BubbleSort ที่เรียกว่า sortingAlgorithm ซึ่งเราใช้ในโค้ดบรรทัดถัดไปเพื่อเรียก sortNumbers การทำงาน. เมื่อเรียกใช้ฟังก์ชันนี้ รายการของเราจะถูกจัดเรียง
สุดท้าย เราใช้ Arrays.toString() วิธีการแปลงรายการของเราเป็นสตริงเพื่อให้เราสามารถพิมพ์ไปยังคอนโซลได้ รหัสของเราส่งคืน:
[2, 5, 7, 9]
ขณะนี้มีอาร์เรย์ที่จัดเรียงแล้ว!
เพิ่มประสิทธิภาพการจัดเรียงบับเบิ้ล
มีวิธีทำให้โค้ดของเรามีประสิทธิภาพมากขึ้น ตอนนี้ การเรียงลำดับของเราดำเนินต่อไปจนกว่าจะมีการเปรียบเทียบที่เป็นไปได้ทั้งหมด ซึ่งหมายความว่าแม้ว่าอาร์เรย์ของเราจะจัดเรียง การเรียงลำดับจะดำเนินต่อไปจนกว่าการเปรียบเทียบจะเสร็จสิ้น
เราสามารถป้องกันพฤติกรรมนี้ได้โดยการเพิ่มตัวแปรใหม่ลงในโค้ดของเรา ซึ่งจะทำให้เราสามารถหยุดการเรียงลำดับของเราได้หากมีการสลับรายการ มาเพิ่มตัวแปรนี้ใน sortNumbers . ของเรา ฟังก์ชันจากก่อนหน้านี้:
class BubbleSort {
void sortNumbers(int array[]) {
int size = array.length;
for (int item = 0; item < size - 1; item++) {
boolean hasSwapped = false;
for (int j = 0; j < size - item - 1; j++) {
if (array[j] > array[j + 1]) {
int temporary = array[j];
array[j] = array[j + 1];
array[j + 1] = temporary;
hasSwapped = true;
}
}
if (hasSwapped == false) {
break;
}
}
}
}
เราได้ทำการเปลี่ยนแปลงสามครั้งในโค้ดของเรา ภายใน for loop แรกของเรา เราได้ประกาศตัวแปรที่เรียกว่า “hasSwapped” ตัวแปรนี้ติดตามว่ามีการแลกเปลี่ยนหรือไม่ โดยค่าเริ่มต้น ตัวแปรนี้ถูกตั้งค่าเป็น "เท็จ" หากมีการแลกเปลี่ยน ค่าของตัวแปรนี้จะถูกตั้งค่าเป็น "จริง"
ในตอนท้ายของ for loop เราได้เพิ่มคำสั่ง if เพื่อตรวจสอบว่า hasSwapped เท่ากับเท็จหรือไม่ หากไม่มีการแลกเปลี่ยนใด ๆ อาร์เรย์จะถูกจัดเรียง เราใช้คีย์เวิร์ด "break" เพื่อหยุดการทำงานของลูปของเราหาก hasSwapped มีค่าเท่ากับเท็จ
มารันโค้ดของเราโดยใช้โปรแกรมหลักที่เราเขียนไว้ก่อนหน้านี้และดูว่าเกิดอะไรขึ้น:
[2, 5, 7, 9]
รายการของเราได้รับการจัดเรียงแล้ว แต่คราวนี้อัลกอริทึมของเรามีประสิทธิภาพมากขึ้น หากเราใช้รายการที่ใหญ่กว่าโดยมีค่ามากกว่าในการจัดเรียง ประสิทธิภาพของอัลกอริธึมนี้จะชัดเจนยิ่งขึ้น เพียงเท่านี้ คุณได้เขียนการเรียงลำดับบับเบิลที่ปรับให้เหมาะสมใน Java!
บทสรุป
การเรียงลำดับฟองใช้เพื่อเรียงลำดับรายการในลำดับจากน้อยไปมากหรือมากไปหาน้อย พวกเขาทำงานโดยการเปรียบเทียบค่าที่อยู่ติดกันและสลับกันหากพวกเขาอยู่ในลำดับที่ไม่ถูกต้อง
การจัดเรียงแบบบับเบิลมีสองประเภท:แบบมาตรฐานและแบบปรับให้เหมาะสม การเรียงลำดับแบบฟองมาตรฐานดำเนินการตามจำนวนครั้งของการแลกเปลี่ยนที่กำหนดไว้ล่วงหน้า ในขณะที่การเรียงลำดับแบบฟองที่ปรับให้เหมาะสมจะทำการเรียงลำดับจนกว่าจะมีการเรียงลำดับรายการเท่านั้น
ตอนนี้คุณพร้อมที่จะเริ่มเขียน Bubble sorts ใน Java อย่างผู้เชี่ยวชาญแล้ว!
