อัลกอริทึมการจัดอันดับ

การเรียงลำดับที่ช้าอย่างตั้งใจ

• คลังข้อมูลระดับมืออาชีพทั้งหมดใช้อัลกอริทึมในการเรียงลำดับที่ไม่ได้สอบให้เขียน Bubble sort และ Insertion sort มีค่า $O(n^2)$ ทั้งคู่ และถูกจัดอันดับต่ำกว่าการเรียงลำดับที่ดีในรายการขนาดใหญ่
• พวกเขาอยู่ในหลักสูตร anyway และเพื่อเหตุผลที่ดี: มีความยาวพอที่จะทำ trace ด้วยมือ และการทำ trace หนึ่งครั้งคือวิธีที่คุณเรียนรู้ว่าการเรียงลำดับ ทำอะไร กับอาเรย์จริงๆ
• ยังมีกรณีการใช้งานจริงสำหรับ insertion sort ในรายการขนาดเล็กหรือที่เรียงลำดับมาเกือบเต็มแล้ว มันเร็วที่สุดในบรรดาทั้งหมด และคลังข้อมูลจริงจะสลับไปใช้สำหรับกรณีเหล่านี้โดยเฉพาะ
• บทเรียนนี้คือ bubble sort และ insertion sort: อัลกอริทึม, พฤติกรรมของแต่ละตัว และจุดที่แต่ละตัวชนะ

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

FOR pass ← 1 TO n - 1
    swapped ← FALSE
    FOR i ← 1 TO n - pass
        IF A[i] > A[i + 1] THEN
            swap A[i], A[i + 1]
            swapped ← TRUE
        ENDIF
    NEXT i
    IF NOT swapped THEN      // already sorted
        EXIT FOR
    ENDIF
NEXT pass

• แต่ละรอบจะเปรียบเทียบ คู่ที่อยู่ติดกัน และสลับหากไม่ถูกต้อง ทำให้ค่าที่เหลือมากที่สุด "ลอย" ไปยังท้ายรายการ
• หลังรอบที่ $k$元素 $k$ ตัวสุดท้ายจะเป็นตำแหน่งสุดท้ายแล้ว นี่คือเหตุผลที่วงลูปภายในหยุดที่ $n - \text{pass}$
• ป้าย swapped ช่วย让它หยุดเร็วขึ้น: หากรอบหนึ่งไม่มีการสลับใดเลย รายการนั้นจะถูกเรียงลำดับแล้ว

Insertion sort

FOR i ← 2 TO n
    key ← A[i]
    j ← i - 1
    WHILE j >= 1 AND A[j] > key DO
        A[j + 1] ← A[j]                 // shift right
        j ← j - 1
    ENDWHILE
    A[j + 1] ← key                      // drop it in
NEXT i

• มันสร้าง ส่วนที่เรียงลำดับแล้วที่ด้านหน้า ซึ่งขยายขึ้นหนึ่งขั้นตอนในแต่ละครั้ง ตัว στοι mới จะถูกวางไว้ชั่วคราวเป็น key, ตัว στοι ที่ใหญ่กว่าจะเลื่อนไปทางขวาเพื่อเปิดช่องว่าง และใส่คีย์เข้าไปในช่องนั้น
• นี่คือวิธีที่คนส่วนใหญ่เรียงไพ่ในมือ ซึ่งเป็นการเปรียบเทียบที่ข้อสอบคาดหวัง

*ฝั่งซ้ายเรียงแล้ว ฝั่งขวา untouched และขอบเขตเคลื่อนที่ไปทางขวา

ตัวอย่างวิธีทำ: ทำตามกระบวนการหนึ่งรอบ

ประสิทธิภาพ

• In place หมายความว่าต้องใช้หน่วยความจำเสริมเพียงจำนวนคงที่ เรียงลำดับภายในอาเรย์เอง Stable หมายความว่าค่าที่เท่ากันสองค่าจะรักษาลำดับสัมพัทธ์เดิมไว้ ซึ่งสำคัญเมื่อรายการถูกเรียงลำดับด้วยฟิลด์อื่นมาก่อน
• ทั้งคู่ถึง $O(n)$ บนข้อมูลที่เรียงลำดับอยู่แล้ว แต่เฉพาะถ้า bubble sort มี flag swapped เท่านั้น如果没有มัน总会执行每一轮

ตัวอย่างวิธีทำ: การเรียงลำดับใด และทำไม

ทำไมหนึ่งรอบจึงไม่ใช่เรื่องราวทั้งหมด

• ทั้งสองการเรียงลำดับทำหลายรอบ และข้อสอบแยกแยะโดยสิ่งที่ หนึ่งรอบทำได้ และ เมื่อไหร่他们就停下来
• การทำรอบของ บับเบิลโซर्ट เปรียบเทียบคู่ ที่อยู่ติดกัน และสลับพวกมัน ดังนั้นการทำรอบหนึ่งจะพาองค์ประกอบที่เหลือมากที่สุดไปยังตำแหน่งสุดท้าย การเรียงลำดับทั้งหมดใช้ $n - 1$ รอบ
• พาสของ insertion sort จะนำ ตัว στοι ถัดไป มาเคลื่อนย้ายกลับเข้าไปในส่วนที่เรียงลำดับแล้วแล้ว ดังนั้นหลังจาก $k$ พาส ตัว στοι แรก $k$ ตัวจะเรียงลำดับ ระหว่างกันเอง แต่ยังไม่ได้อยู่ในตำแหน่งสุดท้าย
• Bubble sort สามารถปรับปรุงได้ด้วย flag: หากรอบใดรอบหนึ่งไม่มีการสลับตำแหน่งใดๆ แสดงว่ารายการนั้นถูกเรียงลำดับเรียบร้อยแล้วและอัลกอริทึมจะหยุดทำงาน สำหรับข้อมูลที่ถูกเรียงลำดับเกือบสมบูรณ์แล้ว วิธีนี้จะทำให้การทำงานเหลือเพียงรอบเดียว
• โดยไม่มี flag ทั้งสองกรณีจะมี $n^2$ ในกรณี 최악 ซึ่งนี่คือเหตุผลที่ทั้ง two เป็นตัวเลือกที่ไม่ดีสำหรับไฟล์ขนาดใหญ่ และทำไมข้อสอบจึงถามถึงไฟล์ขนาดเล็กเท่านั้น

คะแนนที่หลุดหายไป

คุณเข้าใจแล้ว