สมัครเรียนโทร. 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 ดีๆ

การเรียงลำดับแบบผสาน (Merge Sort)

                Merge sort เป็นอัลกอริทึมแบบแบ่งแยกและเอาชนะ (divide and conquer algorithm) ก็คือมีการแบ่งแยก โดยแบ่งข้อมูลออกเป็นสองส่วนจากนั้นให้ recursive เรียกตัวเอง ต่อมาเอาชนะเป็นการเอาแต่ละส่วนมาพิจารณารวมกันจนได้เป็นส่วนใหญ่ที่เรียงลำดับเรียบร้อยแล้ว โดยส่วนที่เอามาพิจารณาต้องเรียงลำดับแล้วด้วย สมมติว่ามีข้อมูลอยู่ n ตัว เวลาการทำงานก็จะเป็น T(n) ซึ่งการคำนวณหาเวลาก็หาได้จาก master’s method คือ T(n) = 2T(n/2) + n 

            การทำงานของ merge sort เป็นไปอย่างรวดเร็วเพราะในกรณีแย่สุดก็ยังทำงานแค่ O(n log n) นอกจากนี้ยังสามารถทำได้ทั้งแบบบนลงล่าง (Top-down) และแบบล่างขึ้นบน (Bottom-up) 

 

 

รูป1-7

            บรรทัดที่ 1 มีข้อมูลอยู่หนึ่งชุด แบ่งออกมาครึ่งหนึ่งแล้วแบ่งอีกครึ่งหนึ่งจนได้ข้อมูลเดี่ยวในบรรทัดที่ 4 ค่อยๆ merge ที่ข้อมูลกลับเข้ามาโดยเรียงให้เป็นลำดับ รวมกันเรื่อยๆจนได้บรรทัดที่ 7 ก็จะได้ข้อมูลชุดเดิมที่เอาเข้ามาแต่เรียงลำดับแล้ว

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

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

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

ประสิทธิภาพการทำงานเมื่อเกิดกรณีดีที่สุด O(n log n) โดยทั่วไป หรือ O(n) เมื่อใส่เงื่อนไขพิเศษ

Merge sort source code

 

รูป1-8

บรรทัดที่  59 : สร้างเมท็อด mergeSort รับอินพุทเป็น อาร์เรย์ และตัวแปรตำแหน่งซ้ายสุด(l) ตัวแปรตำแหน่งขวาสุด(r)

บรรทัดที่  60 : ถ้ารับเข้ามาแล้วตำแหน่ทางซ้ายมากกว่าตำแหน่งทางขวาให้คืนค่าออกไป

บรรทัดที่  61 : สร้างตัวแปร m เพื่อหาตำแหน่งตรงกลาง โดยตำแหน่งตรงกลางจะได้จากการเอาตำแหน่งซ้ายกับขวามาบวกกันแล้วหารสอง

บรรทัดที่  63 : เรียกซ้ำตัวเองโดยให้อินพุทขวาสุดเป็นตรงกลางแล้วหาค่ากลาง เรียกซ้ำแบ่งไปเรื่อยๆ

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

บรรทัดที่  69-70 : เอาตัวน้อยช่อง i (ช่องซ้ายสุดถึงตรงกลาง) ไปเก็บใน k เพิ่มค่าตรวจสอบตัวถัดไป

บรรทัดที่  73-74 : เอาตัวน้อยช่อง j (ช่องตรงกลางไปถึงขวา) ไปเก็บใน k เพิ่มค่าตรวจสอบตัวถัดไป

บรรทัดที่  78-79 : ถ้าตัวซ้ายมากกว่าตัวตรงกลางแล้วให้ออกจากลูป

บรรทัดที่  92-93 : เอาค่าที่อยู่ใน temp[i] มาใส่ a[i] ให้เป็นลำดับ

