klainfo's weblog (กล้าอินโฟ)

ไหนๆ เรียนวิชา Algorithm มาแล้ว มาเขียน Blog ให้เป็นประโยชน์กะรุ่นน้องหน่อยละกัน

Bubble Sort [O(n²)]

1 2 3 4 5 6 7 8 9

def bubble(list): swap = True while swap: swap = False for i in range(len(list)-1): if list[i] > list[i+1] : list[i],list[i+1] = list[i+1],list[i] swap = True return list

รายละเอียดเพิ่มเติม Wikipedia

Selection Sort [O(n²)]

1 2 3 4 5 6 7 8 9

def selection(list): for i in range(len(list)-1): min = i for j in range(i+1,len(list)): if list[min] > list[j] : min = j if i != min : list[i],list[min] = list[min],list[i] return list

รายละเอียดเพิ่มเติม Wikipedia

Insertion Sort [O(n²)]

1 2 3 4 5 6

def insertion(list): for i in range(1,len(list)): for j in range(i): if list[i] <= list[j] : list[i],list[j] = list[j],list[i] return list

รายละเอียดเพิ่มเติม Wikipedia

Quick Sort [O(n log n)]

1 2 3 4 5 6 7

def qsort(lst): if len(lst) = 1: return lst pivot = lst.pop(0) greater_eq = qsort([i for i in lst if i >= pivot]) lesser = qsort([i for i in lst if i < pivot]) return lesser + [pivot] + greater_eq

รายละเอียดเพิ่มเติม Wikipedia

Merge Sort [O(n log n)]

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26

def merge(left, right): result = [] i ,j = 0, 0 while(i < len(left) and j < len(right)): if (left[i] <= right[j]): result.append(left[i]) i = i + 1 else: result.append(right[j]) j = j + 1   result += left[i:] result += right[j:] return result   def mergesort(list): if len(list) < 2: return list else: middle = len(list) / 2 left = mergesort(list[:middle]) right = mergesort(list[middle:]) return merge(left, right)   if __name__ == "__main__": print mergesort([3, 4, 8, 0, 6, 7, 4, 2, 1, 9, 4, 5])

รายละเอียดเพิ่มเติม Wikipedia

ผลการทดสอบ

N=999

Bubble Sort                  0.213470935822

Selection Sort              0.0615670681

Insertion Sort              0.0541729927063

Quick Sort                    0.0682079792023

Merge Sort                    0.00430583953857

N=10,000

Bubble Sort                  21.2315962315

Selection Sort              5.70303916931

Insertion Sort              5.75223207474

Merge Sort                   0.0512270927429

Python Sort                 0.000328063964844

เมื่อทดสอบกับชุดข้อมูลที่ random ขึ้นมา สรุปว่า Bubble ห่วยสุด ตามสมมติฐานพื้นฐาน

Python sort ยังเจ๋งกว่า Merge Sort ที่เขียนกันขึ้นมาเอง

สำหรับ python sort ใช้คำสั่งว่า

1	print sorted(list)