你可以將Bubble排序爲幺半羣或半羣嗎？

考慮下面的僞代碼冒泡排序你可以將Bubble排序爲幺半羣或半羣嗎？

procedure bubbleSort(A : list of sortable items) 
    repeat  
    swapped = false 
    for i = 1 to length(A) - 1 inclusive do: 
     /* if this pair is out of order */ 
     if A[i-1] > A[i] then 
     /* swap them and remember something changed */ 
     swap(A[i-1], A[i]) 
     swapped = true 
     end if 
    end for 
    until not swapped 
end procedure

這裏是冒泡排序爲斯卡拉

def bubbleSort[T](arr: Array[T])(implicit o: Ordering[T]) { 
    import o._ 
    val consecutiveIndices = (arr.indices, arr.indices drop 1).zipped 
    var hasChanged = true 
    do { 
    hasChanged = false 
    consecutiveIndices foreach { (i1, i2) => 
     if (arr(i1) > arr(i2)) { 
     hasChanged = true 
     val tmp = arr(i1) 
     arr(i1) = arr(i2) 
     arr(i2) = tmp 
     } 
    } 
    } while(hasChanged) 
}

這是Haskell的實現代碼：

bsort :: Ord a => [a] -> [a] 
bsort s = case _bsort s of 
       t | t == s -> t 
       | otherwise -> bsort t 
    where _bsort (x:x2:xs) | x > x2 = x2:(_bsort (x:xs)) 
         | otherwise = x:(_bsort (x2:xs)) 
     _bsort s = s

是否有可能把它表述成幺半羣還是半羣？

來源

2014-02-19 hawkeye

你可以（例如）創建一個超過「有序集合」的monoid，並使用sort（'sort。（++）'）作爲monoid組合運算符，但「將bsort」制定爲monoid「不是對我來說很清楚 – josejuan

我正在使用我的手機與一個較差的網絡連接，但這裏。

tl; dr bubblesort is insertion sort is monoidal「crush」for the monoid of ordered list with merging。

有序列表形成一個monoid。

newtype OL x = OL [x] 
instance Ord x => Monoid (OL x) where 
    mempty = OL [] 
    mappend (OL xs) (OL ys) = OL (merge xs ys) where 
    merge [] ys = ys 
    merge xs [] = xs 
    merge [email protected](x : xs') [email protected](y : ys') 
     | x <= y = x : merge xs' ys 
     | otherwise = y : merge xs ys'

插入排序由

isort :: Ord x => [x] -> OL x 
isort = foldMap (OL . pure)

給出，因爲插入合併正好與另一個列表中的單列表。（Mergesort是通過構建一棵平衡樹給出的，然後做同樣的foldMap。）

這與bubblesort有什麼關係？插入排序和bubblesort具有完全相同的比較策略。如果您將其作爲從比較和交換框構成的排序網絡，則可以看到這一點。這裏，數據向盒向下和下部輸入流[n]的去左：

| | | | 
[1] | | 
| [2] | 
[3] [4] 
| [5] | 
[6] | | 
| | | |

如果通過上述的編號所給的順序進行比較，切斷的圖中/片，則得到插入排序：所述第一次插入不需要比較;第二需要比較1;第三個2,3;最後4,5,6。

但是相反，如果你在\切片切...

| | | | 
[1] | | 
| [2] | 
[4] [3] 
| [5] | 
[6] | | 
| | | |

...你正在做的冒泡排序：先通過1,2,3;第二通4,5;最後一遍6.

來源

2014-02-19 11:26:32 pigworker

你可以將Bubble排序爲幺半羣或半羣嗎？

回答

相關問題