Bubble เรียงลำดับอัลกอริทึมใน Java: โปรแกรมและตัวอย่างการเรียงลำดับอาร์เรย์

ความหมายของ Bubblเรียงลำดับ?

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

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

ในบทความนี้ เราจะสร้าง... Java โครงการเพื่อดำเนินการ Bubble. เรียงลำดับ ตรวจสอบผลลัพธ์ของโค้ดที่จะช่วยให้คุณเข้าใจตรรกะของโปรแกรม จากนั้นตรวจสอบเวอร์ชันที่ปรับให้เหมาะสมและการวิเคราะห์ความซับซ้อนที่ตามมา

อย่างไร Bubblอัลกอริทึมการเรียงลำดับแบบ e ทำงานได้หรือไม่?

BubbleSort ทำงานโดยการวนซ้ำไปซ้ำมาในอาร์เรย์ แต่ละรอบจะวนจากดัชนีแรกไปยังส่วนท้ายของพื้นที่ที่ยังไม่ได้เรียงลำดับ โดยจะเปรียบเทียบค่าที่อยู่ใกล้เคียงและสลับตำแหน่งกันping ค่าเหล่านั้นจะปรากฏขึ้นเมื่อใดก็ตามที่ปรากฏในลำดับที่ไม่ถูกต้อง เนื่องจากค่าที่เหลืออยู่มากที่สุดจะเคลื่อนไปทางด้านขวาสุดของพื้นที่ที่ยังไม่ได้เรียงลำดับเสมอ ดังนั้นพื้นที่ดังกล่าวจึงหดตัวลงหนึ่งตำแหน่งพอดีหลังจากทุกรอบการเรียงลำดับ

กระบวนการทั้งหมดสามารถแบ่งออกเป็นสี่ขั้นตอนที่ทำซ้ำได้:

1. เปรียบเทียบ: ตรวจสอบองค์ประกอบที่ดัชนี j-1 เทียบกับองค์ประกอบที่ดัชนี j
2. Swap: ถ้าค่าขององค์ประกอบด้านซ้ายมากกว่าค่าขององค์ประกอบด้านขวา ให้สลับค่าทั้งสองโดยใช้ตัวแปรชั่วคราว
3. ล่วงหน้า เลื่อนไปทางขวาหนึ่งตำแหน่ง แล้วทำซ้ำจนกว่าจะถึงจุดสิ้นสุดของพื้นที่ที่ยังไม่ได้จัดเรียง
4. ทำซ้ำ: เริ่มการประมวลผลใหม่ในบริเวณที่มีจำนวนองค์ประกอบน้อยลงหนึ่งตัว และหยุดหลังจากประมวลผลครบ n-1 ครั้ง หรือเมื่อการประมวลผลนั้นไม่มีการสลับใดๆ เกิดขึ้น

ตารางด้านล่างนี้ tracนี่คืออาร์เรย์ตัวอย่าง {860, 8, 200, 9} ที่ใช้ในโปรแกรมในส่วนถัดไปของหน้านี้ มันแสดงให้เห็นอย่างชัดเจนว่าค่าใดจะเข้าสู่ตำแหน่งสุดท้ายเมื่อสิ้นสุดแต่ละรอบ

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

Bubblรหัสเทียมของอัลกอริธึมการเรียงลำดับ

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

procedure bubbleSort(array A, integer n)
    for i from 0 to n - 2 do
        swapped := false
        for j from 1 to n - i - 1 do
            // compare the adjacent pair
            if A[j - 1] > A[j] then
                swap A[j - 1] and A[j]
                swapped := true
            end if
        end for
        // no swap in a full pass means the array is sorted
        if swapped = false then
            break
        end if
    end for
end procedure

ลูปภายนอกควบคุมจำนวนรอบการประมวลผล และลูปภายในควบคุมการเปรียบเทียบภายในรอบการประมวลผลเดียว ขอบเขตบนของลูปภายในคือ n – i – 1 เนื่องจากตำแหน่ง i สุดท้ายได้เก็บค่าสุดท้ายไว้แล้ว

Java โครงการที่จะดำเนินการ Bubblอีเรียงลำดับ

โปรแกรมต่อไปนี้เรียงลำดับอาร์เรย์จำนวนเต็มจากน้อยไปมาก มีการเว้นข้อความพิมพ์เพิ่มเติมไว้ภายในลูปโดยเจตนา เนื่องจากการอ่านค่าแบบ pass-by-pass นั้น... trace เป็นวิธีที่เร็วที่สุดสำหรับผู้เริ่มต้นที่จะเข้าใจว่าการแลกเปลี่ยนสะสมกันอย่างไร

package com.guru99;

public class BubbleSort {

