Java Bubble Sort: คู่มือฉบับสมบูรณ์

วิธีเขียน Java Bubble Sort

เมื่อโปรแกรมเมอร์พูดถึง bubble sorts พวกเขาไม่ได้พูดถึงฟองน้ำที่คุณเคยเป่ามาบ้าง พวกเขาพูดถึง sorting algorithm ที่ใช้จัดลำดับรายการ items

ในคู่มือนี้ เราจะพูดถึง bubble sorts และวิธีการทำงานของพวกมัน เราจะไป implement bubble sort ด้วย Java เพื่อให้คุณเข้าใจว่า algorithm นี้แปลงเป็นโค้ดอย่างไร โดยไม่เสียเวลา มาดุไดฟ์ Java bubble sorts!

Java Bubble Sort คืออะไร?

Bubble sort เป็น algorithm ที่จัดเรียงค่าโดยการเปรียบเทียบ adjacent elements และ swap พวกมันหากพวกมันปรากฏในลำดับผิด

กระบวนการนี้ซ้ำจนทุก item ในรายการจัดเรียงถูกต้อง Bubble sorts สามารถใช้จัดเรียงรายการได้ทั้ง ascending หรือ descending order

Bubble sorts เป็น sort แรกที่สอนใน algorithms classes เพราะพวกมันเข้าใจง่ายกว่า sorts อื่นๆ เช่น insertion sort หรือ selection sort และให้ introduction ที่ดีต่อ sorting algorithms

Bubble sorts มีประสิทธิภาพสูงสุดเมื่อข้อมูลจัดเรียงเกือบเรียบร้อยแล้ว อย่างไรก็ตาม หากข้อมูลของคุณไม่ได้จัดเรียงเลย อีกประเภท sort หนึ่งอาจมีประสิทธิภาพมากกว่า

Bubble Sorts ทำงานอย่างไร?

ก่อนที่เราจะเริ่มเขียนโค้ดสำหรับ Java bubble sort เราต้องเข้าใจก่อนว่า algorithm นี้ implement ในทางปฏิบัติอย่างไร

พิจารณารายการต่อไปนี้:

81% ของผู้เข้าร่วมระบุว่ารู้สึกมั่นใจมากขึ้นเกี่ยวกับโอกาสงานทางเทคโนโลยีหลังจากเข้าร่วมบูทแคมป์ ได้รับการจับคู่กับบูทแคมป์วันนี้

นักศึกษาจบบูทแคมป์เฉลี่ยใช้เวลาน้อยกว่า 6 เดือนในการเปลี่ยนอาชีพ ตั้งแต่เริ่มบูทแคมป์จนหางานแรก

Bubble sort ของเราเริ่มด้วยการเปรียบเทียบ element แรกและที่สองในรายการของเรา

หาก element แรกมากกว่า element ที่สอง elements เหล่านี้ swap ตำแหน่ง ในกรณีนี้ 5 ไม่มากกว่า 9 ดังนั้น elements อยู่ที่เดิม

จากนั้น sort ของเราจะเปรียบเทียบสอง items ถัดไปในรายการของเรา 9 มากกว่า 2 และดังนั้นตัวเลขสองตัวนี้ swap:

กระบวนการนี้ซ้ำจนทุก item ในรายการถูกเปรียบเทียบ ในกรณีนี้ มีการเปรียบเทียบอีกหนึ่งครั้ง: 9 มากกว่า 7 หรือไม่? 9 มากกว่า 7 ดังนั้นตัวเลขเหล่านี้ swap:

รายการของเราใกล้จะเรียงแล้ว เมื่อทุก item ถูกเปรียบเทียบแล้ว bubble sort จะเริ่มใหม่จนทุก element จัดเรียง

5 มากกว่า 2 และดังนั้นตัวเลขเหล่านี้ swap

รายการของเราตอนนี้จัดเรียงถูกต้องแล้ว Bubble sort ของเราจะเปรียบเทียบตัวเลขต่อไปจนถึงท้ายรายการ และจะหยุด นี่คือทั้งหมดของ bubble sort มันเป็น algorithm ที่ง่ายมากเมื่อคุณจับมันได้

วิธีเขียน Java Bubble Sort

การรู้ theory เป็นอย่างหนึ่ง แตคุณมาที่นี่เพื่อเรียนรู้ Java bubble sorts เราควรอภิปรายวิธี implement bubble sort ใน Java

มีสองประเภทของ bubble sorts:

• Standard bubble sort
• Optimized bubble sort

Standard bubble sort ทำ comparisons ทั้งหมดที่เป็นไปได้ แม้ array จะเรียงแล้ว นี่เพิ่มเวลาที่ bubble sort ใช้ในการ execute ทำให้ sort นี้มีประสิทธิภาพน้อยกว่า

Optimized bubble sorts ติดตามว่ารายการจัดเรียงแล้วหรือยังโดยใช้ตัวแปรเพิ่มเติม นี่อนุญาตให้เราหยุด sort ของเราทันทีที่รายการของเราจัดเรียงแล้ว

มาเริ่มเขียน standard bubble sort

Standard Bubble Sort

เริ่มต้น เราจะ import Arrays library เข้าโค้ดของเรา เราจะใช้มันภายหลังในโค้ดเพื่อพิมพ์รายการตัวเลขที่จัดเรียงแล้วไปที่ console:

