การใช้การเรียงลำดับแบบฟองใน Java

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

การแนะนำ

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

คัดแยกผ่านตาเครื่องและตามนุษย์

สมมติว่าคุณต้องเรียงลำดับคอลัมน์ที่มีความสูงต่างกัน 5 คอลัมน์จากน้อยไปหามาก คอลัมน์เหล่านี้อาจหมายถึงข้อมูลประเภทใดก็ได้ (ราคาหุ้น แบนด์วิดท์ช่องทางการสื่อสาร ฯลฯ) คุณสามารถนำเสนองานนี้บางเวอร์ชันของคุณเองเพื่อให้ชัดเจนยิ่งขึ้น เป็นตัวอย่าง เราจะจัดเรียงเวนเจอร์สตามส่วนสูง: ต่างจากโปรแกรมคอมพิวเตอร์ การเรียงลำดับจะไม่ใช่เรื่องยากสำหรับคุณ เพราะคุณสามารถเห็นภาพทั้งหมดและสามารถคิดได้ทันทีว่าฮีโร่ตัวไหนจะต้องย้ายไปที่ใดจึงจะเรียงลำดับตามความสูงได้สำเร็จ คุณอาจเดาได้แล้วว่าในการจัดเรียงโครงสร้างข้อมูลนี้จากน้อยไปมาก เพียงแค่สลับตำแหน่งของ Hulk และ Iron Man:

เสร็จแล้ว!

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

• เปรียบเทียบสององค์ประกอบ
• สลับหรือคัดลอกหนึ่งในนั้น
• ไปที่องค์ประกอบถัดไป

อัลกอริธึมที่แตกต่างกันสามารถดำเนินการเหล่านี้ได้หลายวิธี แต่เราจะพิจารณาต่อไปว่าการเรียงลำดับแบบฟองทำงานอย่างไร

อัลกอริทึมการเรียงลำดับแบบบับเบิ้ล

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

• คุณย้ายไปที่องค์ประกอบศูนย์ของอาเรย์ของเรา (แม่ม่ายดำ);
• เปรียบเทียบองค์ประกอบที่เป็นศูนย์ (Black Widow) กับองค์ประกอบแรก (Hulk);
• หากองค์ประกอบที่ตำแหน่งศูนย์สูงกว่า คุณจะต้องสลับองค์ประกอบเหล่านั้น
• มิฉะนั้น หากองค์ประกอบที่ตำแหน่งศูนย์มีขนาดเล็กลง คุณจะปล่อยองค์ประกอบเหล่านั้นไว้ในตำแหน่งเดิม
• ย้ายไปที่ตำแหน่งทางด้านขวาแล้วทำการเปรียบเทียบซ้ำ (เปรียบเทียบ Hulk กับกัปตัน)

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

การใช้งาน Bubble sort ใน Java

เพื่อสาธิตวิธีการทำงานของการเรียงลำดับใน Java นี่คือโค้ดโปรแกรม:

• สร้างอาร์เรย์ 5 องค์ประกอบ
• อัปโหลดการเพิ่มขึ้นของเวนเจอร์สลงไป
• แสดงเนื้อหาของอาร์เรย์
• ดำเนินการเรียงลำดับแบบฟอง;
• แสดงอาร์เรย์ที่เรียงลำดับอีกครั้ง

คุณสามารถดูโค้ดด้านล่าง และดาวน์โหลดลงในIntelliJ IDE ที่คุณชื่นชอบได้ จะมีการวิเคราะห์ดังนี้:

class ArrayBubble{
    private long[] a;   // array reference
    private int elems;  //number of elements in the array

    public ArrayBubble(int max){    //class constructor
        a = new long[max];          //create an array with size max
        elems = 0;                  //when created, the array contains 0 elements
    }

    public void into(long value){   // method for inserting an element into an array
        a[elems] = value;           //insert value into array a
        elems++;                    //array size increases
    }

    public void printer(){          // method for outputting an array to the console
        for (int i = 0; i < elems; i++){    //for each element in the array
            System.out.print(a[i] + " ");   // output to console
            System.out.println("");         //a new line
        }
        System.out.println("----End array output----");
    }

    private void toSwap(int first, int second){ //method swaps a pair of array numbers
        long dummy = a[first];      // put the first element into a temporary variable
        a[first] = a[second];       // put the second element in place of the first
        a[second] = dummy;          //instead of the second element, write the first from temporary memory
    }

