สมัครเรียนโทร. 085-350-7540 , 084-88-00-255 , ntprintf@gmail.com

ฟรี TUTORIAL JAVA

ฟรีtutorial JAVA 01 install Eclipse ฟรีtutorial JAVA 02 intro to programming Eclipse ฟรีtutorial JAVA 03 condiotion ฟรีtutorial JAVA 04.loop ฟรีtutorial JAVA 05.array ฟรีtutorial JAVA 05 2 array cont ฟรีtutorial JAVA 06 01 function ฟรีtutorial JAVA 06 02 function cont ฟรีtutorial JAVA 07 object ฟรีtutorial JAVA 08 string ฟรีtutorial JAVA 09 constructor ฟรีtutorial JAVA 10 01 oop ฟรีtutorial JAVA 10 02 oop2 ฟรีtutorial JAVA 11 exception ฟรีtutorial JAVA 12 reading file ฟรีtutorial JAVA 13 thread ฟรีtutorial JAVA 14 generic ฟรีtutorial JAVA 15 01 GUI ฟรีtutorial JAVA 15 02 GUI2 ฟรีtutorial JAVA 15 03.GUI3 ฟรีtutorial JAVA 16 using WindowBuilder ฟรีtutorial JAVA 17 event ฟรีtutorial JAVA 18 database management system ฟรีtutorial JAVA 19 ER diagram ฟรีtutorial JAVA 20 Relational ฟรีtutorial JAVA 21 Xampp ฟรีtutorial JAVA 22 JDBC ฟรีtutorial JAVA 23 MVC ฟรีtutorial JAVA 24 SQL ฟรีtutorial JAVA
ขอย้ำอีกครั้งว่าเนื้อหาที่เห็นอยู่นี้ไม่ใช่เนื้อหาตามปกติที่เราสอนในห้องเรียนเป็นแค่ tutorial ไว้อ่านประกอบเฉยๆ แทบไม่เกี่ยวกันเลย และไม่เกี่ยวกับการบ้านที่ทำครับ ในห้องเรียนเนื้อหาจะเยอะกว่านี้ค่อนข้างมากครับ
ขอบคุณน้องตี้ อย่างสูงสำหรับ Tutorial ดีๆ

ฟรี TUTORIAL DATA STRUCTURE

DATA STRUCTURE

ฟรีtutorial : DATA STRUCTURE : 01 1การเรียงลำดับ(Sorting) ฟรีtutorial : DATA STRUCTURE : 01 2 การเรียงลำดับ2 ฟรีtutorial : DATA STRUCTURE : 02 อาร์เรย์ลิสต์ (Array List) ฟรีtutorial : DATA STRUCTURE : 03 ลิงค์ลิสต์ (Linked List) ฟรีtutorial : DATA STRUCTURE : 04 สแต๊ค ฟรีtutorial : DATA STRUCTURE : 05 1 คิวและไพออริตี้คิว ฟรีtutorial : DATA STRUCTURE : 05 2 คิวและไพออริตี้คิว ฟรีtutorial : DATA STRUCTURE : 06 1 ไบนารีทรี ฟรีtutorial : DATA STRUCTURE : 06 2 ไบนารีเสิร์ชทรี ฟรีtutorial : DATA STRUCTURE : 06 3 ไบนารีเสิร์ชทรี ฟรีtutorial : DATA STRUCTURE : 08 แฮช ฟรีtutorial : DATA STRUCTURE : 09 กราฟ ฟรีtutorial : DATA STRUCTURE :
ขอย้ำอีกครั้งว่าเนื้อหาที่เห็นอยู่นี้ไม่ใช่เนื้อหาตามปกติที่เราสอนในห้องเรียนเป็นแค่ tutorial ไว้อ่านประกอบเฉยๆ แทบไม่เกี่ยวกันเลย และไม่เกี่ยวกับการบ้านที่ทำครับ ในห้องเรียนเนื้อหาจะเยอะกว่านี้ค่อนข้างมากครับ
ขอบคุณน้องตี้ อย่างสูงสำหรับ Tutorial ดีๆ

การเรียงลำดับ(Sorting)

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

การเรียงลำดับแบบฟอง (Bubble Sort)

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

 

รูป1-1

ประสิทธิภาพการทำงานของ การเรียงลำดับแบบ bubble

ประสิทธิภาพการทำงานเมื่อเกิดกรณีแย่สุด O(n2)

ประสิทธิภาพการทำงานเมื่อเกิดกรณีทั่วไป O(n2)

ประสิทธิภาพการทำงานเมื่อเกิดกรณีดีที่สุด O(n)

