【舌尖上的演算法】Day11 -- Decrease and Conquer - Shell Sort

2020 IT邦鐵人賽

Posted by Hank Lee on Friday, September 18, 2020

2 Minutes Read

Table of Contents

本系列文章同步分享於IT邦幫忙第12屆鐵人賽

前言

第十天我們第一次介紹了Decrease and Conquer類別的運作方式,同時也介紹了Insertion Sort,小複習一下,Insertion Sort就是大部分人在玩撲克牌時針對手牌進行排序的方式,而今天我們來介紹Insertion Sort的進化版 – Shell Sort。


Shell Sort如何改善Insertion Sort?

Shell Sort是針對目標陣列再次進行Decrease的動作,將陣列以預先定義好的區間的數值進行比較,針對這幾個指定位置的數值排序,當此利用此區間進行排序完成後,再將區間縮小,反覆之前的動作,直到區間已經無法縮小(最小區間為3)後,再進行原先的Insertion Sort。

文字實在有點難形容這個過程,我們直接來看GIF吧:

Shell Sort

從GIF中可以看到,我們一開始從1+5的倍數的位置(1, 6, 11, 16, 21, …)開始進行排序,並僅在這幾個位置進行數值的交換,當利用5的倍數作為依據將陣列排序後,改成使用3的倍數的位置再排序一次,結束之後,因為3的倍數基本上已經是最小單位了,因此我們就直接針對這個已經排序兩次的陣列進行InSertion Sort,就可以得到結果啦。

而如何決定這個幾的倍數是一個一直被大家廣泛討論的問題,但是有一個已知數列可以讓Shell Sort執行效率還不錯:1, 4, 13, 40, 121, 364,...(3x+1)

x為『前一個數』


Shell Sort的時間複雜度

當我們使用上方數列(1, 4, 13, 40, 121, 364,…(3x+1))作為Shell Sort的依據時,Worst case的時間複雜度為𝜪(n^(3/2));而且Shell Sort本身是一個Unstable Sorting,原因是因為他的排序某程度而言,並沒有照著數值原先順序進行一個一個排序,Shell Sort的排序方式有點像跳棋,所以有可能當兩個數值一樣,但後面的數值會被往前移動而跳過原先排在前面且值相同的數值,有興趣的人可以試著畫圖試試看。


小結

  • Shell Sort是進化版的Insertion Sort。
  • 讓Shell Sort執行效率還不錯的數列:1, 4, 13, 40, 121, 364,...(3x+1)
  • Shell Sort若使用上方數列,其Worst case的時間複雜度為𝜪(n^(3/2))
  • Shell Sort是Unstable Sorting

預告

明天我們將會介紹的是Binary Search。


References

  1. Introduction to the Design and Analysis of Algorithms, 3rd Edition, by Anany Levitin