[Project Solution] Bubble Sort … step by step

บทความนี้เป็นบทความเก่า ย้ายบล๊อกมาจาก nartra.blogspot.com

Bubble Sort

เป็นการทำให้ข้อมูลใน array มันเรียงกัน (ไม่ว่าจะเรียงจาก น้อยไปมาก หรือ มากไปน้อย ก็ตาม)
ส่วนคำสั่งของโปรเจคคือ

C:\ java programname [DataSize] [RandomSeed] [-ASC/-DSC]  

สั่งรันโปรแกรมแบบนี้แล้วให้ผลออกมาเป็น

C:\ java DemoBubbleSort 100 200 -ASC
 Bubble Sort Result:
 1: 3 0 1 8 7 2 5 4 6 9
 2: 0 1 3 7 2 5 4 6 8 9
 3: 0 1 3 2 5 4 6 7 8 9
 4: 0 1 2 3 4 5 6 7 8 9
 5: 0 1 2 3 4 5 6 7 8 9

และกำหนดให้ จำนวน array มากที่สุดไม่เกิน 100,000 ส่วน RandomSeed คือค่าที่เอาไว้ทำให้การแรมด้อมเลขมันประจายแบบสุ่มมากขึ้น

แต่ก่อนจะเริ่มเขียนโปรแกรม ลองมาทำความเข้าใจกับการเรียงข้อมูลแบบ bubble sort ซึ่งเป็นการเรียงข้อมูลแบบเบสิกที่สุดตัวนึงก่อน

หลักการ

รอบย่อย

ตัวอย่างข้อมูล: 8 23 2 12 40 21
ต้องการจะเรียงข้อมูลชุดนี้จาก น้อยไปมาก (ส่วนวิธีมากไปน้อยก็สลับกันนะ) ขั้นตอนที่เราต้องทำก็คือ

จับคู่ตัวแรกก่อน .. ดูว่าตำแหน่งมันถูกแล้วหรือยัง (เช่น 8 กับ 23 .. 8
ควรจะอยู่หน้า 23 อยู่แล้วเพราะมันน้อยกว่า
ดังนั้นคู่นี้ถือว่าถูกต้องแล้ว)

• ถ้าถูกอยู่แล้ว --> ไม่ต้องทำอะไร (แล้วข้ามไปเช็กคู่ต่อไปอีกเรื่อยๆ)
• ถ้าไม่ถูก --> ให้สลับที่พวกมันซะ (เช่น รอบที่2: 23 กับ 2 .. 23
  มากกว่า 2 ดังนั้นมันควรจะอยู่ข้างหลัง 2 ก็จับมันสลับที่กันซะ)

แล้วก็ทำแบบนี้ไปเรื่อยๆ กับทุกคู่จนถึงตัวสุดท้าย จะได้ลำดับการทำงานประมาณนี้

จากการทำงานไป 1 รอบ เราจะเห็นว่า ข้อมูลที่ "มาก" จะค่อยๆ ถูกดันไปด้านท้ายแถวเรื่อยๆ ในทุกรอบ และสิ่งที่เราได้แน่ๆ คือ ค่าที่มากที่สุดใน array จะถูกดันไปจนสุดแถว หรือก็คือการทำงานแบบนี้ (เรียกว่า 1 รอบย่อย) จะทำให้เราได้ค่ามากที่สุดมาเรียงอยู่ที่ท้ายแถว

ซึ่งถ้าเขียนเป็น code ก็จะได้ประมาณนี้

// สมมุติว่ามี array ของ int ชื่อว่า arr
for( i = 0; i < arr.length - 1; i++) {
    if( arr[i] > arr[i+1] ){
        // swap arr[i] and arr[i+1]
    }
}

คือเริ่มที่ตัวแรก ( i = 0 ) และจบที่ตัวรองสุดท้าย ( ตัวก่อน arr.length - 1 ) ... ที่เราหยุดที่ตัวรองสุดท้ายเพราะว่าการเอาข้อมูล 2 ตัวมาเทียบกันนั้นต้องใช้ ตัวมันเอง และ ตัวที่อยู่ถัดจากมัน ซึ่งตัวสุดท้ายของแถวมันไม่มีตัวต่อไป เราเลยหยุดที่ตัวรองสุดท้ายซึ่งมีตัวที่อยู่ถัดจากมันเป็นตัวสุดท้ายของแถวพอดี .. งงป่ะ? ถ้างงกลับไปอ่านใหม่อีกซักรอบนะ (ฮา)

แล้วเราก็ทำการเปรียบเทียบค่าหรือ compare ว่าถ้า ตัวมันเอง "มากกว่า" ตัวถัดจากมัน (แสดงว่าตำแหน่งผิดซะแล้ว) ก็สลับที่หรือ swap มันซะ แล้วก็ loop ไปจนถึงตัวรองสุดท้าย (เทียบกับตัวสุดท้าย) เป็นอันจบพิธี