Bubble sort source code

 

รูป1-2

บรรทัดที่ 6 : สร้างเมท็อดชื่อ bubbleSort รับพารามิเตอร์เป็น อาร์เรย์หนึ่งมิติ (สร้างเป็นเมท็อดเดี๋ยวไวเรียก

ทดสอบทีหลัง)

บรรทัดที่ 8 : วนลูปที่หนึ่ง ลูปนี้จะคอยควบคุมให้การวนลูปเริ่มตั้งแต่ตัวแรกไปจนถึงตัวสุดท้าย โดยมีค่าเท่ากับ

ขนาดของอาร์เรย์ที่รับเป็นอินพุท

บรรทัดที่ 10 : วนลูปที่สอง ให้ลูปวนไปสุดที่ a.length-i-1 คือถ้าไม่มีการสลับให้ j ขยับได้แต่ต้องไม่เกิน i

บรรทัดที่ 12 : สร้างเงื่อนไข ถ้าตัวทางซ้าย a[j] มีค่ามากกว่าตัวทางขวา a[j+1] ให้สลับ

บรรทัดที่ 14 : การสลับสร้างตัวแปร t ขึ้นมา เอาข้อมูล a[j] ไปเก็บไว้ใน t ก่อน

บรรทัดที่ 15 : ทำการสลับโดยเอาข้อมูลของ a[j+1] มาใส่ a[j]

บรรทัดที่ 16 : เอาข้อมูลเดิมของ a[j] ที่อยู่ใน t มาใส่ a[j+1] เท่านี้การสลับก็เรียบร้อย

 

การเรียงลำดับแบบเลือก (Selection Sort)

การเรียงลำดับแบบselection  อันนี้พัฒนามาจาก bubble sort โดยที่การสลับจะเป็นการเลือกและสลับเอาที่มากที่สุดไปไว้ทางขวาของตารางหรืออาจะเป็นการเลือกเอาตัวน้อยสุดมาไว้ทางซ้ายก็ได้ ครั้งแรกตัวที่มากที่สุดจะไปอยู่ทางขวาสุด ครั้งที่สองตัวที่มากสุดรองลงมาก็จะไปอยู่ต่อจากตัวที่เรียงแล้ว ครั้งต่อๆไปตัวที่มากอันดับต่อไปก็จะไปเรียงต่อของที่เรียงไว้แล้ว ทำไปเรื่อยๆจนกว่าจะหมดข้อมูล ถ้ามีข้อมูล n ตัว จะต้องทำการตรวจสอบ n-1 ครั้ง ไม่เหมาะกับข้อมูลจำนวนมากๆๆ

 

รูป1-3

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

ประสิทธิภาพการทำงานของ การเรียงลำดับแบบ selection sort

ประสิทธิภาพการทำงานเมื่อเกิดกรณีแย่สุด O(n2)

ประสิทธิภาพการทำงานเมื่อเกิดกรณีทั่วไป O(n2)

ประสิทธิภาพการทำงานเมื่อเกิดกรณีดีที่สุด O(n2)

Selection sort source code

 

รูป1-4

บรรทัดที่ 22 : สร้างเมท็อด selectionSort รับพารามิเตอร์เป็นอาร์เรย์ a

บรรทัดที่ 24 : สร้างลูปสำหรับตรวจสอบตามขนาดของอาร์เรย์ที่รับเข้ามา

บรรทัดที่ 26 : สร้างตัวแปร last ไว้เก็บค่าตำแหน่งสุดท้าย โดยตำแหน่งสุดท้ายของ selection sort คือตำแหน่ง

ที่ต่อจากตำแหน่งของอันที่เรียงแล้วเลยต้องลบออกด้วย –i-1

บรรทัดที่ 27 : สร้างตัวแปร max_index ไว้เก็บค่าตำแหน่งของข้อมูลที่มีค่ามากที่สุด

บรรทัดที่ 28 : สร้างตัวแปร max เพื่อหาค่าที่มากที่สุด ตั้งค่าเป็น Integer.MIN_VALUE เพราะเผื่อไว้ไม่ว่าตัว

แรกที่เอาไปเทียบจะมีค่าเป็นอะไรก็จะได้มากกว่าตัวแปร max

บรรทัดที่ 29 : สร้างลูปอีกอันเพื่อให้วนตรวจหาค่าที่มากที่สุดในอาร์เรย์ที่รับเข้ามา

บรรทัดที่ 31-34 : ถ้าเจอ a ตำแหน่งที่ j ที่มีค่ามากกว่า max ให้ max เก็บ a[j] ส่วน max_index ก็เก็บตำแหน่งj

