Sorting algorithm: Difference between revisions

Revision as of 19:38, 7 November 2009

Revision as of 07:11, 9 November 2009

Line 50:

{|class="wikitable sortable"

!Name !! Average !! Worst !! Memory !! Stable !! Method !! width="350"|Other notes

|- align="center"

|[[Bubble sort]]

Line 58:

|style="background:#ddffdd"| Yes

|| Exchanging

|nowrap align=left|

|- align="center"

|[[Cocktail sort]]

Line 66:

|style="background:#ddffdd"| Yes

|| Exchanging

|nowrap align=left|

|- align="center"

|[[Comb sort]]

Line 74:

|style="background:#ffdddd"| No

|| Exchanging

|nowrap align="left"|Small code size

|- align="center"

|[[Gnome sort]]

Line 82:

|style="background:#ddffdd"| Yes

|| Exchanging

|nowrap align=left| Tiny code size

|- align="center"

|[[Selection sort]]

Line 90:

|style="background:#ffdddd"| No

|| Selection

|nowrap align=left| Its stability depends on the implementation.

|- align="center"

|[[Insertion sort]]

Line 98:

|style="background:#ddffdd"| Yes

|| Insertion

|nowrap align=left| Average case is also <math>\mathcal{O}\left( {n + d} \right)</math>, where ''d'' is the number of [[Permutation_groups#Transpositions.2C_simple_transpositions.2C_inversions_and_sorting|inversions]]

|- align="center"

|[[Shell sort]]

Line 106:

|style="background:#ffdddd"| No

|| Insertion

|nowrap align=left|

|- align="center"

|[[Binary tree sort]]

Line 114:

|style="background:#ddffdd"| Yes

|| Insertion

|nowrap align="left"| When using a [[self-balancing binary search tree]]

|- align="center"

|[[Library sort]]

Line 122:

|style="background:#ddffdd"| Yes

|| Insertion

|nowrap align=left|

|- align="center"

|[[Merge sort]]

Line 130:

|style="background:#ddffdd"| Yes

|| Merging

|nowrap align=left|

|- align="center"

|nowrap|[[In-place]] [[merge sort]]

Line 138:

|style="background:#ffdddd"| No

|| Merging

|nowrap align="left"| Example implementation here: [http://citeseer.ist.psu.edu/472101.html]; can be implemented as a stable sort based on stable in-place merging: [http://comjnl.oxfordjournals.org/cgi/content/abstract/35/6/643]

|- align="center"

|[[Heapsort]]

Line 146:

|style="background:#ffdddd"| No

|| Selection

|nowrap align=left|

|- align="center"

|[[Smoothsort]]

Line 154:

|style="background:#ffdddd"| No

|| Selection

|nowrap align=left|An [[adaptive sort]] - <math>\mathcal{O}\left( {n} \right)</math> comparisons when the data is already sorted, and <math>\mathcal{O}\left( {0} \right)</math> swaps.

|- align="center"

|[[Quicksort]]

Line 162:

|style="background:#ffdddd"| No

|| Partitioning

|nowrap align="left"| [[Naïve algorithm|Naïve]] variants use <math> \mathcal{O} \left( n \right) </math> space

|- align="center"

|[[Introsort]]

Line 170:

|style="background:#ffdddd"| No

|| Hybrid

|nowrap align="left"| Used in [[Silicon Graphics|SGI]] [[Standard Template Library|STL]] implementations

|- align="center"

|[[Patience sorting]]

Line 178:

|style="background:#ffdddd"| No

|| Insertion & Selection

|nowrap align=left| Finds all the [[longest increasing subsequence]]s within O(''n'' log ''n'')

|- align="center"

|[[Strand sort]]

Line 186:

|style="background:#ddffdd"| Yes

|| Selection

|nowrap align=left|

|- align="center"

|[[Tournament sort]]

Line 194:

|

|| Selection

|nowrap align=left|

|}