import java.util.Arrays;

ตอนนี้เรื่องนั้นเสร็จแล้ว เราสามารถเริ่มเขียน algorithm ของเราได้

เราจะเริ่มด้วยการกำหนด class ที่ชื่อ BubbleSort ซึ่งจัดเก็บโค้ดสำหรับ Java program ของเรา และฟังก์ชันที่ทำ sort ของเรา:

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; } } } } }

เรา declare ฟังก์ชันชื่อ sortNumbers ซึ่งรับตัวแปรเป็นพารามิเตอร์ ฟังก์ชันนี้เริ่มด้วยการคำนวณขนาดของรายการตัวเลขที่เราระบุ

เมื่อคำนวณเสร็จ for loop ถูก initialize ลูปนี้เดินผ่านทุก item ใน array ของเรา เรา initialize for loop อีกตัวซึ่งอนุญาตให้เราเปรียบเทียบแต่ละ item ใน array

หาก item ด้านซ้ายของรายการมากกว่าตัวเลขด้านขวา ค่าจะถูก swap มิฉะนั้น ไม่มีอะไรเกิดขึ้น

เราทำ swap นี้โดยการกำหนดค่าด้านซ้ายให้ตัวแปรชื่อ "temporary" เรากำหนดค่าด้านขวาเป็นค่าที่อยู่ด้านซ้ายของการเปรียบเทียบ จากนั้น ค่าด้านซ้ายถูกกำหนดค่าของตัวแปร temporary

ถ้า 6 และ 5 กำลังถูกเปรียบเทียบ พวกมันจะถูก swap ดังนั้นรายการของเราจะปรากฏเป็น: 6, 5

โปรแกรมของเรายังไม่ทำอะไรเลย เรายังไม่ได้เขียน main program ที่เรียกฟังก์ชันของเราและให้ list มา sort

เพิ่มโค้ดต่อไปนี้ด้านล่างฟังก์ชัน 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)); }

เรา declare ตัวแปรชื่อ toSort ซึ่งจัดเก็บรายการค่าที่เราต้องการ sort เรา declare instance ของคลาส BubbleSort ชื่อ sortingAlgorithm ซึ่งเราใช้ในบรรทัดถัดไปของโค้ดเพื่อเรียกฟังก์ชัน sortNumbers เมื่อฟังก์ชันนี้ถูกเรียก รายการของเราจะถูก sort

สุดท้าย เราใช้เมธอด Arrays.toString() แปลงรายการของเราเป็น string เพื่อที่เราจะพิมพ์มันไปที่ console โค้ดของเราคืนค่า:

[2, 5, 7, 9]

ตอนนี้เรามี sorted array แล้ว!

Optimized Bubble Sort

มีวิธีทำให้โค้ดของเรามีประสิทธิภาพมากกว่า ตอนนี้ sort ของเราทำงานต่อจนทำ comparisons ทั้งหมดที่เป็นไปได้ นี่หมายความว่าแม้ array ของเราจะเรียงแล้ว sort จะทำงานต่อจน comparisons นั้นเสร็จ

เราสามารถป้องกันพฤติกรรมนี้ได้โดยการเพิ่มตัวแปรใหม่เข้าโค้ดของเรา นี่จะอนุญาตให้เราหยุด sort ของเราถ้ารายการถูก swapped มาเพิ่มตัวแปรนี้เข้าฟังก์ชัน 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 แรกของเรา เรา declare ตัวแปรชื่อ "hasSwapped" ตัวแปรนี้ติดตามว่ามีการ swap เกิดขึ้นหรือไม่ โดยค่าเริ่มต้น ตัวแปรนี้ตั้งค่าเป็น "false" หากมีการ swap ค่าของตัวแปรนี้จะถูกตั้งเป็น "true"

ที่ท้ายของ for loop ของเรา เราเพิ่ม if statement ตรวจสอบว่า hasSwapped เท่ากับ false หรือไม่ หากไม่มีการ swap เกิดขึ้น array ก็เรียงแล้ว เราใช้ keyword "break" หยุดลูปของเราไม่ให้ execute หาก hasSwapped เท่ากับ false

มา run โค้ดของเราใช้ main program ที่เราเขียนก่อนหน้านี้และดูว่าจะเกิดอะไร:

[2, 5, 7, 9]

รายการของเราถูก sort แตคราวนี้ algorithm ของเรามีประสิทธิภาพมากกว่า หากเราใช้รายการใหญ่กว่าพร้อมค่ามากกว่าที่จะ sort ความเหนือชี้ของ algorithm นี้จะชัดเจนกว่า นั่นคือมัน คุณเขียน optimized bubble sort ใน Java แล้ว!

สรุป

Bubble sorts ใช้จัดเรียงรายการใน ascending หรือ descending order พวกมันทำงานโดยเปรียบเทียบ adjacent values และ swap พวกมันหากพวกมันอยู่ในลำดับผิด

มีสองประเภทของ bubble sort: standard และ optimized Standard bubble sorts ทำ swaps จำนวนที่กำหนดไว้ล่วงหน้า ในขณะที่ optimized bubble sorts เรียงต่อจนกว่ารายการจะเรียง

ตอนนี้คุณพร้อมที่จะเริ่มเขียน bubble sorts ใน Java อย่างเชี่ยวชาญแล้ว!