    public static void main(String[] args)
    {
        int arr[] = {860, 8, 200, 9};

        System.out.println("---Array BEFORE Bubble Sort---");

        printArray(arr);

        bubbleSort(arr); //sorting array elements using bubble sort

        System.out.println("---Array AFTER Bubble Sort---");

        printArray(arr);

    }

    static void bubbleSort(int[] array)
    {
        int n = array.length;
        int temp = 0;
        for(int i = 0; i < n; i++) // Looping through the array length
        {   System.out.println("Sort Pass Number " + (i + 1));
            for(int j = 1; j < (n - i); j++)
            {
                System.out.println("Comparing " + array[j - 1] + " and " + array[j]);
                if(array[j - 1] > array[j])
                {
                    //swap elements
                    temp = array[j - 1];
                    array[j - 1] = array[j];
                    array[j] = temp;
                    System.out.println(array[j] + " is greater than " + array[j - 1]);
                    System.out.println("Swapping Elements: New Array After Swap");
                    printArray(array);
                }

            }
        }

    }

    static void printArray(int[] array){

        for(int i = 0; i < array.length; i++)
        {
            System.out.print(array[i] + " ");
        }
        System.out.println();

    }
}

Output:

---Array BEFORE Bubble Sort---
860 8 200 9
Sort Pass Number 1
Comparing 860 and 8
860 is greater than 8
Swapping Elements: New Array After Swap
8 860 200 9
Comparing 860 and 200
860 is greater than 200
Swapping Elements: New Array After Swap
8 200 860 9
Comparing 860 and 9
860 is greater than 9
Swapping Elements: New Array After Swap
8 200 9 860
Sort Pass Number 2
Comparing 8 and 200
Comparing 200 and 9
200 is greater than 9
Swapping Elements: New Array After Swap
8 9 200 860
Sort Pass Number 3
Comparing 8 and 9
Sort Pass Number 4
---Array AFTER Bubble Sort---
8 9 200 860

Code คำอธิบาย: การขอ เรียงลำดับฟอง เมธอดนี้รับอาร์เรย์โดยการอ้างอิง ดังนั้นผู้เรียกจะเห็นผลลัพธ์ที่เรียงลำดับแล้วโดยไม่มีค่าส่งคืนใดๆ ตัวแปร อุณหภูมิ รักษาค่าหนึ่งค่าในระหว่างการสลับสามบรรทัด ซึ่งเป็นเหตุผลว่าทำไมอัลกอริทึมจึงต้องการหน่วยความจำเพิ่มเติมเพียง O(1) เท่านั้น นิพจน์ n – i เงื่อนไขในลูปด้านในรับประกันว่าตำแหน่งที่จัดเรียงแล้วที่ส่วนท้ายจะไม่ถูกเรียกซ้ำอีก

ปลดข้อจำกัด Bubble จัดเรียงโปรแกรมใน Java

โปรแกรมข้างต้นจะทำการวนซ้ำ n-1 ครั้งเสมอ แม้ว่าอาร์เรย์จะเรียงลำดับเรียบร้อยแล้วก็ตาม การเพิ่มแฟล็กบูลีนเพียงตัวเดียวจะช่วยแก้ไขปัญหาความไม่มีประสิทธิภาพนี้ได้ หากการวนซ้ำเสร็จสมบูรณ์โดยไม่มีการสลับข้อมูลแม้แต่ครั้งเดียว อาร์เรย์ก็จะเรียงลำดับเรียบร้อยแล้ว และลูปภายนอกสามารถหยุดทำงานได้ทันที

package com.guru99;

public class OptimizedBubbleSort {

    public static void main(String[] args) {
        int arr[] = {5, 12, 33, 47, 58};
        bubbleSort(arr);
        System.out.println(java.util.Arrays.toString(arr));
    }

    static void bubbleSort(int[] array) {
        int n = array.length;
        int passes = 0;
        for (int i = 0; i < n - 1; i++) {
            boolean swapped = false;
            for (int j = 1; j < n - i; j++) {
                if (array[j - 1] > array[j]) {
                    int temp = array[j - 1];
                    array[j - 1] = array[j];
                    array[j] = temp;
                    swapped = true;
                }
            }
            passes++;
            // Early exit: the array is already sorted
            if (!swapped) {
                break;
            }
        }
        System.out.println("Passes executed: " + passes);
    }
}

Output:

Passes executed: 1
[5, 12, 33, 47, 58]

อาร์เรย์อินพุตได้รับการจัดเรียงแล้ว ดังนั้นเวอร์ชันที่ปรับให้เหมาะสมจึงเสร็จสิ้นหลังจากการประมวลผลเพียงครั้งเดียวแทนที่จะเป็นสี่ครั้ง สำหรับข้อมูลที่เกือบจะเรียงลำดับแล้ว การเปลี่ยนแปลงนี้จะเปลี่ยนภาระงานแบบกำลังสองให้เป็นภาระงานเชิงเส้นเกือบสมบูรณ์ ซึ่งเป็นเหตุผลหลัก Bubblคำสั่ง Sort ยังคงปรากฏให้เห็นในโค้ดจริงอยู่บ้างเป็นครั้งคราว