บรรทัดที่ 38-40 : ทำการสลับ max กับตำแหน่ง last

การเรียงลำดับแบบแทรก (Insertion Sort)

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

 

รูป1-5

            insertion จะแบ่งส่วนของข้อมูลเป็นส่วนที่เรียงแล้วกับยังไม่เรียง ในรูปบรรทัดแรกที่เรียงแล้วก็คือ 40 ต่อมา มาพิจารณา 15 น้อยกว่า 40 ก็เอาไปไว้ทางซ้าย ต่อมา พิจารณา 30 น้อยกว่า 40 แต่มากกว่า 15 ก็เอาไว้ตรงกลาง พิจรณาไปเรื่อยๆจนหมด็จะได้ ข้อมูลที่เรียงลำดับ

ประสิทธิภาพการทำงานของ การเรียงลำดับแบบ insertion

ประสิทธิภาพการทำงานเมื่อเกิดกรณีแย่สุด O(n2)

ประสิทธิภาพการทำงานเมื่อเกิดกรณีทั่วไป O(n2)

ประสิทธิภาพการทำงานเมื่อเกิดกรณีดีที่สุด O(n)

Insertion sort source code

 

รูป1-6

บรรทัดที่ 44 : สร้างเมท็อดชื่อ insertionSort รับอินพุทเป็นอาร์เรย์หนึ่งมิติ

บรรทัดที่ 46 : วนลูปตามขนาดของอาร์เรย์ โดยให้ i เริ่มที่ 1 ไปเรื่อยๆจนขวาสุด

บรรทัดที่ 48 : สร้างตัวแปร temp เก็บเป็นอาร์เรย์ในตำแหน่งของรอบที่วนลูป ซึ่งเป็นตัวที่เราสนใจ เพราะเราอยากรู้ว่าไอ่ตัวนี้มันจะอยู่ตำแหน่งไหนทางซ้ายมือที่เรียงแล้ว

บรรทัดที่ 50 : สร้างลูปอีกอันไว้โดยเริ่มจากตำแหน่งที่ก่อน i แล้วไล่ลดลงไปเรื่อยๆ เพื่อหาว่ามีตำแหน่งที่ temp จะไปแทรก

บรรทัดที่ 52 : (ลองนึกภาพว่ามีอาร์เรย์หนึ่ง  temp อยู่ทางขวามือของ j เสมอเพราะกำหนดให้ j อยู่หน้า temp หนึ่งตำแหน่ง แล้วไล่ลงไปทางซ้าย)ถ้าตำแหน่งที่ j มีค่าน้อยกว่า temp(ตัวที่เราต้องการว่ามันอยู่ตรงไหน) ก็ไม่ต้องทำอะไรเพราะอยู่ตำแหน่งที่ถูกต้องแล้ว break ออกจากลูป         

บรรทัดที่ 53 : แต่ถ้าหาไปเรื่อยๆแล้วเจอว่าตำแหน่งที่ j มีค่ามากกว่า temp แสดงว่า temp ต้องไปอยู่ก่อนหน้า j ก็ให้เลื่อน j ออกไป 1ตำแหน่ง ไปใส่ไว้ใน a[j+1] เป็นการดันข้อมูลไปทางขวา ถ้ายังน้อยกว่าก็ดันออกไปอีก จนได้ตำแหน่ง a[j+1] สำหรับแทรกลงไป

บรรทัดที่ 55 : ให้            a[j+1] เก็บ temp ข้อมูลก็จะไปอยู่ในตำแหน่งของมัน

จากตัวอย่างในรูป 5 15 30 40 25 รับอินพุทมา 5 ตัว อยากรู้ว่า 25 อยู่ตรงไหน 25 = a[4] เอาไปเก็บใน temp ต่อมาตรวจสอบข้อมูล (บรรทัดที่ 50) i =4 ดังนั้นต้องเริ่มจาก j ที่น้อยกว่า i อยู่1 ก็เริ่มจาก i=3 คือ 40 พบว่า25 น้อยกว่า40 ดัน 40ออกไป 1 ช่อง(บรรทัดที่ 53) ลดลงทีละ 1 ไล่มา 30 ไล่มา 15 พบว่า temp มากกว่า 15 เท่ากับว่า j ตอนนี้เป็น 1(ตอนที่จะ break บรรทัดที่ 52)  j[1]=15 ดังนั้นก็เอา temp ไปใส่  a[j+1] เท่านี้ 25 ก็จะอยู่ถัดจาก 15                                    

 



แผนผังการเรียนเขียนโปรแกรม

>