หากคุณเคยได้ยินเกี่ยวกับวิธีการเรียงลำดับในการเขียนโปรแกรม เป็นไปได้มากว่าอัลกอริทึมการเรียงลำดับแบบฟอง เป็นที่เลื่องลือแห่งหนึ่ง โปรแกรมเมอร์ทุกคนรู้จักการเรียงลำดับแบบบับเบิล (หรืออย่างน้อยก็เคยได้ยินขณะเรียนรู้) ไม่ใช่เพราะมันเป็นอัลกอริทึมการเรียงลำดับที่ดีที่สุดในโลก แต่เป็นอัลกอริธึมที่ง่ายที่สุด อัลกอริทึมนี้มักจะใช้เพื่อวัตถุประสงค์ในการเรียนรู้ หรือคุณอาจทำเป็นงานใน Java Junior Interview ของคุณ อัลกอริทึมการเรียงลำดับ Java Bubble นั้นเข้าใจง่ายมาก แต่ก็ไม่มีประสิทธิภาพ อย่างไรก็ตามลองคิดดูสิ
ขั้นตอนที่ 1: เรากำลังดำเนินการผ่านอาร์เรย์ อัลกอริทึมเริ่มต้นด้วยสององค์ประกอบแรก (ที่มีดัชนี 0 และ 1), 8 และ 7 และตรวจสอบว่าองค์ประกอบเหล่านั้นอยู่ในลำดับที่ถูกต้องหรือไม่ แน่นอน 8 > 7 เราจึงสลับมัน ต่อไป เราจะดูองค์ประกอบที่สองและสาม (ดัชนี 1 และ 2) ซึ่งตอนนี้เป็น 8 และ 1 ด้วยเหตุผลเดียวกัน เราจึงสลับองค์ประกอบเหล่านี้ เป็นครั้งที่สามที่เราเปรียบเทียบ 8 และ 2 และอย่างน้อย 8 และ 5 เราได้ทำการแลกเปลี่ยนทั้งหมดสี่รายการ: (8, 7), (8, 1), (8, 2) และ (8, 5) ค่า 8 ซึ่งเป็นค่าที่ใหญ่ที่สุดในอาร์เรย์นี้ โผล่ขึ้นมาที่ส่วนท้ายของรายการในตำแหน่งที่ถูกต้อง
ผลลัพธ์ของขั้นตอนแรกของอัลกอริทึมการเรียงลำดับแบบฟองคืออาร์เรย์ถัดไป:
ขั้นตอนที่ 2 ทำเช่นเดียวกันกับ (7,1), (7,2) และ (7,5) ตอนนี้อันดับ 7 อยู่ในตำแหน่งสุดท้าย และเราไม่จำเป็นต้องเปรียบเทียบกับ "หาง" ของรายการ มันเรียงไปแล้ว
ผลลัพธ์ของขั้นตอนที่สองของอัลกอริทึมการเรียงลำดับแบบฟองคืออาร์เรย์ถัดไป:
อย่างที่คุณเห็น อาร์เรย์นี้ถูกจัดเรียงแล้ว อย่างไรก็ตาม อัลกอริทึม Bubble Sort ควรดำเนินการต่อไปอย่างน้อยหนึ่งครั้ง ขั้นตอนที่ 3 เรากำลังผ่านอาร์เรย์อีกครั้ง ไม่มีอะไรจะแลกเปลี่ยนที่นี่ ดังนั้นหากเราใช้อัลกอริทึม Bubble Sort ที่ "ปรับปรุงแล้ว" (โดยตรวจสอบว่ามีการแลกเปลี่ยนอย่างน้อยหนึ่งครั้งในขั้นตอนก่อนหน้าหรือไม่) ขั้นตอนนี้เป็นขั้นตอนสุดท้าย
การเรียงลำดับคืออะไร
ก่อนอื่น คุณต้องเข้าใจว่าการเรียงลำดับโดยทั่วไปคืออะไร และเราสามารถเรียงลำดับอะไรได้บ้างในโปรแกรม Java หากเราสามารถเปรียบเทียบองค์ประกอบหรือวัตถุตั้งแต่ 2 รายการขึ้นไปตามคุณลักษณะใดๆ ขององค์ประกอบนั้น ก็หมายความว่าสามารถจัดเรียงองค์ประกอบหรือวัตถุเหล่านี้ตามคุณลักษณะนี้ได้ ตัวอย่างเช่น ตัวเลขในลำดับจากน้อยไปมากหรือจากมากไปน้อยหรือคำตามตัวอักษร ดังนั้นองค์ประกอบจะต้องเปรียบเทียบกัน โดยวิธีการที่องค์ประกอบของอะไร ใน Java เราสามารถเปรียบเทียบองค์ประกอบของคอลเลกชันได้ ตัวอย่างเช่น เราสามารถเรียงลำดับ Array หรือ ArrayList ของจำนวนเต็ม สตริง และอื่นๆBubble sort ทำงานอย่างไร
สมมติว่าเราต้องเรียงลำดับอาร์เรย์ของจำนวนเต็มจากน้อยไปมาก นั่นคือ จากจำนวนที่น้อยที่สุดไปหาจำนวนที่มากที่สุด ขั้นแรก เราจะไปตามอาร์เรย์ทั้งหมดและเปรียบเทียบทุกๆ 2 องค์ประกอบที่อยู่ใกล้เคียง ถ้าเรียงผิด (ข้างซ้ายใหญ่กว่าข้างขวา) เราก็เปลี่ยนให้ ในรอบแรกในตอนท้ายจะปรากฏองค์ประกอบที่ใหญ่ที่สุด (ถ้าเราเรียงลำดับจากน้อยไปหามาก) คุณอาจพูดได้ว่าองค์ประกอบที่ใหญ่ที่สุด "ปรากฏขึ้น" นั่นคือเหตุผลของชื่ออัลกอริทึมการเรียงลำดับแบบฟอง เราทำซ้ำขั้นตอนแรกจากองค์ประกอบแรกไปยังองค์ประกอบถัดไป เรามีองค์ประกอบที่ใหญ่เป็นอันดับสองในตำแหน่งถัดไป และอื่น ๆ เราสามารถปรับปรุงอัลกอริทึมได้เล็กน้อยด้วยการตรวจสอบว่ามีการแลกเปลี่ยนอย่างน้อยหนึ่งครั้งในขั้นตอนก่อนหน้าหรือไม่ ถ้าไม่ใช่เราจะหยุดวิ่งไปตามอาร์เรย์ตัวอย่างการจัดเรียงฟอง
ลองเรียงลำดับอาร์เรย์ของจำนวนเต็ม ซึ่งคุณอาจเห็นด้านล่างของรูปภาพ




