โครงสร้างข้อมูล + อัลกอริทึม = โปรแกรม
โครงสร้างข้อมูลอาร์เรย์
ปกติ การเก็บข้อมูลที่มีเพียงค่าเดียวก็สามารถใช้โครงสร้างข้อมูลเบื้องต้น แต่เมื่อลักษณะของข้อมูลเริ่มซับซ้อนและมีจำนวนมากขึ้นจึงไม่เพียงพอที่จะ ใช้ข้อมูลโครงสร้างข้อมูลเบื้องต้นได้จึงต้องนำโครงการข้อมูลแบบอื่น ๆ มาใช้แทน โดยจะกล่าวถึงโครงสร้างข้อมูลอาร์เรย์ก่อน ซึ่งสามารถเก็บข้อมูลได้เป็นจำนวนมาก ๆ เป็นชุดของข้อมูลที่เกี่ยวข้องกัน
โครงสร้างข้อมูลอาร์เรย์
อาร์เรย์เป็นโครงสร้างข้อมูลแบบหนึ่งที่ผู้ใช้ต้องกำหนดคุณสมบัติขึ้นมาก่อน โดยที่อาร์เรย์ประกอบด้วยสมาชิกจำนวนหนึ่งที่เรียกต่อรวมกันตามลำดับที่ถูกมองเป็นตาราง สมาชิกทุกตัวจะมีชนิดข้อมูลที่เป็นแบบเดียวกัน ในการใช้อาร์เรย์เป็นการเข้าถึงแบบสุ่ม หรือโดยตรง เป็นการอ้างไปยังแต่ละสมาชิกที่ต้องการได้โดยตรง ซึ่งมีตัวชี้ใช้อ้างไปยังแต่ละสมาชิกเรียกว่าดัชนี หรือ Subscript และต้องเป็นเลขจำนวนเต็ม การกำหนดช่วงหรือจำนวนของสมาชิกจะใช้ขอบเขตล่าง ซึ่งมีค่าน้อยที่สุด และขอบเขตบน ซึ่งมีค่ามากที่สุดอาร์เรย์เป็นโครงสร้างข้อมูลที่คงที่ เปลี่ยนแปลงจำนวนสมาชิกไม่ได้ขณะทำงาน และเนื่องจากข้อมูลอาร์เรย์ถูกมองเป็นตารางในการใช้งาน จึงมีการกำหนดลักษณะของอาร์เรย์ออกเป็นมิติต่าง ๆ ได้ดังนี้
โครงสร้างข้อมูลสตริง และเรคคอร์ด
โครงสร้างข้อมูลสตริง
สตริงเป็นโครงสร้างข้อมูลที่เป็นการรวบรวมโครงสร้างข้อมูลคาร์แรคเตอร์ (Character) ซึ่งเป็นตัวอักษรและสัญลักษณ์ (Symbol) ต่าง ๆ เป็นชนิดข้อมูลที่ถูกใช้งานมากชนิดหนึ่ง ภาษาเขียนโปรแกรมหลายภาษาจะกำหนดให้มาใช้งานได้ทันที เช่น ภาษาปาสคาล แต่บางภาษาไม่มีมาให้ เช่น ภาษาซี จะต้องสร้างขึ้นมาด้วยผู้เขียนโปรแกรม โดยนำโครงสร้างอาร์เรย์มาใช้และสมาชิกทุกตัวมีโครงสร้างข้อมูลคาร์แรคเตอร์ได้ชนิดเดียว ดังในรูปที่ 3.1 เป็นสตริงที่มีตัวอักษรต่อเป็นข้อความ
โครงสร้างข้อมูลสแตก
โครงสร้างข้อมูลที่รู้จักและนำมาใช้งานมากชนิดหนึ่งก็คือ สแตก ( Stack ) มีลักษณะเป็นรายการในแนวเชิงเส้น ( Linear List ) รูปแบบหนึ่ง และมีข้อกำหนด ให้ชุดปฏิบัติการ สามารถเพิ่มและลบรายการเพียงด้านเดียว ซึ่งเป็นด้านบนสุดของสแตก ( Top of Stack ) เรียกว่าตัวชี้สแตก ( Stack Pointer ) มีรูปแบบเป็น Top ( S ) โดยสแตกมีการกำหนดเป็นรูปแบบ ดังนี้
S = [ S 1 , S 2 , . . . , S T ]
ด้านบนสุดของสแตกจะอยู่ที่ Top ( S ) = S T และมีจำนวนสมาชิกในสแตกเท่ากับ T ดังในรูปที่ 4.1
รูปที่ 4.1 ตัวอย่างลักษณะสแตกที่มีสมาชิกเท่ากับ T มีตัวชี้สแตก Top
โครงสร้างข้อมูลคิว
คิว (Queue) เป็นโครงสร้างข้อมูลที่รู้จักและนำมาใช้งานมากเช่นเดียวกับสแตก (Stack) และมีลักษณะเป็นรายการในแนวเชิงเส้น (Linear List) เช่นกัน มีข้อกำหนดให้ชุดปฏิบัติการสามารถเพิ่มค่าเข้าไปในตอนท้ายของรายการเพียงด้านเดียว เรียกว่า ส่วนหลัง (Rear) และลบค่าในตอนต้นของรายการเพียงด้านเดียว เรียกว่าส่วนหน้า (Front) ซึ่งกำหนดคิวเป็นรูปแบบดังนี้
Q = [Q1, Q2, . . . , QT]
โดย Front (Q) คือ Q1 และ Rear (Q) คือ QT มีจำนานสมาชิกในคิวเท่ากับ T ดังในรูปที่ 5.1 โดยลักษณะมีตัวชี้ส่วนหน้าอยู่ด้านซ้ายและตัวชี้ด้านท้ายอยู่ด้านขวา และอาจกลับด้านกันก็ได้ให้ตัวชี้ส่วนหน้าอยู่ด้านขวาและตัวชี้ส่วนท้ายอยู่ด้านซ้าย
โครงสร้างข้อมูลลิ้งค์ลิสต์
ที่ผ่านมาโครงสร้างสแตกและคิวมีการใช้อาร์เรย์ในการเก็บค่าสมาชิก ซึ่งต้องใช้พื้นที่ในการจัดเก็บที่มีขนาดแน่นอนเปลี่ยนแปลงไม่ได้ จึงเป็นปัญหาในการใช้อาร์เรย์เมื่อขอพื้นที่มาใช้งานในขณะที่สแตกและคิวยังว่าอยู่ หรือมีโอกาสที่จะเกิดการล้นเมื่อค่าที่ต้องเก็บมากกว่าขนาดอาร์เรย์ เช่นเดียวกันเมื่อลบค่าสมาชิกใดออกหรือมีการแทรกค่าสมาชิกใหม่เข้ามา ก็จะทำให้สมาชิกอื่นๆ มีการขยับตำแหน่งตามไปด้วย
โครงสร้างข้อมูลลิ้งค์ลิสต์
วิธีแก้ปัญหาในการย้ายข้อมูลที่พบในการจัดเก็บที่มีรูปแบบเรียงตามลำดับ(Sequential)เปลี่ยนมาใช้รูปแบบไม่เรียงตามลำดับ(Non-sequential)ซึ่งรูปแบบการเรียงตามลำดับจะมีสมาชิกเรียงต่อเนื่องติดกันในทางตรรกะ (Logical) และทางกายภาพ(Physical) เป็นแบบเดียวกัน แต่รูปแบบไม่เรียงตามลำดับสมาชิกต่อเนื่องติดกันในทางตรรกะ ส่วนทางกายภาพไม่จำเป็นต้องเหมือนกัน โดยในทางตรรกะจะแสดงด้วยแต่ละสมาชิกมีการชี้ (Point) ต้อไปยังสมาชิกตัวถัดไป สมาชิกทุกตัวในรายการจึงถูกเชื่อมต่อ (Link) เข้าด้วยกัน ดังรูปที่ 6.1 เป็นรายการเชื่อมต่อหรือเรียกว่าลิงค์ลิสต์ (Linked List) มีสมาชิก N ตัว แต่ละสมาชิกเรียกว่าโหนด (Node)
รีเคอร์ซิฟ
ในระหว่างการออกแบบเขียนโปรแกรมแบบบนลงล่าง (Top-down Design) จะมีงานย่อย (Subtask) เพื่อแก้ปัญหาในแต่ละเรื่อง และผู้เขียนโปรแกรมต้องการใช้งานย่อยที่เรียบง่าย และสามารถแก้ไขปัญหาที่มีขนาดใหญ่ได้ จึงมีการใช้งานย่อยในลักษณะที่เรียกตัวเองขึ้นมาทำงาน เรียกว่า รีเคอร์ซีฟ (Recursive) เป็นเทคนิคที่ส่วนใหญ่ใช้กับโครงสร้างข้อมูลที่ไม่เป็นเชิงเส้น อย่างเช่น ทรี (Tree) และกราฟ (Graph) เพื่อให้การใช้งานมีความสะดวกและง่าย
ฟังก์ชันรีเคอร์ซีฟ
โดยส่วนใหญ่การเขียนโปรแกรมจะใช้ฟังก์ชันเรียกฟังก์ชันอื่นขึ้นมาทำงาน บางครั้งอาจต้องมีการให้ฟังก์ชันเรียกตัวเองขึ้นมาทำงานเรียกว่าฟังก์ชันรีเคอร์ซีฟ (Recursive Function) ซึ่งใช้ในบางภาษา เช่น ภาษาซี ปาสคาล จาวา ปกติแล้วการเขียนอัลกอริทึมที่มีการทำงานซ้ำแบบเดิมจะใช้การวนลูปแบบต่าง ๆ แต่ใช้เป็นฟังก์ชันรีเคอร์ซีฟแทนได้ในลักษณะทำซ้ำอัตโนมัติ บางครั้งจึงเรียกว่า ลูปเสมือน (Virtual Loop)
อัลกอริทึม
การออกแบบระบบในขั้นตอนที่สองของกระบวนการพัฒนาซอฟต์แวร์จากบทที่ 1 มี 2 ส่วนที่สำคัญ คือ การเลือกใช้โครงสร้างข้อมูลและการออกแบบอัลกอริทึม (Algorithm) ซึ่งที่ผ่านมาได้กล่าวถึงโครงสร้างข้อมูลพื้นฐานแบบต่าง ๆ และในบทนี้จะกล่าวถึงรายละเอียดของอัลกอริทึมโดยพิจารณาถึงวิธีการตรวจสอบการทำงานของอัลกอริทึมว่ามีความถูกต้องมากน้อยเพียงใดซึ่งใช้เทคนิคแบบการตรวจสอบความจริง (Verification) นอกจากนี้มีการพิจารณาเปรียบเทียบหลาย ๆ อัลกอริทึมที่ใช้แก้ปัญหาเรื่องเดียวกันว่ามีประสิทธิภาพต่างกันอย่างไรซึ่งมีเทคนิคที่นำมาใช้ตรวจวัดว่าอัลกอริทึมไหนดีกว่ากัน
การตรวจสอบความถูกต้องของอัลกอริทึม
การเรียกให้โปรแกรมหรือระบบทำงานแบบเบื้องต้นเพื่อทดสอบกับข้อมูลที่หลากหลายยังไม่มีประสิทธิภาพเพียงพอเนื่องจากการทดสอบแสดงให้ทราบถึงข้อผิดพลาดที่ปรากฏอยู่เท่านั้น แต่ข้อผิดพลาดที่ไม่ปรากฏจะไม่สามารถทราบได้ จึงนำการตรวจสอบแบบการอนุมาน (Deductive) มาใช้เพื่อรับประกันว่าผลลัพธ์มีความถูกต้อง
การตรวจสอบอัลกอริทึมเพื่อใช้แก้ไขปัญหาว่ามีความถูกต้องจึงใช้การอนุมานซึ่งแสดงขั้นตอนการประมวลผลของอัลกอริทึมถูกต้องหรือไม่ตั้งแต่มีการรับข้อมูลเข้ามาและแก้ปัญหาจนถึงผลลัพธ์ที่ได้ออกมา ดังนั้น การตรวจสอบความถูกต้องของอัลกอริทึม A เริ่มต้นด้วยการ
วินิจฉัย I เป็นการสมมุติข้อมูลที่จะรับเข้ามาใช้งาน (Input Assertion) เรียกว่าเงื่อนไขตอนต้นเรียกว่าเงื่อนไขตอนท้าย (Post ondition) ได้เป็นข้อพิสูจน์ทางตรรกะแสดงให้ทราบวา O จะเกิดขึ้นตาม I และได้เป็น
ได้หลักเกณฑ์ คือ เมื่อกำหนดเงื่อนไขตอนต้น I หลังจากอัลกอริทึม A ทำงานจนถึงจุดสิ้นสุด (Terminate) จะต้องได้เงื่อนไขตอนท้าย O โดยพิจารณาจากตัวอย่างอัลกอริทึมหาค่าเฉลี่ยของค่าทั้งหมดที่เก็บไว้ในอาร์เรย์ดังในตารางที่ 8.1
ตารางที่ 8.1 อัลกอริทึมคำนวณหาค่าเฉลี่ย
1.กำหนดค่าเริ่มต้นให้ตัวแปร sum = 0
2.กำหนดค่าเริ่มต้นให้ตัวแปรดัชนี i = 0
3.วนลูป while i < n ให้ทำดังนี้
a. นำค่าของอาร์เรย์ X[i] บวกกับตัวแปร sum
b. เพิ่มค่าให้กับตัวแปร i หนึ่งค่า
4. คำนวณหาค่าเฉลี่ย sum/n และส่งคืนกลับ |
เมื่อวินิจฉัยการรับค่า I จะได้คำอธิบายดังนี้
I: ค่าที่รับเข้ามาประกอบด้วยตัวเลข n > 1 และอาร์เรย์ X ที่เก็บค่าเลขทศนิยม
เมื่อวินิจฉัยผลลัพธ์ O ออกมาจะได้คำอธิบาย
O: อัลกอริทึมทำงานเสร็จ ค่าที่ส่งคืนกลับมาให้เป็นค่าเฉลี่ยของ X[0],…,X[n-1]
การแสดงผลการทำงานได้ว่าเงื่อนไขตอนท้าย O จะเกิดขึ้นมาได้ตามเงื่อนไขตอนต้น I และมีหลายช่วงของอัลกอริทึมซึ่งเป็นการวินิจฉัยตอนกลาง (Intermediate Assertion) โดยเกี่ยวกับสถานะของการประมวลผลเมื่อทำงานถึงในช่วงนั้น ๆ จากตัวอย่างอัลกอริทึมที่ผ่านมามีการวินิจฉัยตอนกลาง L ในส่วนท้ายของการวนลูป while ซึ่งจะเป็นจริงทุกครั้งเมื่อการทำงานมาถึงช่วงนี้และการวินิจฉัยตอนกลางนี้เรียกว่าการวนลูปสม่ำเสมอ (Loop Invariant) จะได้ว่า
I: ค่าที่เข้ามาประกอบด้วยตัวเลข n > 1 และอาร์เรย์ X ที่เก็บค่าเลขทศนิยม
1. กำหนดค่าเริ่มต้นให้ตัวแปร sum = 0
2. กำหนดค่าเริ่มต้นให้ตัวแปรดัชนี i = 0
3. วนลูป while i < n ให้ทำดังนี้
a. นำค่าของอาร์เรย์ X[i] บวกให้ตัวแปร Sum
b. เพิ่มค่าให้กับตัวแปร i หนึ่งค่า
L: ค่าของตัวแปร i เป็นจำนวนครั้งในการทำงานที่ถึงในแต่ละช่วง และตัวแปร sum เป็นผลรวมค่าของแต่ละสมาชิก i ในอาร์เรย์ X
4. คำนวณค่าเปลี่ยน sum/n และส่วนคืนกลับ
O: อัลกอริทึมทำงานเสร็จ ค่าที่ส่งคืนกลับมาให้เป็นค่าเฉลี่ยของ X[i],…,X[n-1]
การตรวจสอบจึงประกอบด้วยการแสดงคำอธิบายให้ทราบว่าการวินิจฉัย L จะเกิดขึ้นตาม
การรับค่าเข้ามาของการวินิจฉัย I และแสดงให้ทราบว่าการวินิจฉัย O จะเกิดขึ้นตามการวินิจฉัย L
การอนุมานทางคณิตศาสตร์สามารถนำมาใช้กับการวนลูปสม่ำเสมอ I ได้โดยสมมุติให้ k เป็นจำนวนครั้งในการทำงานที่ไปถึงส่วนล่างของการวนลูป ให้ ik และ sumk เป็นค่าของตัวแปร i และ sum ตามลำดับของแต่ละครั้งที่ทำงานมาถึง เมื่อ k = 1 เป็นการผ่านรอบแรกในลูป ค่าของ i มีค่าเป็น 0 จากค่าเริ่มต้นเท่ากับ 0 (บรรทัด 2) ตัวแปร sum มีค่าเท่ากับ X[0] (บรรทัด 3) ดังนั้นจะได้ว่าตัวแปร i และ sum มีค่าที่ถูกวินิจฉัยของ L เมื่อ k = 1 หากสมมุติให้การทำงานเมื่อไปถึงส่วนล่างของการวนลูปสำหรับครั้งที่ k การวนลูปสม่ำเสมอของ L ได้เป็น ดังนี้
ik = k และ sumk = X[0] + . . . + X[k]
ซึ่งสามารถตรวจสอบได้ว่า L เป็นจริงเช่นกันเมื่อการทำงานต่อไปผ่านไปถึงการวนลูปในครั้งที่ k + 1 ซึ่งได้เป็น
ik+1 = k + 1 และ sumk+1 = X[0] +. . . + X[k]
ในรอบที่ k + 1 เมื่อผ่านการวนลูปค่าของ i มีความถูกต้องเพื่อใช้งานดังนี้
sumk+1 = sumk + X[k] (บรรทัด 3a)
= X[0] +. . . + X[k] (การอนุมานสมมุติ)
และค่าของ i จะเพิ่มขึ้นหนึ่งค่าดังนี้
ik+1 = ik + 1 (บรรทัด 3b)
= k + 1 (การอนุมานสมมุติ)
จากนี้เมื่อทำต่อเนื่องโดยการอนุมานในแต่ละครั้งการทำงานไปถึงส่วนล่างของการวนลูปค่าของตัวแปร i และ sum จะถูกวินิจฉัยในการวนลูปสม่ำเสมอ หลังจากการวนลูปทำงานผ่านรอบที่ n ค่าของ sum = X[0] + ... + X[n-1] และค่าของ i = n เมื่อค่าของ i เท่ากับค่า n นิพจน์ i < n ซึ่งควบคุมการทำงานซ้ำในลูปเป็นเท็จ ลูป while จึงหยุดการทำงานและทำต่อที่บรรทัด 4 เป็นการคำนวณหาค่าของสมาชิกในอาร์เรย์ จากนั้นการทำงานถึงจุดสิ้นสุดของอัลกอริทึมและนำการวินิจฉับผลลัพธ์มาใช้ ดังนั้น การตรวจสอบความถูกต้องของอัลกอริทึมจึงเสร็จสมบูรณ์
โครงสร้างข้อมูลทรี
โครงสร้างข้อมูลในบทต่าง ๆ ที่ได้กล่าวผ่านมาเป็นโครงสร้างเชิงเส้น (Linear Data Structure) แต่ละสมาชิกจะมีสมาชิกตัวถัดไปเพียงตัวเดียว สำหรับในบททนี้จะกล่าวถึงโครงสร้างข้อมูลไม่เป็นเชิงเส้น (Nonlinear Data Structure) ซึ่งแต่ละสมาชิกสามารถมีสมาชิกตัวถัดไปได้หลายตัว โดยมีแนวความคิดของโครงสร้างแตกสาขา (Branching Structure) และเป็นที่รู้จักคือ โครงสร้างข้อมูลทรี (Tree) ซึ่งกล่าวถึงในบทนี้กับโครงสร้างข้อมูลกราฟ (Graph) จะกล่าวถึงในบทหน้าถัดไป
ทรีทั่วไป
จากลักษณะพิเศษของทรีทั่วไป (General Tree) มีการกำหนดเป็นระดับซึ่งมีตัวแรก คือ รูททรี (Rooted Tree) ซึ่งมีเพียงโหนดเดียวทำหน้าที่เป็นรูท (Root) และมีความแตกต่างจากโหนดอื่น ๆ รูทของทรี T จะกำหนดเป็น Root(T) โดยทรี T เป็นเช็ตจำนวนที่แน่นอน (Finite Set) ตั้งแต่ 0 หรือมากกว่าของโหนด (v1, v2, . . . , vn) ดังนั้น
1. จะมีเพียงโหนดเดียว (v1) ที่ออกแบบเป็นพิเศษ เรียกว่า Root (T)
2. โหนดที่เหลือ (v2, . . . , vn) จะถูกแบ่งออกเป็นส่วน ๆ เท่ากับ m
0 ที่ต่อกันเป็นเช็ตชื่อ T1, T2, . . ., Tm จะได้ว่าแต่ละ Ti คือ ทรีและเป็นทรีย่อย (Subtree) ของรูททรีหรือ Root(T)
3. หากทรีใด ๆ ไม่มีโหนดเลยเรียกว่านัลทรี (Null Tree)
โครงสร้างข้อมูลกราฟ
กราฟ (Graph) เป็นโครงสร้างข้อมูลไม่เป็นเชิงเส้น (Nonlinear Data Structure) มีความแตกต่างจากโครงสร้างข้อมูลทรีในบทที่ผ่านมา แต่เป็นลักษณะพิเศษแบบหนึ่งของกราฟ โดยทรีเป็นกราฟอะไซคลิกที่ไม่มีการวนลูปและการวนถอยกลับ เป็นกราฟเชื่อมกันที่มีเพียงเอจเดียวระหว่างสองโหนด
กราฟมีลักษณะเป็นเซ็ตของจุด (Point) และเซ็ตของเส้น (Line) ซึ่งแต่ละเส้นทำหน้าที่เชื่อมจุดเข้าด้วยกัน แต่ละจุดเรียกว่าโหนด (Node) ของกราฟและเส้นเรียกว่าเอจ (Edge) บางครั้งเอจจะเรียกว่าอาร์ค (Arc) และโหนดเรียกว่าเวอร์ทิค (Vertice) โดยกำหนดให้กราฟ G มีเซ็ตของโหนดเป็น VG และเซ็ตของเอจเป็น EG เช่น ในรูปที่ 10.1 VG = {a, b, c, d} และ EG = {1, 2, 3, 4, 5, 6, 7, 8,} จำนวนสมาชิกที่มีใน VG เรียกว่าออเดอร์ (Order) ของกราฟ ถ้าออเดอร์เท่ากับ 0 คือ กราฟไม่มีสมาชิกเรียกว่านัลกราฟ (Null Graph)
การจัดเรียงลำดับข้อมูล
สำหรับบทนี้เป็นการกล่าวถึงเทคนิคในการจัดเรียงลำดับค่าของข้อมูล ( Sorting ) ซึ่งเป็นกระบวนการที่คล้ายกับเทคนิคในการค้นหาค่าของข้อมูล ( Searching ) ที่จะกล่าวในบทถัดไปเป็นการจัดเรียงลำดับค่าของข้อมูลหรือการเรียงลำดับข้อมูลจะพิจารณาจากการรวบรวมเรคคอร์ดหรือระเบียน ( Record ) โดยมีคีย์ที่นำมาใช้พิจารณาถึงลำดับก่อนหน้าและหลังของแต่ละเรคคอร์ดเพื่อประสิทธิภาพการทำงานและง่ายต่อการเรียกใช้งาน การเรียงลำดับข้อมูลจึงเป็นกระบวนการเพื่อจัดการเรคคอร์ดให้จัดเรียงลำดับตามค่าของคีย์ เป็นเทคนิคที่ช่วยให้การค้นหาข้อมูลมีประสิทธิภาพมากขึ้น โดยมีการแบ่งออกเป็น 2 ประเภทหลัก ๆ คือ
การเรียงลำดับภายใน
การเรียงลำดับภายใน ( Internal Sorting ) เป็นหลักการที่นำมาใช้เมื่อข้อมูลทั้งหมดที่รวบรวมไว้มีขนาดเล็กเพียงพอที่จะเก็บไว้ และทำการเรียงลำดับภายในหน่วยความจำหลัก ( Memory ) เวลาที่ใช้ในการอ่านและเขียนเรคคอร์ดจะไม่นำมาใช้พิจารณาถึงประสิทธิภาพการเรียงลำดับข้อมูล แต่จะใช้เวลาในการเปรียบเทียบค่าของคีย์มาพิจารณา นอกจากนี้การเรียงลำดับภายในยังแบ่งออกเป็น 2 ลักษณะ คือ การเรียงลำดับข้อมูลที่ใช้เฉพาะพื้นที่หน่วยความจำของตนเอง ( Inplace Sort ) และการเรียงลำดับข้อมูลที่ต้องใช้พื้นที่หน่วยความจำเพิ่มเติมเข้ามาช่วยจัดเรียง
การเรียงลำดับภายนอก
การเรียงลำดับภายนอก ( External Sorting ) เป็นหลักการที่นำมาใช้กับข้อมูลที่รวบรวมไว้เป็นจำนวนมาก ๆ ไม่สามารถเก็บไว้ในหน่วยความจำหลักได้หมดในคราวเดียวกัน แต่ต้องเก็บไว้ในหน่วยความจำสำรอง เช่น เทปแม่เหล็กหรือจานแม่เหล็ก การเรียงลำดับข้อมูลจะกระทำได้เพียงบางส่วน ในแต่ละครั้ง ประสิทธิภาพการเรียงลำดับแบบนี้จึงพิจารณาจากเวลาที่ใช้อ่านและเขียน เพื่อถ่ายโอนข้อมูลระหว่างหน่วยความจำหลักกับหน่วยความจำสำรอง
บางครั้งการเรียงลำดับใช้กับเรคคอร์ดที่มีค่าของคีย์ซ้ำกันได้ ทำให้อัลกอริทึมการเรียงลำดับเรียกว่า สเตเบิ้ล ( Stable Sort ) เมื่อลำดับของเรคคอร์ดที่มีค่าของคีย์ที่ซ้ำกันยังคงมีลำดับเหมือนเดิมหลังจากมีการเรียงลำดับ เช่น เรคคอร์ดที่ 5 และ 8 มีค่าของคีย์เท่ากัน หลังจากที่เรียงลำดับแล้วเรคคอร์ดที่ 5 ยังคงมาก่อนเรคคอร์ดที่ 8 เหมือนเดิม จึงเรียกว่า การเรียงลำดับแบบสเตเบิ้ล แต่ถ้าหากเรคคอร์ดที่ 5 ไปอยู่หลังเรคคอร์ดที่ 8 ไม่ว่าจะเป็นสเตเบิ้ล การเรียงลำดับแบบสเตเบิ้ลนำมาใช้เมื่อลำดับเดิมยังมีความสำคัญหรือมีความหมายบางอย่างในการใช้งาน เช่น การเรียงลำดับเรคคอร์ดตามค่าของคีย์แต่คำนึงถึงเวลาของแต่ละเรคคอร์ดที่บันทึกเก็บไว้
การค้นหาข้อมูล
ในบทนี้เป็นการกล่าวถึงเทคนิคในการค้นหาค่าของข้อมูล (Searching) ที่เป็นโครงสร้างซึ่งเป็นเทคนิคที่นำมาใช้กับแฟ้มข้อมูล และเมื่อพิจารณาถึงการรวบรวมเรคคอร์ด แต่ละเรคคอร์ดจะมีคีย์ที่นำมาใช้แยกแยะความแตกต่างจากเรคคอร์ดอื่น ๆ คีย์อาจประกอบด้วยฟิลด์เดียวหรือหลายฟิลด์ ค่าของคีย์อาจจะสร้างความเป็นหนึ่งเดียวให้กับเรคคอร์ดหรือเป็นแบบให้มีค่าซ้ำกันได้หลายเรคคอร์ด แต่คำนึงถึงลำดับก่อนหลังเมื่อถูกเพิ่มเข้ามา การค้นหาข้อมูลจึงเป็นกระบวนการหาตำแหน่งของเรคคอร์ดที่ต้องการตามค่าของคีย์ โดยมีอัลกอริทึมการค้นหาเป็นเทคนิคในการค้นหาเรคคอร์ดตามค่าของคีย์ซึ่งเป็นค่าที่ได้รับเข้ามาเพื่อค้นหา ในการค้นหาจะสิ้นสุดลงเมื่อพบเรคคอร์ดที่มีค่าคีย์ตรงกันหรือไม่พบ อัลกอริทึมที่นำมาใช้มีหลายแบบแต่ที่กล่าวถึง คือ
1. การค้นหาแบบลำดับ (Sequential Search)
2. การค้นหาแบบแบ่งครึ่ง (Binary Search)
3. การค้นหาแบบสอดแทรก (Interpolation Search)
4. การค้นหาข้อความ (Text Searching)
อ้างอิง