Data structure

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

• เริ่มจาก เลือกค่าของข้อมูลที่มีค่าน้อยที่สุด
• นำมาแลกเปลี่ยกับค่าในตำแหน่งแรกสุดของกลุ่ม
• หลังจากนั้นกระทำตามหลักการทั้ง 2 กับข้อมูลที่เหลื่อ คือ ครั้งที่ 2 ค่า A(2) จะถูกแลกกับค่าที่เหลือกแล้วว่าน้อยที่สุดในลิสต์ A(2)....A(n)
• และครั้งที่ 3 ค่า  A(3) จะถูกแลกกับค่าที่เลือกแล้วว่าน้อยที่สุดในลิตส์ A(3)....A(n)
• และเรียงไปจนกระทั่งเลือข้อมูลที่ถูกเปรี่ยบเทียบแค่  2 ค่าคือ A(n-1) และ A(n) ดั้งนั้นจำนวนรอบในากรกระทำเป็น n-1 รอบ

1. ใช้เปรี่ยบเทียบคีย์ที่อยู่ติดกันทีละคู่
2. ถ้าคีย์ที่เปรียบเทียบไม่อยู่ในตำแหน่งที่ต้องการสลับที่กัน
3. ทิศทางการทำงานอาจจะทำจากคู่ซ้ายไปหาขวา หรือคู่ขวาไปหาซ้าย
4. ในแต่ระรอบที่เปรียบเทียบ คีย์ที่มีค่ามากจะถูกสลับไปตำแหน่งท้าย กรือคีย์ที่มีค่าน้อยจะถูกสลับไปยังตำแหน่งตอนบน(จะเลือกเปรียบเทียบจากขวามาซ้าย หรือซ้ายไปหาขวาก็ได้)
5. ข้อมูลที่มีค่ามากกว่าสลับไปตอนท้ายของข้อมูล

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

• ที่ทุกระดับของ  Heap  จะแตกสาขาออกไปได 2  ทาง  คือทางซ้ายและ ทางขวา
• จะต้องมีโหนดในระดับบนครบ 2  ด้านก่อน   จึงจะแตกโหนดต่อในระดับล่างได้
• การแตกโหนดออกไปนั้นจะต้องเริ่มทางด้านซ้ายก่อน  จึงจะแตกไปทางด้านขวาตามลำดับ
• ค่าคีย์ของโหนด  จะต้องถูกจัดในลักษณะที่ว่า  โหนดตัวบน (FATHER)จะต้องมีค่าของคีย์สูงกว่าโหนดตัวล่าง  (SON)

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

1. สร้างไบนารีทรี 
2. สร้างฮีป  โดยให้โหนดแม่มีค่ามากกว่าโหนดลูกเสมอ
3. สลับข้อมูลในตำแหน่งท  1  กับตำแหน่งที่  n แล้วตัดข้อมูลในตำแหน่ง ที่ n ออก 
4. ปรับทรีที่เหลือให้เป็นฮีป   โดยทำการเปรียบเทียบโหนดลูกสองโหนดพร้อมกันในแต่ละระดับ  ถ้าโหนดลูกโหนดใด   มีค่ามากกว่าก็ให้สลับตำแหน่งกับโหนดแม่ 
5. สลับข้อมูลในตำแหน่งที่ 1กับตำแหน่งที่ n -1
6.  ปรับทรีที่เหลือให้เป็นฮีป
7. ทำวนไปอย่างนี้ เรื่อย ๆ  จนกระทั่งถึงการสลับข้อมูลในตำแหน่งที่ 1 กับ ตำแหน่งที่ 2  ก็จะได้ข้อมูลที่เรียงลำดับจากน้อยไปมากตามต้องการ

ตัวอย่าง

การจัดเรียงข้อมูลโดยการรวม ข้อมูลเข้าด้วยกัน Merge Sort

เป็ นการเรียงลำดับที่อาศัยหลักการ  Divide and Conquer โดยจะแบ่ง ข้อมูลออกเป็ น 2 ส่วน ซึ่งแต่ละส่วนจะแบ่งย่อยข้อมูลเป็ นอีก 2 ส่วนเรื่อยไป จนกระทั่งไม่สามารถแบ่งได้อีก   แล้วจึงเรียงลำดับข้อมูลแต่ละส่วนย่อย  จากนั้นนำข้อมูลข้อมูลแต่ละส่วนย่อยมารวม (Merge) เข้าเป็นข้อมูลชุดเดียวกันพร้อมทั้งเรียงลำดับ