โค้ด Java เรียงฟอง
บับเบิ้ลการจัดเรียง Java ทำให้เป็นจริง
มาสร้างสองวิธีสำหรับการเรียงลำดับแบบฟอง อันแรกbubbleSort(int[] myArray)เป็นระนาบหนึ่ง มันทำงานผ่านอาร์เรย์ทุกครั้ง อันที่สองoptimizedBubbleSort(int myArray[])ถูกปรับให้เหมาะสมโดยการหยุดอัลกอริทึมหากวงในไม่ทำให้เกิดการสลับใดๆ ตัวนับแสดงจำนวนขั้นตอนที่คุณทำขณะเรียงลำดับ ที่นี่เรามีการสร้าง Java แบบ Bubble sort:
import java.util.Arrays;
public class BubbleSortExample {
// Plane Bubble sort example
public static int[] bubbleSort(int[] myArray) {
int temp = 0; // temporary element for swapping
int counter = 0; // element to count quantity of steps
for (int i = 0; i < myArray.length; i++) {
counter = i + 1;
for (int j = 1; j < (myArray.length - i); j++) {
if (myArray[j - 1] > myArray[j]) {
// swap array’s elements using temporary element
temp = myArray[j - 1];
myArray[j - 1] = myArray[j];
myArray[j] = temp;
}
}
}
System.out.println("Steps quantity, non optimized = " + counter);
return myArray;
}
// An optimized version of Java Bubble Sorting
static int[] optimizedBubbleSort(int myArray[]) {
int temp;
boolean swapped;
int counter = 0; // element to count quantity of steps
for (int i = 0; i < myArray.length - 1; i++) {
counter = i + 1;
swapped = false;
for (int j = 0; j < myArray.length - i - 1; j++) {
// counter++;
if (myArray[j] > myArray[j + 1]) {
// swap arr[j] and arr[j+1]
temp = myArray[j];
myArray[j] = myArray[j + 1];
myArray[j + 1] = temp;
swapped = true;
}
} // counter = i;
// If there weren't elements to swap in inner loop, then break
if (swapped == false) {
break;
}
}
System.out.println("steps quantity, optimized = " + counter);
return myArray;
}
public static void main(String[] args) {
int arr[] = {8, 7, 1, 2, 5};
int arr1[] = {8, 7, 1, 2, 5};
System.out.println("Array arr Before Bubble Sort");
// we use java.util.Arrays toString method to print the array
System.out.println(Arrays.toString(arr));
System.out.println("Array arr After Bubble Sort");
System.out.println(Arrays.toString(bubbleSort(arr)));
System.out.println("Array arr1 Before Bubble Sort");
System.out.println(Arrays.toString(arr1));
System.out.println("Array arr1 After Optimized Bubble Sort");
System.out.println(Arrays.toString(optimizedBubbleSort(arr1)));
}
}
ผลลัพธ์ของการทำงานของอัลกอริทึม Java Bubble sort:
Array arr Before Bubble Sort
[8, 7, 1, 2, 5]
Array arr After Bubble Sort
Steps quantity, non optimized = 5
[1, 2, 5, 7, 8]
Array arr1 Before Bubble Sort
[8, 7, 1, 2, 5]
Array arr1 After Optimized Bubble Sort
steps quantity, optimized = 3
[1, 2, 5, 7, 8]
GO TO FULL VERSION