DES231 · Lab 2 · ตอนที่ 3

เรียงของสี่วิธี แล้วเลิกเรียงด้วยแฮช

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

ประมาณ 22 นาที ของที่น้องมีแล้ว: Lab 0 คลาส · ลูป · ลูปซ้อนลูป · เมธอดที่คืนค่า Lab 1 เรียกตัวเอง base case · อาเรย์และการเลื่อนของ โจทย์ในใบงานครบทั้ง 7 ชิ้น ตอนสุดท้ายก่อน Exam 1

1เลขเก้าตัวสลับกันมั่ว จะบอกเครื่องยังไงให้เรียงเอง

2สามเครื่องมือที่ต้องมีก่อนเรียงของ

สามเครื่องมืออาเรย์ที่ส่งเข้าเมธอดแล้วของเดิมเปลี่ยนจริง (เมธอด void จึงเรียงของได้) · การสลับที่สองช่องต้องมีตัวแปรพักสามบรรทัด ไม่งั้นค่าเดิมหาย · และการแทรกคำสั่งพิมพ์ตรงจุดที่ลำดับเปลี่ยน ซึ่งเป็นสิ่งที่โจทย์ทั้งสี่ข้อสั่งไว้ครับ

3เดินทีละก้าว — Selection กับ Insertion

ทุกวิธีเริ่มจากแผง สามคำถามก่อนเขียนอัลกอริทึมเรียง — หนึ่งรอบทำอะไร · รอบต่อไปเหลือของเท่าไร · หยุดเมื่อไร ตอบครบสามข้อเมื่อไร โค้ดจะออกมาเองครับ

Exercise 1SelectionSort
Complete the method SelectionSort in the file Sorting.java. Print out the sequence when there is a change in the sequence. Note that the methods swap, printArray and findIndexSmallest are provided.
เปิดโจทย์และวิธีทำ Exercise 1
Exercise 2InsertionSort
Complete the method InsertionSort in the file Sorting.java. Print out the sequence when there is a change in the sequence. Note that the method swap is provided.
เปิดโจทย์และวิธีทำ Exercise 2
ตัวเลขที่เล่าเรื่องได้ทั้งเรื่องข้อมูลชุดเดียวกันเก้าตัว selection พิมพ์ 6 บรรทัด แต่ insertion พิมพ์ 20 บรรทัด — ผลลัพธ์สุดท้ายเท่ากันเป๊ะ ต่างกันที่จำนวนครั้งที่ลำดับเปลี่ยน · selection สลับได้มากสุดรอบละหนึ่งครั้ง ส่วน insertion สลับคู่ติดกันทุกก้าวที่เดินถอยหลังครับ

4แบ่งแล้วเรียกตัวเอง — Merge กับ Quick

Exercise 3RecursiveMergeSort
Complete the method RecursiveMergeSort in the file Sorting.java. Call RecursiveMergeSort for leftHalf, rightHalf, and merge them. Note the method merge is provided.
จุดที่พลาดกันบ่อยleftHalf กับ rightHalf เป็นอาเรย์ใหม่คนละก้อนกับ A ถ้าเรียกตัวเองแล้วไม่ merge กลับเข้า A ผลที่เรียงแล้วจะหายไปกับก้อนชั่วคราว · และดัชนีของก้อนขวาเยื้องอยู่ ต้องเขียน rightHalf[i - midIndex] ครับ
Exercise 4RecursiveQuickSort
Complete the method RecursiveQuickSort in the file Sorting.java. Call itself for sorting the leftHalf and the rightHalf.
เปิดโจทย์และวิธีทำ Exercise 4
คำว่า end สองความหมายในไฟล์เดียวกันใน RecursiveQuickSort ตัว end คือช่องสุดท้ายที่รวมอยู่ด้วย (เพราะบรรทัด int pivot = A[end]; ต้องหยิบค่ามาได้) แต่ใน findIndexSmallest ตัว end คือช่องที่ไม่รวม (ลูปข้างในเป็น j < end) จึงต้องส่ง A.length ไม่ใช่ A.length - 1 ครับ

5แฮช — เลิกหา แล้วคำนวณเอาว่าอยู่ช่องไหน

ช่องว่างคือเลขศูนย์ไม่มีเขียนไว้ที่ไหนในใบงานเลย แต่โค้ดที่อาจารย์ให้ใช้เลข 0 แทนช่องว่าง — เห็นได้จากเฉลยที่มี 0 คั่น และจากบรรทัด H[addr] = 0; ในเมธอด delete · ไม่รู้ข้อนี้แล้วเขียนเงื่อนไข while ไม่ถูกครับ
Exercise 5 afillHashTable — หกช่องว่าง
Complete the method fillHashTable. Step1: Find an original address according to the Hash function. Step2: check collision. if collision, find an open address.
เปิดโจทย์และวิธีทำ Exercise 5 a
Exercise 5 b & csearch และ delete
Complete the method Search. Searching for a key is similar to filling in data to Hash. Most code can be cut and pasted from the method fillHashTable. · Complete the method delete to delete a key from the hash table.
เปิดโจทย์และวิธีทำ Exercise 5 b กับ 5 c

6สี่เรื่องของ Exam 1 คือคำถามเดียวกันในสี่เสื้อผ้า

สามอย่างที่นำไปใช้ต่อได้

เรียงของ = ทำซ้ำการตัดสินใจเล็ก ๆ อย่างเดียว: สี่วิธีต่างกันแค่ว่าการตัดสินใจนั้นคืออะไร — หาตัวน้อยสุด · หาที่แทรก · รวมสองก้อน · แยกสามกองครับ
สามคำถามก่อนเขียนโค้ด: หนึ่งรอบทำอะไร · รอบต่อไปเหลือของเท่าไร · หยุดเมื่อไร — ตอบครบแล้วจะได้หัวลูป หรือได้พารามิเตอร์กับ base case ของการเรียกตัวเองครับ
แฮชคือการเลิกหา: คำนวณเอาเลยว่าของอยู่ช่องไหน แลกกับการที่สองคีย์อาจได้ช่องเดียวกัน จึงต้องมีวิธีเขยิบและเงื่อนไขว่าหยุดเขยิบเมื่อไรครับ