ความซับซ้อนเชิงเวลาและความซับซ้อนเชิงพื้นที่ของ Bubblอีเรียงลำดับ

ความซับซ้อนอธิบายว่าเวลาในการทำงานเพิ่มขึ้นอย่างไรเมื่อขนาดของข้อมูลป้อนเข้าเพิ่มขึ้น สำหรับ Bubble. จำนวนการเปรียบเทียบในเวอร์ชันที่ยังไม่ได้ปรับให้เหมาะสมนั้นถูกกำหนดไว้ที่ n(n-1)/2 ซึ่งทำให้จัดอยู่ในกลุ่มกำลังสองอย่างแน่นอน

เนื่องจากการแลกเปลี่ยนทุกครั้งเกิดขึ้นภายในอาร์เรย์เดิม และใช้ตัวแปรชั่วคราวเพียงตัวเดียวเท่านั้น BubbleSort เป็นอัลกอริธึมแบบ in-place ที่ใช้พื้นที่เสริม O(1) นอกจากนี้ยังเป็นการเรียงลำดับแบบเสถียร ซึ่งหมายความว่าระเบียนสองรายการที่มีคีย์เดียวกันจะยังคงรักษาลำดับสัมพัทธ์เดิมไว้หลังจากเรียงลำดับแล้ว

ข้อดีและข้อเสียของ Bubblอีเรียงลำดับ

การเข้าใจทั้งสองด้านจะช่วยให้คุณตัดสินใจได้ว่าเมื่อใดที่อัลกอริทึมนี้เป็นตัวเลือกที่เหมาะสม และเมื่อใดควรเปลี่ยนไปใช้อัลกอริทึมอื่น

ข้อดี

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

ข้อเสีย

• การเติบโตแบบกำลังสอง: การเรียงลำดับองค์ประกอบ 10,000 รายการ ต้องใช้การเปรียบเทียบเกือบ 50 ล้านครั้งในกรณีที่เลวร้ายที่สุด
• การเขียนมากเกินไป: อัลกอริทึมนี้ทำการสลับข้อมูลมากกว่า Selection Sort มาก ซึ่ง Selection Sort นั้นสิ้นเปลืองหน่วยความจำและมีการดำเนินการเขียนข้อมูลที่ช้า
• ความสามารถในการขยายขนาดต่ำ: โดยทั่วไปแล้ว การประมวลผลในระดับการผลิตมักจะนิยมใช้ Quicksort, Merge Sort หรือเมธอด Arrays.sort ที่มีอยู่แล้วในระบบ

Bubblการเรียงลำดับแบบ e เทียบกับการเรียงลำดับแบบอื่นๆ Algorithms

ตารางด้านล่างเปรียบเทียบ Bubble. เรียงลำดับโดยใช้เทคนิคการเรียงลำดับที่ผู้เริ่มต้นจะได้เรียนรู้ต่อไป เพื่อให้คุณเห็นได้อย่างชัดเจนว่าแต่ละเทคนิคมีประสิทธิภาพอย่างไร

Bubble Sort และ Insertion Sort มีกรณีที่ดีที่สุดเชิงเส้นเหมือนกัน แต่ Insertion Sort ทำการสลับน้อยกว่าในข้อมูลที่เรียงลำดับบางส่วนแล้ว Selection Sort จะทำการสลับ n-1 ครั้งเสมอ ซึ่งทำให้มีประสิทธิภาพเท่ากับ Selection Sorttracมีประสิทธิภาพเมื่อการเขียนข้อมูลมีค่าใช้จ่ายสูง แม้ว่าจะต้องแลกมาด้วยความเสถียรที่ลดลงก็ตาม สำหรับอาร์เรย์ที่มีขนาดใหญ่กว่าสองสามร้อยองค์ประกอบ การเรียงลำดับแบบ QuickSort หรือ HeapSort คือตัวเลือกที่เหมาะสม

เมื่อคุณคุ้นเคยกับรูปแบบการวนซ้ำในอาร์เรย์ที่ใช้ในที่นี้แล้ว โครงสร้างลูปแบบเดียวกันนี้จะปรากฏในแบบฝึกหัดคลาสสิกหลายๆ แบบ เช่น ลำดับฟิโบนาชี่ใน Java และ Java โปรแกรมพาลินโดรม. Revไอวิง Java อาร์เรย์ และกว้างขึ้น Java เกี่ยวกับการสอน จะช่วยเสริมสร้างพื้นฐานที่อัลกอริทึมนี้พึ่งพาให้แข็งแกร่งยิ่งขึ้น

คำถามที่พบบ่อย