รอบใหญ่

และในเมื่อ array ชุดนี้ของเรามีตัวเลขอยู่ 6 ตัว เราจึงต้องทำ "รอบย่อย" แบบเมื่อกี้อีก 6 ครั้ง
ซึ่งจากที่อธิบายไปข้างบน ในหนึ่งรอบเราจะได้ตัวที่ "มากที่สุด" เลื่อนเข้ามาอยู่ในเขตถูกต้อง (ซึ่งขอเรียกว่า safe zone ละกัน) รอบละ 1 ตัว

for( i = 0; i < arr.length - 1; i++) {
    // ทำรอบย่อย
}

รอบโค้ด

for( i = 0; i < arr.length - 1; i++) {    
     for( j = 0; j < arr.length - 1; j++) {
         if( arr[j] > arr[j+1] ){
             // swap arr[j] and arr[j+1]
         }
     }
}

for( i = 0; i < arr.length - 1; i++) {    
    for( j = 0; j < arr.length - 1; j++) {
        if( arr[j] > arr[j+1] ){
            int tmp = arr[j];
            arr[j] = arr[j+1];
            arr[j+1] = tmp;
        }
    }
}

เอาไปใส่ในโปรเจค

C:\ java programname [DataSize] [RandomSeed] [-ASC/-DSC]  

ความหมายของแต่ละตัวคือ สั่งรันโปรแกรม programname ผ่านคำสั่ง java ซึ่งเป็นการรันโปรแกรมปกติ ส่วนเจ้าพวก [DataSize] [RandomSeed] [-ASC/-DSC] หมายถึง arguments ของโปรแกรม

class MyBubbleSort{
    public static void main (String[] args){

    } 
}

 

โดยปกติการเขียนโปรแกรมภาษา java นั้นจะเริ่มทำงานที่ method main และเจ้า main ตัวเนี๊ยะจะต้องรับ parameter เป็น array ของ String ชุดนึง (บางคนอาจจะสงสัยมากว่ามันเอาไว้ทำอะไร) คำตอบก็คือใช้กับกรณีสั่งรันโปรแกรมผ่าน command line แล้วมีการเพิ่ม arguments ข้างหลังเข้ามานั่นแหละ
ค่าพวกนั้นจะถูกส่งมาเป็น String[] args ให้โปรแกรมเราโดยอัตโนมัติ ค่า args พวกนี้ก็เทียบได้กับเวลาเราสั่งรันโปรแกรม เช่น word ถ้าสั่งเปิดโปรแกรมขึ้นมาเฉยๆ เราจะได้หน้ากระดาษขาวจั๊วเป็นค่าเริ่มต้น
แต่ถ้าเราคลิกเปิดไฟล์ .doc จะเปิดโปรแกรมขึ้นมาเป็นหน้าตาของไฟล์ document นั้นเลย พวกไฟล์พวกนี้แหละที่ถูกส่งผ่านไปเป็น arguments ของโปรแกรม ทำให้โปรแกรมรู้ว่าความจะเปิดไฟล์นี้นะๆ ไม่ใช่เป็นขึ้นมาเป็นกระดาษเปล่าเพราะมันไม่รู้ว่าเราจะให้มันเป็นไฟล์ไหน

กลับมาที่เรื่องของเรา...

• [DataSize] คือ ขนาดของ array
• [RandomSeed] คือ ค่าซีดของการแรนด้อมเลข
• [-ASC/-DSC] คือ ทิศทาง asc - น้อยไปมาก และ dsc - มากไปน้อย

งั้นง่ายที่สุด เปิดโปรแกรมมาก็เขียนก่อนเลย

class MyBubbleSort{
    public static void main (String[] args){
        int dataSize = Integer.parseInt(args[0]);
        int randomSeed = Integer.parseInt(args[1]);
        boolean asc = args[2].equals("-ASC");
    }
}

 

args จะถูกส่งเข้ามาแบบ array ซึ่ง

1. ตัวที่ 0 จะหมายถึง [DataSize]
2. ตัวที่ 1 จะหมายถึง [RandomSeed]
3. ตัวที่ 2 จะหมายถึง [-ASC/-DSC]

ตามลับดับการเรียงเข้ามาอ่ะนะ

ขั้นต่อให้ให้สร้าง array ของ integer ซึ่งเราต้องเป็นคนแรมด้อมเลขใส่เป็นค่าเริ่มต้อให้มันด้วย

int[] arr = new int[dataSize];

สร้าง array ตามขนาดของ dataSize ที่รับมา

Random generater = new Random(randomSeed);
    for (i = 0; i < arr.length; i++) {
    arr[i] = Math.abs(generater.nextInt());
}  