การเรียงลำดับแบบเร็ว (Quick Sort)

            การเรียงลำดับแบบเร็ว คือโดยส่วนใหญ่จะสามารถเรียงลำดับได้เร็วกว่าแบบอื่นในบรรดากลุ่ม O(n log n) แต่ก็มีกรณีเลวร้ายสุดคือ O(n) แต่ก็ไม่ได้เกิดบ่อยๆ โดย quick sort ก็เป็นอัลกอริทึมแบบแบ่งแยกและเอาชนะเหมือน merge sort แต่ก็ไม่เหมือนกันตรงที่ quick sort แบ่งอาร์เรย์ใหญ่ออกเป็นสองอาร์เรย์ย่อยแล้วค่อยๆทำจากสองอาร์เรย์ย่อย โดยจะซุ่มหาตำแหน่งกลางซึ่งอาจจะไม่ได้อยู่ตรงกลางก็ได เรียกว่า pivot ในการเปรียบเทียบ เพื่อทำการสลับให้ค่าที่น้อยกว่าจุดที่เลือกไปอยู่ทางซ้ายของตำแหน่งกลาง recursive ซ้ำจนทั้งหมดอยู่ในตำแหน่งที่ถูกต้อง

 

รูป1-9

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

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

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

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

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

Quick sort source code

 

รูป1-10

บรรทัดที่  99 : สร้างเมท็อด quicksort รับอินพุทเป็น อาร์เรย์ และตัวแปรตำแหน่งซ้ายสุด(l) ตัวแปรตำแหน่งขวาสุด(r)

บรรทัดที่  101 : ถ้ารับเข้ามาแล้วตำแหน่งทางซ้ายมากกว่าตำแหน่งทางขวาให้คืนค่าออกไป

บรรทัดที่  102 : สร้างตัวแปร temp เก็บค่าของข้อมูลตัวซ้ายสุด

บรรทัดที่  103 : สร้างตัวแปร i โดยให้ i เริ่มที่ตำแหน่งซ้ายสุด

บรรทัดที่  104 : สร้างตัวแปร j โดยให้ j เริ่มที่ตำแหน่งขวาสุดบวก1

สิ่งที่จะทำต่อไปนี้คือ

 

รูป1-11

            สร้าง i และ j สำหรับเลื่อนข้อมูลให้ i เลื่อนไปทางขวา ส่วน j เลื่อนไปทางซ้ายเลื่อนจนกระทั่ง i กับ j มาพบกันตรงกลาง โดยถ้าพบว่า ตำแหน่งของ i มีข้อมูลที่มีค่ามากกว่าตำแหน่งของ j ให้สลับข้อมูลสองตัว ส่วนข้อมูลเท่ากับไม่ต้องสลับที่กันเพราะไม่ได้อะไร

บรรทัดที่  106 : วนลูปตราบเท่าที่ i ยังน้อยกว่า j

บรรทัดที่  108-113 : ถ้า temp ยังน้อยกว่าตัวตำแหน่งที่ j ให้ j เลื่อนมาทางซ้ายและ i เลื่อนไปทางขวา

บรรทัดที่  115-118 : ถ้าตำแหน่งที่มีข้อมูลน้อยกว่า temp ให้เลื่อน i ไปทางขวา แต่ถ้า i เท่ากับ r ก็ break

บรรทัดที่  120-124 : ตอนที่ i ยังน้อยกว่า j ให้ สลับตำแหน่งกัน

บรรทัดที่  132 : เรียกซ้ำการทำงาน

บรรทัดที่  133 : เรียกซ้ำการทำงาน

 

การเรียงลำดับแบบเชลล์ (Shell Sort)

            เป็นการเรียงลำดับที่ปรับปรุงมาจาก insertion sort อีกที เพราะ insertion sort ช้าตรงที่ต้องเลื่อนข้อมูลออกไปทีละช่องๆ เชลล์ซอร์ทก็เปลี่ยนเป็นเลื่อนทีละ h ช่องแทน ดูได้จากรูปข้างล่าง

            มีข้อมูลอยู่หนึ่งชุด

 

                                                                         รูป1-12          

 

รูป1-13

                   แบ่งข้อมูลเป็นสามส่วน โดยจะเลือกตามรูปข่างล่างโดยเสมือนว่าตัวที่ห่างกันอยู่ติดกัน

 

รูป1-14

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

 

รูป1-15

Shell sort source code

 

รูป1-16

บรรทัดที่ 167 : สร้างคลาส shellSort รับอินพุทเป็นอาร์เรย์ a

บรรทัดที่ 169-170 : สร้างตัวแปล h สำหรับการเลือกช่องว่างว่าจะให้ห่างกันกี่ตัว

บรรทัดที่ 171 : ให้ลดลงทีละหารสอง

บรรทัดที่ 173: วนลูปขนาดเท่ากับ h

บรรทัดที่ 175-183: เป็นการ insertion

 



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

>