    public void bubbleSorter(){     //МЕТОД ПУЗЫРЬКОВОЙ СОРТИРОВКИ
        for (int out = elems - 1; out >= 1; out--){  //Outer loop
            for (int in = 0; in < out; in++){       //Inner loop
                if(a[in] > a[in + 1])               //If the order of the elements is wrong
                    toSwap(in, in + 1);             // call the swapping method
            }
        }
    }
}

public class Main {
    public static void main(String[] args) {
        ArrayBubble array = new ArrayBubble(5); //Create array array with 5 elements

        array.into(163);       //fill the array
        array.into(300);
        array.into(184);
        array.into(191);
        array.into(174);

        array.printer();            //display elements before sorting
        array.bubbleSorter();       //ИСПОЛЬЗУЕМ ПУЗЫРЬКОВУЮ СОРТИРОВКУ
        array.printer();            // print the sorted list again
    }
}

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

• into– วิธีการแทรกองค์ประกอบลงในอาร์เรย์
• printer– แสดงเนื้อหาของอาร์เรย์ทีละบรรทัด

• toSwap– จัดเรียงองค์ประกอบใหม่หากจำเป็น ในการดำเนินการนี้ จะใช้ตัวแปรชั่วคราวdummyซึ่งเขียนค่าของตัวเลขแรก และแทนที่ตัวเลขแรก ค่าจากตัวเลขที่สองจะถูกเขียน จากนั้นเนื้อหาจากตัวแปรชั่วคราวจะถูกเขียนไปยังหมายเลขที่สอง นี่เป็นเทคนิคมาตรฐานสำหรับการสลับสององค์ประกอบ

  และสุดท้ายก็เป็นวิธีการหลัก:

• bubbleSorter– ซึ่งทำงานหลักและเรียงลำดับข้อมูลที่เก็บไว้ในอาร์เรย์เราจะนำเสนอแยกกันอีกครั้ง:

  public void bubbleSorter(){     //МЕТОД ПУЗЫРЬКОВОЙ СОРТИРОВКИ
      for (int out = elems - 1; out >= 1; out--){  //Outer loop
          for (int in = 0; in < out; in++){       //Inner loop
              if(a[in] > a[in + 1])               //If the order of the elements is wrong
                  toSwap(in, in + 1);             // call the swapping method
          }
      }
  }

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

บทสรุป

อัลกอริธึมการเรียงลำดับแบบฟองเป็นหนึ่งในวิธีที่ช้าที่สุด หากอาร์เรย์ประกอบด้วยองค์ประกอบ N การเปรียบเทียบ N-1 จะดำเนินการในการผ่านครั้งแรก N-2 ในวินาที จากนั้น N-3 เป็นต้น นั่นคือจำนวนรอบทั้งหมดจะเกิดขึ้น: (N-1) + (N-2) + (N-3) + … + 1 = N x (N-1)/2 ดังนั้นเมื่อทำการเรียงลำดับอัลกอริทึม ทำการเปรียบเทียบประมาณ 0.5x(N ^2) สำหรับ N = 5 จำนวนการเปรียบเทียบจะอยู่ที่ประมาณ 10 สำหรับ N = 10 จำนวนการเปรียบเทียบจะเพิ่มขึ้นเป็น 45 ดังนั้น เมื่อจำนวนองค์ประกอบเพิ่มขึ้น ความซับซ้อนของการเรียงลำดับจะเพิ่มขึ้นอย่างมาก: ความเร็วของอัลกอริธึมไม่เพียงได้รับผลกระทบตามจำนวนรอบเท่านั้น แต่ยังรวมถึงจำนวนการเรียงสับเปลี่ยนที่ต้องดำเนินการด้วย สำหรับข้อมูลสุ่ม จำนวนการเรียงสับเปลี่ยนเฉลี่ย (N^2) / 4 ซึ่งเท่ากับประมาณครึ่งหนึ่งของจำนวนการส่งผ่าน อย่างไรก็ตาม ในกรณีที่เลวร้ายที่สุด จำนวนการเรียงสับเปลี่ยนอาจเป็น N^2 / 2 ได้ - ในกรณีนี้หากข้อมูลถูกจัดเรียงในลำดับย้อนกลับในตอนแรก แม้ว่านี่จะเป็นอัลกอริธึมการเรียงลำดับที่ค่อนข้างช้า แต่ก็ค่อนข้างสำคัญที่จะต้องรู้และเข้าใจวิธีการทำงาน และดังที่กล่าวไว้ข้างต้น อัลกอริธึมนี้เป็นพื้นฐานของอัลกอริธึมที่ซับซ้อนมากขึ้น เจ๊ด!