ตัวอย่าง

การจัดเรียงข้อมูลแบบเร็ว Quick Sort

เป็ นการเรียงลำดับที่อาศัยหลักการ Divide and Conquer โดยจะแบ่ง  ข้อมูลออกเป็น 2 ส่วน ซึ่งแต่ละส่วนจะแบ่งย่อยข้อมูลเป็นอีก 2 ส่วนเรื่อยไป จนกระทั่งไม่สามารถแบ่งได้อีก แล้วจึงเรียงลำดับข้อมูลแต่ละส่วนย่อย จากนั้นนำ  ข้อมูลแต่ละส่วนย่อยมารวม (Merge) เข้าเป็นข้อมูลชุดเดียวกันพร้อมทั้งเรียงลำดับข้อมูล

ตัอวอย่าง

3 9 1 2 6 7 5 4 8 //Start

3 4 1 2 5 7 6 9 8

1 4 3 2 5 7 6 9 8

1 2 3 4 5 7 6 9 8

1 2 3 4 5 6 7 9 8

.1 2 3 4 5 6 7 8 9

1. .เลือก pivot มา 1 ตัว (นิยมตัวกลาง หรือสุ่ม) 
2. เตรียมตัวชี้ ไว้ 2 ตัว ตัวนึงชี้ ซ้าย ตัวนึ่งชี้ ขวา
3. ตัวชี้ ซ้าย ให้ไล่ไปทางขวาเรื่อยๆ จนกว่าเจอตัวที่มากกว่าหรือเท่ากับ pivot
4.  .ส่วนตัวขวา ให้ไล่ไปทางซ้ายเรื่อยๆ จนกว่าเจอตัวที่น้อยกว่าหรือเท่ากับ pivot 
5. จับตัวที่ตัวชี้ ทั้ง 2 ชี้ อยู่ สลับที่กัน แล้วขยับตัวชี้ ทั้ง 2 เข้าหากัน 1 ต าแหน่ง
6.  ถ้าเกิดตัวชี้ ทั้ง 2 ยังไม่ไขว้กัน กลับไปท าข้อ 3 ไปเรื่อยๆ
7. .ถ้าไขว้กันแล้ว แบ่งฟาก เรียงฟากซ้ายก่อน แล้วเรียงฟากขวา

องค์ประกอบของทรีประกอบด้วย

• โหนดราก (Root Node) คือโหนด A ซึ่งโหนดรากหรือรูทโหนดถือเป็นโหนดแรกสำรับโครงสร้างทรีเป็นโหนดเริ่มต้นเพื่อขยายลูกหลานต่อไป
• โหนดพ่อ (Parents) คือโหนด A,B และ F ก็คือโหนดที่มี Successor
• โหนดลูก (Children) B,E,F,C,D,G,H และ I ซึ่งก็คือโหนดที่มี Predecessor
• โหนดพี่น้อง (Siblings) คือโหนด {B,E,F},{C,D}และ {G,H,I}
• โหนดใบ (Leaf Node) คือโหนด C,D,E,G,H และ I ซึ่งก็คือโหนดที่ไม่มี Successor

การสร้างต้นไม้แบบใบนาทรี (Binary Tree) 

ใบน่าทรี หมายถึง ทรีที่มีโหนดลูกไม่เกินสองโหนดจะประกอบด้ายโหนดลูกทางซ้าย (Left child) และโหนดลูกทางขวา (Right child) โหนดลูกอ่าจเป็นที่ย่อยก็ได้ ซึ่งแบ่งออกเป็นทรีย่อยทางซ้ายและทรีย่อยทางขวา และโหนดลูกแต่ละโหนดอาจมีโหนดลูกเพี่ยงด้านซ้ายหรือด้านขวาด้านเดี่ยวก็ได้ สำรับโหนดของทรีที่มีจำนวนเป็น 0 เรี่ยกว่า ทรีว่าง (Empty Tree)

ตัวอย่าง

การสร้างใบนาทรีแบบสมบูรณ์

