บับเบิ้ลจัดเรียง Java

หากคุณเคยได้ยินเกี่ยวกับวิธีการเรียงลำดับในการเขียนโปรแกรม เป็นไปได้มากว่าอัลกอริทึมการเรียงลำดับแบบฟอง เป็นที่เลื่องลือแห่งหนึ่ง โปรแกรมเมอร์ทุกคนรู้จักการเรียงลำดับแบบบับเบิล (หรืออย่างน้อยก็เคยได้ยินขณะเรียนรู้) ไม่ใช่เพราะมันเป็นอัลกอริทึมการเรียงลำดับที่ดีที่สุดในโลก แต่เป็นอัลกอริธึมที่ง่ายที่สุด อัลกอริทึมนี้มักจะใช้เพื่อวัตถุประสงค์ในการเรียนรู้ หรือคุณอาจทำเป็นงานใน Java Junior Interview ของคุณ อัลกอริทึมการเรียงลำดับ Java Bubble นั้นเข้าใจง่ายมาก แต่ก็ไม่มีประสิทธิภาพ อย่างไรก็ตามลองคิดดูสิ

การเรียงลำดับคืออะไร

ก่อนอื่น คุณต้องเข้าใจว่าการเรียงลำดับโดยทั่วไปคืออะไร และเราสามารถเรียงลำดับอะไรได้บ้างในโปรแกรม Java หากเราสามารถเปรียบเทียบองค์ประกอบหรือวัตถุตั้งแต่ 2 รายการขึ้นไปตามคุณลักษณะใดๆ ขององค์ประกอบนั้น ก็หมายความว่าสามารถจัดเรียงองค์ประกอบหรือวัตถุเหล่านี้ตามคุณลักษณะนี้ได้ ตัวอย่างเช่น ตัวเลขในลำดับจากน้อยไปมากหรือจากมากไปน้อยหรือคำตามตัวอักษร ดังนั้นองค์ประกอบจะต้องเปรียบเทียบกัน โดยวิธีการที่องค์ประกอบของอะไร ใน Java เราสามารถเปรียบเทียบองค์ประกอบของคอลเลกชันได้ ตัวอย่างเช่น เราสามารถเรียงลำดับ Array หรือ ArrayList ของจำนวนเต็ม สตริง และอื่นๆ

Bubble sort ทำงานอย่างไร

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

ตัวอย่างการจัดเรียงฟอง

ลองเรียงลำดับอาร์เรย์ของจำนวนเต็ม ซึ่งคุณอาจเห็นด้านล่างของรูปภาพ ขั้นตอนที่ 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 เรียงฟอง

บับเบิ้ลการจัดเรียง 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]

Bubble sort มีประสิทธิภาพแค่ไหน?

Bubble sort เป็นหนึ่งในอัลกอริธึมที่ง่ายที่สุดในการติดตั้ง แต่ก็ไม่มีประสิทธิภาพ มันต้องใช้คู่ของลูปที่ซ้อนกัน แม้ในอัลกอริทึมเวอร์ชันที่ปรับให้เหมาะสมที่สุด ในกรณีที่เลวร้ายที่สุด (แต่ละองค์ประกอบของชุดข้อมูลอยู่ในลำดับที่กลับกันกับที่ต้องการ) วนรอบนอกจะวนซ้ำหนึ่งครั้งสำหรับแต่ละองค์ประกอบ n ของชุดข้อมูล การวนซ้ำภายในจะวนซ้ำnครั้งในครั้งแรก ( n-1 ) ในครั้งที่สอง และต่อไปเรื่อยๆ ดังนั้น เพื่อให้nเรียงองค์ประกอบทั้งหมด ลูปจำเป็นต้องดำเนินการn*(n-1)/2ครั้ง มันเรียกO(n ² )ความซับซ้อนของเวลาและหมายความว่าอัลกอริทึมทำการเปรียบเทียบประมาณ 500,000 รายการสำหรับ 1,000 องค์ประกอบในอาร์เรย์ อย่างไรก็ตาม อัลกอริธึมการเรียงลำดับแบบฟองค่อนข้างมีประสิทธิภาพในการใช้งานหน่วยความจำ (ความซับซ้อนของหน่วยความจำคือO(n) ) และดีมากสำหรับชุดข้อมูลขนาดเล็กที่เกือบจะเรียงลำดับ