เราก็สร้าง object สำหรับ random ค่าออกมาตัวนึงก่อน แล้วใส่ randomSeed ลงไปเป็น ค่าซีด
หลังจากนั้นเราก็ loop ทุกตัวที่อยู่ใน array แล้วสั่ง .nextInt() ซึ่งเป็นคำสั่งในการขอค่าเลขแรมด้อมออกมา
นอกจากนั้นยังทำให้ชัวร์ว่ามันเป็นค่าบวกเท่านั้นด้วยคำสั่ง Math.abs() 

แล้วเราก็เอา array ของเราตัวนี้ ไปเข้า code สำหรับ sort ที่เขียนไว้ตั้งแต่ต้น
แต่โจทย์บอกให้ ผู้ใช้เลือกได้ด้วยว่าจะ ASC หรือ DSC ซึ่งสิ่งที่เราเขียนไปเมื่อกี้เป็นแบบ ASC เท่านั้น
ถ้าวิธีสิ้นคิดก็เอา if-else ครบมันซะ

for( i = 0; i < arr.length - 1; i++) {    
  for( j = 0; j < arr.length - 1; j++) {
    if( asc ){
      if( arr[j] > arr[j+1] ){
        int tmp = arr[j];
        arr[j] = arr[j+1];
        arr[j+1] = tmp;
      }
    }
    else {
      if( arr[j] < arr[j+1] ){
        int tmp = arr[j];
        arr[j] = arr[j+1];
        arr[j+1] = tmp;
      }
    }
  }
}

ยุ่งนักก็ใส่มันทั้งสองตัวนี่แหละ ฝั่ง code ถึกๆ เอา เปลี่ยนแค่ มากกว่า กับ น้อยกว่า
แต่ถ้าอยากได้แบบ advance ให้อ่านข้างล่างต่อไป (ใครพอใจแค่นี้ก็ข้ามๆ ไปล่ะนะ)

ให้สังเกตว่าเงื่อนไขของเราเป็นแบบนี้

1. asc = true   +  arr[j] > arr[j+1] = true     :: swap
2. asc = true   +  arr[j] > arr[j+1] = false    :: no swap
3. asc = false  +  arr[j] > arr[j+1] = true     :: no swap
4. asc = false  +  arr[j] > arr[j+1] = false    :: swap

ถ้าใครดูออก สมการ นี้มันคือ  ! ( A XOR B ) หรือ A XNOR B นั่นเอง แต่การเขียนโปรแกรมไม่มี XNOR ให้เราเปลี่ยน ไปใช้รูปแบบ AND OR NOT แทนจะได้
A XNOR B = (A AND B) OR (!A AND !B)
อ่ะ .. ก็จะได้แบบนี้

for( i = 0; i < arr.length - 1; i++) {    
  for( j = 0; j < arr.length - 1; j++) {
     if( 
         (asc && arr[j] > arr[j+1]) ||
         (!asc && !(arr[j] > arr[j+1]) )
      ){
        int tmp = arr[j];
        arr[j] = arr[j+1];
        arr[j+1] = tmp;
     }
  }
}

code ก็จะดูไฮโซขึ้น ลดความซ้ำซ้อนในการเขียน code ลงไปได้เยอะ
แต่ก็ยังไม่หมดแค่นั้น เพราะโจทย์สั่งให้เราปริ๊นแสดงการเปลี่ยนแปลงของข้อมูลทุกขั้นตอน (สังเกตดูว่ามันเป็นขั้นตอนแบบ "รอบใหญ่" นะ)

Bubble Sort Result:
 1: 3 0 1 8 7 2 5 4 6 9
 2: 0 1 3 7 2 5 4 6 8 9
 3: 0 1 3 2 5 4 6 7 8 9
 4: 0 1 2 3 4 5 6 7 8 9
 5: 0 1 2 3 4 5 6 7 8 9

แสดงว่าในรอบใหญ่ของเราที่เคยเขียน code ไว้นั้น ทำแค่รอบย่อยไม่พอ เราต้องปริ๊นข้่อมูลออกไปด้วย

for( i = 0; i < arr.length - 1; i++) {
   // ทำรอบย่อย
   // ปริ๊นแสดงผลด้วย
}

การปริ๊นข้อมูลใน array ก็ทำได้ได้ยากหรอก ก็ loop แล้วปริ๊นไปนั่นแหละ ง่ายจะตายไปด้วย

System.out.print( (i + 1) + ": ");
for( index = 0; index < arr.length; index++) {
    System.out.print(arr[index] + " ");
}
System.out.println();

ถือจบทุกอย่าง เรียบร้อย 😉

* ขอไม่รวม code ให้ละกัน ลองอ่านตามดูแล้วทำไปเรื่อยๆ step by step