เป็นการสร้างต้นไม้ใบนารีแต่ละโหนดภายในมีโหนดย่อยซ้อยและขวา(มั่นคือแต่ละโหนดภายใน lett son และ right son) และโหนดใบ (leaf nodes) ทั้งหลายอยู่ในระดับที่ n รูป 

ตัวอยู่างในนารีสมบูรณ์ที่มี 3 ระดับ

การเปลี่ยน  Tree เป็น  Bineeary Tree

1. พิจารณากิ่งที่อยู่ทางซ้ายสุดที่อยู่ใต้พ่อเดี่ยวกัน
2. ต่อกิ่งของโหนดทางซ้ายสุดในขั้นที่ 1 ไปทางขวาทางลำดัยอาวุโสกับพี่น้องที่เกิดจากพ่อเดี่ยวกัน
3. ทำขั้นที่ 1 และ 2 จนครบทุกโหนด
4. ปรับมุ่มของแต่ละกิ่ง ประมาณ 45 องศา

ตัวอย่าง

การท่องผ่าน Binary

เป็นการเข้าไปในโครงสร้างต้นไม้เพื่อสร้างข้อมูลในโหนดมาแสดง หรื่อเพื่อการค้นหา การประมวลผลและการเดินเยี่ยมโหนดจะมี 3 ขั้นตอนดั่งนี้

1. Inorder traversel หรือ smmyetrit order จะทำการเยี่ยมโหนดในต้นไม้ย่อยทางซ้ายแบบอินออเดอร์ กอนเยี่ยมโหนดรากและเยี่ยมโหนดในต้นไม้ย่อยทางขวาแบบอินออเดอร์ (Root/Left/Right)
2. Preorder traversel จะทำการเยี่ยมโหนดรากก่อนเยี่ยใโหนดในต้นไม้ย่อยทางซ้ายแบบพรีออเดอร์ และเยี่ยมโหนดในต้นไม้ย่อมทางขวาแบบพรี(Root/Left/Right)
3. postorder traversel หรือ Enorder จะทำการเยี่ยมโหนดในต้นไม้ย่อยทางซ้ายแบบ โพสออเดอร์ กอนเยี่ยมโหนดต้นไม้ย่อยทางขวาแบบ โพสออเดอร์ และเยี่ยมโหนดราก(Left/Right/Root)

ตัวอย่าง

1. แบบอินออเดอร์ (Root/Left/Right) DB A  EG  C HFI
2. แบบอินออเดอร์ (Root/Left/Right) ABD CEG FHI
3. แบบอินออเดอร์  (Left/Right/Root) DB GE HIE

การสร้าง Enpression Tree

เป็นต้นไม้ที่สร้างขึ้นจากตัวกระทำ (operand)  และเคื่องหมาย (operators) ทางคณิตศาสตร์ของนิพจน์โดยการว่างตัวกระทำโหนดใบ(leave node) และว่างเครื่องหมายไว้ ที่โหนดภายใน

สำรับเครื่องหมายที่เป็นเครื่องหมายเดี่ยว (unary operator) จะมีกิ่งย่อยเพี่ยงต้นไม้เดี่ยว เรามักจะวาง เครื่องหมายเดี่ยวไว้ทางซ้ายของตัวกระทำ ซึ่งเครื่องหมายที่จัดเป็นเครื่องหมายเดี่ยว ได้แก่ Log() cos()

และมีเครื่องหมายเดี่่ยว ที่ถูกจัดวางไหว้ทางขวาของตัวกระทำ ได้แก่ แฟกทอเรียล ฟังก์ชัน เลกยกกำหลังต่างๆ

ตัวอย่าง แสดงการสร้างเอ็กเพรสชันทรีจากนิพจท์ (x-((Y/R)*D))

จะได้ว่า

• การเยี่ยมโหนด แบบอินออเดอร์จะได้  X-Y/R*D  ซึ่งอยู่ในรูปอินฟิกฟอร์ม
• การเยี่ยมโหนด แบบพรีออเดอร์จะได้  -X*/YRD   ซึ่งอยู่ในรูปพรีฟิกฟอร์ม
• การเยี่ยมโหนดแบบโพสออเดอร์จะได้  XYR/D*-  ซึ่งอยู่ในรูปโพสฟีกฟอร์ม

ส่วนประกอบสำคัญของสแตก

