Strand Sort
หน้าตา
บทความนี้ต้องการการจัดหน้า จัดหมวดหมู่ ใส่ลิงก์ภายใน หรือเก็บกวาดเนื้อหา ให้มีคุณภาพดีขึ้น คุณสามารถปรับปรุงแก้ไขบทความนี้ได้ และนำป้ายออก พิจารณาใช้ป้ายข้อความอื่นเพื่อชี้ชัดข้อบกพร่อง |
Strand Sort คือ อัลกอริธึมการจัดเรียงที่ทำงานได้ดีหากมีหลายรายการเรียงตามลำดับ ขั้นแรกให้เริ่มต้นรายการย่อยโดยการย้ายรายการแรกจากรายการต้นฉบับไปยังรายการย่อย สำหรับแต่ละรายการถัดไปในรายการเดิมถ้ารายการนั้นมากกว่ารายการสุดท้ายของรายการย่อยให้นำรายการนั้นออกจากรายการเดิมแล้วเพิ่มลงในรายการย่อย รวมรายการย่อยไว้ในรายการเรียงลำดับขั้นสุดท้าย แยกและรวมรายการย่อยซ้ำ ๆ จนกระทั่งรายการทั้งหมดถูกจัดเรียง จัดการสินค้าสองรายการหรือน้อยกว่าเป็นกรณีพิเศษ
การนำ Strand Sort ไปใช้งานในภาษาPython
[แก้]ตัวอย่างภาษาไพทอน
def sort(array):
if len(array) < 2:
return array
result = []
while array:
sublist = [array.pop(0)]
leftovers = []
last = sublist[0]
sublist_append = sublist.append
leftovers_append = leftovers.append
for item in array:
if item >= last:
sublist_append(item)
last = item
else:
leftovers_append(item)
result = merge(result, sublist)
array = leftovers
return result
def merge(left, right):
if not left:
return right
if not right:
return left
if left[-1] > right[-1]:
left, right = right, left
it = iter(right)
y = next(it)
result = []
for x in left:
while y < x:
result.append(y)
y = next(it)
result.append(x)
result.append(y)
result.extend(it)
return result
Strand Sort เป็นอัลกอริทึมการเรียงลำดับที่ทำงานในเวลา O (n) ถ้ารายการถูกจัดเรียงแล้วและทำงานใน O (n * n) ในกรณีที่เลวร้ายที่สุด