ការតម្រៀបបែបសែល
ការតម្រៀបប្រៀបធៀបនៅនឹងកន្លែងដែលមានប្រសិទ្ធភាពខ្ពស់។ វាជាទូទៅនៃការតម្រៀបបែបបញ្ចូល ដែលអនុញ្ញាតឱ្យមានការផ្លាស់ប្ដូរធាតុដែលនៅឆ្ងាយពីគ្នា។
Visualization
Details
Analogy
ស្រមៃថាកំពុងតម្រៀបសន្លឹកបៀមួយสำรับใหญ่។ แทนที่จะเปรียบเทียบសន្លឹកបៀที่อยู่ติดกัน คุณจะតម្រៀបសន្លឹកបៀที่อยู่ห่างกันก่อน (ឧ. ทุกๆសន្លឹកที่ 10)។ นี่จะทำให้សន្លឹកបៀเข้าที่โดยประมาณ។ จากนั้นคุณจะลด 'គម្លាត' (ឧ. តម្រៀបทุกๆសន្លឹកที่ 5) และทำซ้ำ จนกระทั่งในที่สุดคุณจะតម្រៀបសន្លឹកបៀที่อยู่ติดกัน។
Purpose
ដើម្បីតម្រៀបអារេដោយចាប់ផ្ដើមពីគម្លាតធំ ហើយค่อยๆลดมันลง។ สำหรับแต่ละគម្លាត វាจะทำការតម្រៀបแบบបញ្ចូលលើធាតុที่อยู่ห่างกันเท่านั้น។
Use Cases
เป็นทางเลือกที่ดีสำหรับรายการขนาดกลาง (มากถึงสองสามพันรายการ)။ มันเร็วกว่าการតម្រៀប O(n²) แบบง่ายๆ แต่ไม่ซับซ้อนเท่าการតម្រៀប O(n log n)។
Algorithm Steps
gap = n / 2
while gap > 0:
for i = gap to n-1:
temp = arr[i]
j = i
while j >= gap and arr[j-gap] > temp:
arr[j] = arr[j-gap]
j -= gap
arr[j] = temp
gap /= 2
Explanation
What's Happening?
អារេដំបូង។ ចាប់ផ្តើមដោយ gap = 4។
Code Implementation
def shell_sort(arr):
n = len(arr)
gap = n // 2
while gap > 0:
for i in range(gap, n):
temp = arr[i]
j = i
while j >= gap and arr[j - gap] > temp:
arr[j] = arr[j - gap]
j -= gap
arr[j] = temp
gap //= 2
return arr