ฟังก์ชัน push stack

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

แตกให้ไปชี้ในตำแหน่งต่อไปของสแตกก่อน ซึ่งต้องเป็นช่องหรือตำแหน่งที่ยังว่างอยู่ แล้วจึงทำการ 

Push ข้อมูลลงไปในตำแหน่งที่ตัวชี้สแตกชี้อยู่

ตัวอย่างการ push stack

อัลกอริทึมในการ push stack

1.ตรวจสอบว่าสแตกเต็มหรือไม่ โดยเปรียบเทียบค่า Top กับขนาดของตัวแปรอาร์เรย์ที่ใช้เก็บ ถ้าไม่เต็ม ทำข้อ 2. ถ้าเต็ม ทำข้อ 4.

2.ขยับตำแหน่ง Top ไปยังตำแหน่งถัดไป (Top = Top +1)

3.ทำการนำค่าที่ได้มาเก็บไว้ยังตำแหน่งของ Top {push(value,stack);}

4.แจ้งผู้ใช้งานว่า สแตกเต็มไม่สามารถเก็บข้อมูลได้

จบการทำงาน

อัลกอริทึม pop stack

1.ตรวจสอบว่าสแตกว่างหรือไม่ โดยเปรียบเทียบค่า Top ว่ามีค่าเท่ากับ -1 หรือไม่ ถ้าไม่ว่าง ทำข้อ 2. ถ้าว่าง ทำข้อ 4. isEmpty(stack)

2.ทำการดึงค่าในตำแหน่งของ Top ออกมาใช้งาน pop(stack)

3.ขยับตำแหน่ง Top ให้ถอยหลังลงมา (Top = Top-1) ไปทำข้อ 5.

4.แจ้งผู้ใช้งานว่า สแตกว่างไม่สามารถดึงข้อมูลไปใช้งานได้

5.จบการทงาน

กรณีข้อมูลแบบลิงค์ลิสต์

Begin

  IF Not EmptyStack(Stack) then

    Begin

    PopData := Stack^.Element;

  DisposeNode := Stack;

    Stack := Stack^.Next;

    Dispose(DisposeNode);

    End

  Else

    writeln(‘Stack Underflow’);

End;

เปรียบเทียบประสิทธิภาพของการสร้างสแตกด้วยอะเรย์และลิงค์ลิสต์

•การแทนที่ข้อมูลสแตกด้วยอะเรย์ มีข้อจำกัด สำหรับขนาดของสแตกและจะต้องจองเนื้อที่เท่ากับขนาด

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

•การแทนที่ข้อมูลสแตกด้วยลิงค์ลิสต์ ไม่มี ข้อจำกัดของขนาดของสแตกและหน่วยความจำจะถูกใช้ก็ต่อ

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

การแทนที่ข้อมูลด้วยลิงค์ลิสต์

ตัวอย่าง

เริ่มต้นสร้างสแตก S ขึ้นทำงานจะได้เป็นสแตกว่าง ไม่มีสมาชิกโดยตัวชี้สแตก Top ยังไม่มีค่า 

  [    ]    ===> S = {}   

    <---- Top (Top = -1)     

 นำค่า 'A' เข้ามาเก็บเป็นตัวแรกโดยใช้คำสั่ง push('A',S); ===> S = { 'A' }

 

    [       A ]<---- Top (Top = 0) // ได้มาจาก Top = Top +


การใช้สแตกเพื่อแปลงนิพจน์ Infix เป็น Postfix

ตัวดำเนินการ ก็คือ เครื่องหมายทางคณิตศาสตร์ สำหรับการคำนวณต่าง ๆ เรียงตามลำดับการดำเนิน

การก่อนหลัง (precedence) ได้แก่

  ยกกำลัง ^

  คูณ หาร * , /

  บวก ลบ + , -

ถ้าเครื่องหมายมีลำดับการดำเนินการเดียวกัน จะเลือกดำเนินงานของเครื่องหมาย จากซ้ายไปขวา

 (ยกเว้น ยกกำลัง) และถ้ามีวงเล็บจะดำเนินงานสิ่งที่อยู่ในวงเล็บก่อน

ข้อเสียของนิพจน์ infix ที่ทำให้คอมไพเลอร์ยุ่งยาก คือ ลำดับความสำคัญของโอเปอร์เรเตอร์

(Precedence) ที่ต่างกัน เช่น เครื่องหมายยกกำลัง (^) มีความสำคัญมากกว่า เครื่องหมายคูณ (*) และ

หาร (/) และเครื่องหมายคูณและหารมี ความสำคัญมากกว่าเครื่องหมายบวก (+) และลบ (-) 

เครื่องหมายใดมีลำดับความสำคัญมากกว่าจะถูกคำนวณก่อน (ถ้าไม่มีวงเล็บกำกับ)เช่น  A +  B * C 

เครื่องจะคำนวณ  B * C ก่อนแล้วนำผลลัพธ์นั้นไปบวกกับค่า A ซึ่งจะทำงานเหมือน กับ  A + (B * 

C)  ส่วนนิพจน์ใดที่มีโอเปอร์เรเตอร์ที่มีลำดับ ความสำคัญเท่ากัน การคำนวณจะกระทำจากซ้ายไป

ขวา เช่น  A – B + C จะทำ  A – B ก่อน  แล้วจึงนำผลลัพธ์นั้นไปบวกกับ ค่า  C

ข้อดีของนิพจน์ postfix คือเป็นนิพจน์ที่มีการคำนวณตาม โอเปอร์เรเตอร์ที่มาก่อนหลัง เช่น นิพจน์ 

ABC*+  หมายถึง ทำการคูณแล้วจึงทำการบวก ซึ่งคือต้องคำนวณ B*C ก่อน แล้วจึงนำผลลัพธ์นั้น

ไปบวกกับ A ต่อไป

กฎการแปลงนิพจน์ Infix, Postfix ด้วยมือ

ตัวอย่าง

1.ให้ใส่เครื่องหมายวงเล็บให้กับทุก ๆ นิพจน์ด้วยการคำนึงถึงลำดับการคำนวณ เช่น เครื่องหมายคูณ

และหารต้องมาก่อนเครื่องหมายบวกและลบ

2.ทำการเปลี่ยนสัญลักษณ์ Infix ในแต่ละวงเล็บให้มาเป็นสัญลักษณ์แบบ Postfix โดยให้เริ่มจาก

นิพจน์ที่อยู่ในวงเล็บในสุดก่อน จากนั้นก็ดำเนินการแปลงให้เป็นนิพจน์ Postfix ด้วยการย้ายโอเปอเร

เตอร์ตรงตำแหน่งวงเล็บนั้นไปยังตำแหน่งวงเล็บปิดของคู่นั้นๆ

3.ถอดเครื่องหมายวงเล็บทิ้งให้หมด

การนำสแตกมาใช้ในการแปลงนิพจน์ Infix,Postfix

1. ถ้าค่า input เป็น operand ให้นำค่าไปเป็น Output

2. ถ้าค่า input เป็น operator (เครื่องหมายคณิตศาสตร์) ให้

พิจารณาดังนี้

   2.1 ถ้า สแตกว่าง ให้นำ operator ใส่สแตก

   2.2 ถ้า สแตกไม่ว่าง ให้นำ operator ไปเปรียบกับค่า operator ตัวบน

ในสแตก ถ้าค่า operator ที่เป็น input มีค่า precedence น้อยกว่าหรือ

เท่ากับค่า operator ตัวบนของสแตก ให้ดึง operator ตัวบนในสแตกไป

เป็น output แล้วเปรียบเทียบกับ operator ในสแตกตัวถัดไป แล้วเปรียบ

เทียบเช่นเดียวกับก่อนหน้านี้  แต่ถ้า operator ที่เป็น input มีค่า

precedence มากกว่าค่า operator ตัวบนของสแตก  ให้นำค่า 

operator ที่เป็น input ใส่สแตก

3. ถ้า input เป็น (  ให้ใส่ลงสแตก

4. ถ้า input เป็น ) ให้ดึงข้อมูลออกจากสแตกทีละตัวไปเป็น output จน

กระทั่งพบ ( ในสแตก ให้ดึงออกมาทิ้งไป ไม่ต้องไปใส่เป็น output

5. ถ้า input หมด และสแตกยังมีข้อมูลอยู่ ให้ดึงข้อมูลออกจาก stack ที่ตัวไป

เป็น 

output จนกระทั่งสแตกว่าง