(* Content-type: application/mathematica *) (*** Wolfram Notebook File ***) (* http://www.wolfram.com/nb *) (* CreatedBy='Mathematica 7.0' *) (*CacheID: 234*) (* Internal cache information: NotebookFileLineBreakTest NotebookFileLineBreakTest NotebookDataPosition[ 145, 7] NotebookDataLength[ 29219, 800] NotebookOptionsPosition[ 28733, 779] NotebookOutlinePosition[ 29072, 794] CellTagsIndexPosition[ 29029, 791] WindowFrame->Normal*) (* Beginning of Notebook Content *) Notebook[{ Cell[BoxData[ RowBox[{ RowBox[{"(*", " ", RowBox[{ "any", " ", "code", " ", "herein", " ", "that", " ", "is", " ", "not", " ", "covered", " ", "by", " ", "license", " ", "terms", " ", "as", " ", "indicated", " ", "or", " ", "as", " ", "stated", " ", "on", " ", "the", " ", "source", " ", "website", " ", "is", " ", "hereby", " ", "released", " ", "into", " ", "the", " ", "public", " ", "domain"}], " ", "*)"}], "\[IndentingNewLine]", RowBox[{ RowBox[{ RowBox[{ RowBox[{"nTrials", "[", RowBox[{"sortFunc_", ",", "n_"}], "]"}], ":=", RowBox[{ RowBox[{ RowBox[{"(", RowBox[{ RowBox[{ RowBox[{"{", RowBox[{ RowBox[{"#", "[", RowBox[{"[", "1", "]"}], "]"}], ",", RowBox[{"Round", "[", RowBox[{ RowBox[{ RowBox[{ RowBox[{"#", "[", RowBox[{"[", "2", "]"}], "]"}], "/", "n"}], " ", "100"}], ",", "2"}], "]"}]}], "}"}], "&"}], "/@", "#"}], ")"}], "&"}], "/@", RowBox[{"Sort", "/@", RowBox[{"Tally", "/@", RowBox[{"Transpose", "[", RowBox[{"Table", "[", RowBox[{ RowBox[{"sortFunc", "[", RowBox[{ RowBox[{"{", RowBox[{"0", ",", "1", ",", "2", ",", "3", ",", "4"}], "}"}], ",", RowBox[{ RowBox[{"(", RowBox[{ RowBox[{"RandomInteger", "[", "1", "]"}], "\[Equal]", "1"}], ")"}], "&"}]}], "]"}], ",", RowBox[{"{", RowBox[{"t", ",", "1", ",", "n"}], "}"}]}], "]"}], "]"}]}]}]}]}], ";", RowBox[{ RowBox[{"millionTrials", "[", "sortFunc_", "]"}], ":=", RowBox[{"nTrials", "[", RowBox[{"sortFunc", ",", "1000000"}], "]"}]}], ";", RowBox[{"(*", RowBox[{"--", RowBox[{"--", RowBox[{"--", RowBox[{"--", RowBox[{"--", RowBox[{"--", RowBox[{"--", RowBox[{"--", RowBox[{"--", RowBox[{"--", RowBox[{"--", RowBox[{"--", RowBox[{"--", RowBox[{"--", RowBox[{"--", RowBox[{"--", RowBox[{"--", RowBox[{"--", RowBox[{"--", RowBox[{"--", RowBox[{"--", RowBox[{"--", RowBox[{"--", RowBox[{"--", RowBox[{"--", RowBox[{"--", RowBox[{"--", RowBox[{"--", RowBox[{"--", RowBox[{ "--", "--"}]}]}]}]}]}]}]}]}]}]}]}]}]}]}]}]}]}]}]}]}]}]}]}]\ }]}]}]}]}]}], "*)"}], "\[IndentingNewLine]", RowBox[{"(*", " ", RowBox[{ RowBox[{ RowBox[{"from", " ", RowBox[{"http", ":"}]}], "//", RowBox[{ RowBox[{ RowBox[{ RowBox[{ RowBox[{"rosettacode", ".", "org"}], "/", "wiki"}], "/", "Sorting_algorithms"}], "/", "Bubble_sort"}], "#", "Mathematica", " ", RowBox[{"(", RowBox[{"GNU", " ", "FDL"}], ")"}]}]}], ",", " ", RowBox[{ "modified", " ", "to", " ", "take", " ", "arbitrary", " ", "comparison", " ", "function"}]}], " ", "*)"}], RowBox[{ RowBox[{"BubbleSort", "[", RowBox[{"input_", ",", "fn_"}], "]"}], ":=", RowBox[{"input", "//.", RowBox[{ RowBox[{ RowBox[{"{", RowBox[{"a___", ",", "i_", ",", "j_", ",", "b___"}], "}"}], "/;", RowBox[{"fn", "[", RowBox[{"j", ",", "i"}], "]"}]}], "\[RuleDelayed]", RowBox[{"{", RowBox[{"a", ",", "j", ",", "i", ",", "b"}], "}"}]}]}]}], ";"}], "\[IndentingNewLine]", RowBox[{"(*", RowBox[{"--", RowBox[{"--", RowBox[{"--", RowBox[{"--", RowBox[{"--", RowBox[{"--", RowBox[{"--", RowBox[{"--", RowBox[{"--", RowBox[{"--", RowBox[{"--", RowBox[{"--", RowBox[{"--", RowBox[{"--", RowBox[{"--", RowBox[{"--", RowBox[{"--", RowBox[{"--", RowBox[{"--", RowBox[{"--", RowBox[{"--", RowBox[{"--", RowBox[{"--", RowBox[{"--", RowBox[{"--", RowBox[{"--", RowBox[{"--", RowBox[{"--", RowBox[{"--", RowBox[{ "--", "--"}]}]}]}]}]}]}]}]}]}]}]}]}]}]}]}]}]}]}]}]}]}]}]}]\ }]}]}]}]}]}], "*)"}], "\[IndentingNewLine]", RowBox[{"(*", RowBox[{ RowBox[{"Copyright", " ", RowBox[{"(", "c", ")"}], " ", "2010", " ", "the", " ", "authors", " ", "listed", " ", "at", " ", "the", " ", "following", " ", "URL"}], ",", RowBox[{ RowBox[{ RowBox[{ RowBox[{"and", "/", "or"}], " ", "the", " ", "authors", " ", "of", " ", "referenced", " ", "articles", " ", "or", " ", "incorporated", " ", "external", " ", RowBox[{"code", ":", RowBox[{"http", ":"}]}]}], "//", RowBox[{ RowBox[{ RowBox[{"en", ".", "literateprograms", ".", "org"}], "/", "Quicksort_"}], RowBox[{ RowBox[{"(", "Mathematica", ")"}], "?", "action"}]}]}], "=", RowBox[{ RowBox[{ RowBox[{"history", "&"}], "offset"}], "=", RowBox[{ "20060512235643", " ", "Permission", " ", "is", " ", "hereby", " ", "granted"}]}]}], ",", RowBox[{"free", " ", "of", " ", "charge"}], ",", RowBox[{ "to", " ", "any", " ", "person", " ", "obtaining", " ", "a", " ", "copy", " ", "of", " ", "this", " ", "software", " ", "and", " ", "associated", " ", "documentation", " ", "files", " ", RowBox[{"(", RowBox[{"the", " ", "\"\\""}], ")"}]}], ",", RowBox[{ "to", " ", "deal", " ", "in", " ", "the", " ", "Software", " ", "without", " ", "restriction"}], ",", RowBox[{ "including", " ", "without", " ", "limitation", " ", "the", " ", "rights", " ", "to", " ", "use"}], ",", "copy", ",", "modify", ",", "merge", ",", "publish", ",", "distribute", ",", "sublicense", ",", RowBox[{ RowBox[{"and", "/", "or"}], " ", "sell", " ", "copies", " ", "of", " ", "the", " ", "Software"}], ",", RowBox[{ "and", " ", "to", " ", "permit", " ", "persons", " ", "to", " ", "whom", " ", "the", " ", "Software", " ", "is", " ", "furnished", " ", "to", " ", "do", " ", "so"}], ",", RowBox[{"subject", " ", "to", " ", "the", " ", "following", " ", RowBox[{"conditions", ":", RowBox[{ "The", " ", "above", " ", "copyright", " ", "notice", " ", "and", " ", "this", " ", "permission", " ", "notice", " ", "shall", " ", "be", " ", "included", " ", "in", " ", "all", " ", "copies", " ", "or", " ", "substantial", " ", "portions", " ", "of", " ", "the", " ", RowBox[{"Software", ".", "THE"}], " ", "SOFTWARE", " ", "IS", " ", "PROVIDED", " ", "\"\\""}]}]}], ",", RowBox[{"WITHOUT", " ", "WARRANTY", " ", "OF", " ", "ANY", " ", "KIND"}], ",", RowBox[{"EXPRESS", " ", "OR", " ", "IMPLIED"}], ",", RowBox[{ "INCLUDING", " ", "BUT", " ", "NOT", " ", "LIMITED", " ", "TO", " ", "THE", " ", "WARRANTIES", " ", "OF", " ", "MERCHANTABILITY"}], ",", RowBox[{ "FITNESS", " ", "FOR", " ", "A", " ", "PARTICULAR", " ", "PURPOSE", " ", "AND", " ", RowBox[{"NONINFRINGEMENT", ".", "IN"}], " ", "NO", " ", "EVENT", " ", "SHALL", " ", "THE", " ", "AUTHORS", " ", "OR", " ", "COPYRIGHT", " ", "HOLDERS", " ", "BE", " ", "LIABLE", " ", "FOR", " ", "ANY", " ", "CLAIM"}], ",", RowBox[{"DAMAGES", " ", "OR", " ", "OTHER", " ", "LIABILITY"}], ",", RowBox[{ "WHETHER", " ", "IN", " ", "AN", " ", "ACTION", " ", "OF", " ", "CONTRACT"}], ",", RowBox[{"TORT", " ", "OR", " ", "OTHERWISE"}], ",", RowBox[{"ARISING", " ", "FROM"}], ",", RowBox[{ RowBox[{ RowBox[{ "OUT", " ", "OF", " ", "OR", " ", "IN", " ", "CONNECTION", " ", "WITH", " ", "THE", " ", "SOFTWARE", " ", "OR", " ", "THE", " ", "USE", " ", "OR", " ", "OTHER", " ", "DEALINGS", " ", "IN", " ", "THE", " ", RowBox[{"SOFTWARE", ".", "Retrieved"}], " ", RowBox[{"from", ":", RowBox[{"http", ":"}]}]}], "//", RowBox[{ RowBox[{ RowBox[{"en", ".", "literateprograms", ".", "org"}], "/", "Quicksort_"}], RowBox[{ RowBox[{"(", "Mathematica", ")"}], "?", "oldid"}]}]}], "=", "4625"}], ",", " ", RowBox[{ "modified", " ", "to", " ", "take", " ", "arbitrary", " ", "comparison", " ", "function"}]}], " ", "*)"}], RowBox[{ RowBox[{ RowBox[{"QuickSort", "[", RowBox[{"list_", ",", " ", "fn_"}], "]"}], ":=", RowBox[{"Block", "[", RowBox[{ RowBox[{"{", RowBox[{"list2", ",", "pivot", ",", "pivotidx"}], "}"}], ",", RowBox[{"If", "[", RowBox[{ RowBox[{ RowBox[{"Length", "[", "list", "]"}], ">", "1"}], ",", RowBox[{"(", RowBox[{ RowBox[{"pivotidx", "=", RowBox[{"Random", "[", RowBox[{"Integer", ",", RowBox[{"{", RowBox[{"1", ",", RowBox[{"Length", "[", "list", "]"}]}], "}"}]}], "]"}]}], ";", "\[IndentingNewLine]", RowBox[{"pivot", "=", RowBox[{"list", "[", RowBox[{"[", "pivotidx", "]"}], "]"}]}], ";", "\[IndentingNewLine]", RowBox[{"list2", "=", RowBox[{"Delete", "[", RowBox[{"list", ",", "pivotidx"}], "]"}]}], ";", RowBox[{"Block", "[", RowBox[{ RowBox[{"{", RowBox[{"left", "=", RowBox[{"Select", "[", RowBox[{"list2", ",", RowBox[{ RowBox[{"fn", "[", RowBox[{"#", ",", "pivot"}], "]"}], "&"}]}], "]"}]}], "}"}], ",", "\[IndentingNewLine]", RowBox[{"Join", "[", RowBox[{ RowBox[{"QuickSort", "[", RowBox[{"left", ",", "fn"}], "]"}], ",", RowBox[{"List", "[", "pivot", "]"}], ",", RowBox[{"QuickSort", "[", RowBox[{ RowBox[{"Complement", "[", RowBox[{"list2", ",", "left"}], "]"}], ",", "fn"}], "]"}]}], "]"}]}], "]"}]}], ")"}], ",", RowBox[{"(*", "else", "*)"}], "list"}], "]"}]}], "]"}]}], ";", RowBox[{"(*", RowBox[{"--", RowBox[{"--", RowBox[{"--", RowBox[{"--", RowBox[{"--", RowBox[{"--", RowBox[{"--", RowBox[{"--", RowBox[{"--", RowBox[{"--", RowBox[{"--", RowBox[{"--", RowBox[{"--", RowBox[{"--", RowBox[{"--", RowBox[{"--", RowBox[{"--", RowBox[{"--", RowBox[{"--", RowBox[{"--", RowBox[{"--", RowBox[{"--", RowBox[{"--", RowBox[{"--", RowBox[{"--", RowBox[{"--", RowBox[{"--", RowBox[{"--", RowBox[{"--", RowBox[{ "--", "--"}]}]}]}]}]}]}]}]}]}]}]}]}]}]}]}]}]}]}]}]}]}]}]}]\ }]}]}]}]}]}], "*)"}], RowBox[{"(*", " ", RowBox[{ RowBox[{ RowBox[{"based", " ", "on", " ", "code", " ", "in", " ", RowBox[{"http", ":"}]}], "//", RowBox[{ RowBox[{"books", ".", "google", ".", "com"}], "/", RowBox[{"books", "?", "id"}]}]}], "=", RowBox[{ RowBox[{ RowBox[{"OuzV1M7b0WIC", "&"}], "pg"}], "=", RowBox[{ RowBox[{ RowBox[{"PA198", "&"}], "lpg"}], "=", RowBox[{ RowBox[{ RowBox[{"PA198", "&"}], "dq"}], "=", RowBox[{ RowBox[{ RowBox[{ RowBox[{"mathematica", "+", "mergesort"}], "&"}], "source"}], "=", RowBox[{ RowBox[{ RowBox[{"bl", "&"}], "ots"}], "=", RowBox[{ RowBox[{ RowBox[{ RowBox[{"HB3j", "-", "gHceJ"}], "&"}], "sig"}], "=", RowBox[{ RowBox[{ RowBox[{"AAR1abNZMDL9OmWrN6jutM18sZQ", "&"}], "hl"}], "=", RowBox[{ RowBox[{ RowBox[{"en", "&"}], "ei"}], "=", RowBox[{ RowBox[{ RowBox[{"GX2FS8q3CIqmNubjyTQ", "&"}], "sa"}], "=", RowBox[{ RowBox[{ RowBox[{"X", "&"}], "oi"}], "=", RowBox[{ RowBox[{ RowBox[{"book_result", "&"}], "ct"}], "=", RowBox[{ RowBox[{ RowBox[{"result", "&"}], "resnum"}], "=", RowBox[{ RowBox[{ RowBox[{"7", "&"}], "ved"}], "=", RowBox[{ RowBox[{"0", "CCIQ6AEwBg", "#", "v"}], "=", RowBox[{ RowBox[{ RowBox[{"onepage", "&"}], "q"}], "=", RowBox[{ RowBox[{ RowBox[{ RowBox[{"mathematica", "%20", "mergesort"}], "&"}], "f"}], "=", "false"}]}]}]}]}]}]}]}]}]}]}]}]}]}]}]}]}], " ", "*)"}], "\[IndentingNewLine]", RowBox[{ RowBox[{"mergeList", "[", RowBox[{"lis_List", ",", RowBox[{"{", "}"}], ",", "fn_"}], "]"}], ":=", "lis"}], ";", RowBox[{ RowBox[{"mergeList", "[", RowBox[{ RowBox[{"{", "}"}], ",", "lis_List", ",", "fn_"}], "]"}], ":=", "lis"}], ";", RowBox[{ RowBox[{"mergeList", "[", RowBox[{ RowBox[{"{", RowBox[{"a_", ",", "ra___"}], "}"}], ",", RowBox[{"{", RowBox[{"b_", ",", "rb___"}], "}"}], ",", "fn_"}], "]"}], ":=", RowBox[{"If", "[", RowBox[{ RowBox[{"fn", "[", RowBox[{"a", ",", "b"}], "]"}], ",", RowBox[{"Join", "[", RowBox[{ RowBox[{"{", "a", "}"}], ",", RowBox[{"mergeList", "[", RowBox[{ RowBox[{"{", "ra", "}"}], ",", RowBox[{"{", RowBox[{"b", ",", "rb"}], "}"}], ",", "fn"}], "]"}]}], "]"}], ",", RowBox[{"Join", "[", RowBox[{ RowBox[{"{", "b", "}"}], ",", RowBox[{"mergeList", "[", RowBox[{ RowBox[{"{", RowBox[{"a", ",", "ra"}], "}"}], ",", RowBox[{"{", "rb", "}"}], ",", "fn"}], "]"}]}], "]"}]}], "]"}]}], ";", RowBox[{ RowBox[{"MergeSort", "[", RowBox[{ RowBox[{"{", "}"}], ",", "fn_"}], "]"}], ":=", RowBox[{"{", "}"}]}], ";", RowBox[{ RowBox[{"MergeSort", "[", RowBox[{ RowBox[{"{", "x_", "}"}], ",", "fn_"}], "]"}], ":=", RowBox[{"{", "x", "}"}]}], ";", RowBox[{ RowBox[{"MergeSort", "[", RowBox[{"lis_List", ",", "fn_"}], "]"}], ":=", RowBox[{"Module", "[", RowBox[{ RowBox[{"{", RowBox[{"div", "=", RowBox[{"Floor", "[", RowBox[{ RowBox[{"Length", "[", "lis", "]"}], "/", "2"}], "]"}]}], "}"}], ",", RowBox[{"mergeList", "[", RowBox[{ RowBox[{"MergeSort", "[", RowBox[{ RowBox[{"Take", "[", RowBox[{"lis", ",", "div"}], "]"}], ",", "fn"}], "]"}], ",", RowBox[{"MergeSort", "[", RowBox[{ RowBox[{"Drop", "[", RowBox[{"lis", ",", "div"}], "]"}], ",", "fn"}], "]"}], ",", "fn"}], "]"}]}], "]"}]}], ";"}], "\[IndentingNewLine]", RowBox[{"(*", RowBox[{"--", RowBox[{"--", RowBox[{"--", RowBox[{"--", RowBox[{"--", RowBox[{"--", RowBox[{"--", RowBox[{"--", RowBox[{"--", RowBox[{"--", RowBox[{"--", RowBox[{"--", RowBox[{"--", RowBox[{"--", RowBox[{"--", RowBox[{"--", RowBox[{"--", RowBox[{"--", RowBox[{"--", RowBox[{"--", RowBox[{"--", RowBox[{"--", RowBox[{"--", RowBox[{"--", RowBox[{"--", RowBox[{"--", RowBox[{"--", RowBox[{"--", RowBox[{"--", RowBox[{ "--", "--"}]}]}]}]}]}]}]}]}]}]}]}]}]}]}]}]}]}]}]}]}]}]}]}]\ }]}]}]}]}]}], "*)"}], "\[IndentingNewLine]", RowBox[{"(*", " ", RowBox[{ RowBox[{ "Combinatorica", " ", "provides", " ", "SelectionSort", " ", "and", " ", "HeapSort"}], ",", " ", RowBox[{"but", " ", "HeapSort", " ", RowBox[{"doesn", "'"}], "t", " ", "take", " ", "a", " ", "comparison", " ", "function"}]}], " ", "*)"}], RowBox[{ RowBox[{"<<", "Combinatorica`"}], ";"}], "\[IndentingNewLine]", RowBox[{"(*", RowBox[{"--", RowBox[{"--", RowBox[{"--", RowBox[{"--", RowBox[{"--", RowBox[{"--", RowBox[{"--", RowBox[{"--", RowBox[{"--", RowBox[{"--", RowBox[{"--", RowBox[{"--", RowBox[{"--", RowBox[{"--", RowBox[{"--", RowBox[{"--", RowBox[{"--", RowBox[{"--", RowBox[{"--", RowBox[{"--", RowBox[{"--", RowBox[{"--", RowBox[{"--", RowBox[{"--", RowBox[{"--", RowBox[{"--", RowBox[{"--", RowBox[{"--", RowBox[{"--", RowBox[{ "--", "--"}]}]}]}]}]}]}]}]}]}]}]}]}]}]}]}]}]}]}]}]}]}]}]}]\ }]}]}]}]}]}], "*)"}], RowBox[{"(*", " ", RowBox[{ RowBox[{"NOTE", ":", " ", RowBox[{ "BubbleSort", " ", "fails", " ", "when", " ", "there", " ", "are", " ", "duplicate", " ", "elements"}]}], ";", " ", RowBox[{ "QuickSort", " ", "may", " ", "remove", " ", "duplicate", " ", "elements", " ", "at", " ", "random"}]}], " ", "*)"}]}]}]], "Input", CellChangeTimes->{{3.476027430540949*^9, 3.476027451859111*^9}, { 3.476029945167507*^9, 3.47602994543552*^9}, {3.4760299955106277`*^9, 3.47603006679701*^9}, {3.4760301683673058`*^9, 3.4760302123503532`*^9}, { 3.476030279798594*^9, 3.4760302839842253`*^9}, {3.476030527009468*^9, 3.47603077964806*^9}, {3.476030821639538*^9, 3.47603082221616*^9}, { 3.4760308586068163`*^9, 3.476030897110854*^9}, {3.476030952668653*^9, 3.4760309573002043`*^9}, {3.476031003559286*^9, 3.47603102532694*^9}, { 3.4760320473906717`*^9, 3.476032048087379*^9}, {3.4760320970297203`*^9, 3.476032183285692*^9}}], Cell[CellGroupData[{ Cell[BoxData[ RowBox[{ RowBox[{"testList", "=", RowBox[{"RandomInteger", "[", RowBox[{"100", ",", "10"}], "]"}]}], ";", RowBox[{"Table", "[", RowBox[{ RowBox[{"{", RowBox[{"fn", ",", RowBox[{"fn", "[", RowBox[{"testList", ",", RowBox[{ RowBox[{"OrderedQ", "[", RowBox[{"{", RowBox[{"#1", ",", "#2"}], "}"}], "]"}], "&"}]}], "]"}]}], "}"}], ",", RowBox[{"{", RowBox[{"fn", ",", RowBox[{"{", RowBox[{ "Sort", ",", "BubbleSort", ",", "QuickSort", ",", "MergeSort", ",", "SelectionSort"}], "}"}]}], "}"}]}], "]"}]}]], "Input", CellChangeTimes->{{3.476030245579196*^9, 3.4760302514065104`*^9}, { 3.476031274068308*^9, 3.476031306061891*^9}}], Cell[BoxData[ RowBox[{"{", RowBox[{ RowBox[{"{", RowBox[{"Sort", ",", RowBox[{"{", RowBox[{ "7", ",", "32", ",", "41", ",", "49", ",", "52", ",", "57", ",", "66", ",", "81", ",", "96", ",", "98"}], "}"}]}], "}"}], ",", RowBox[{"{", RowBox[{"BubbleSort", ",", RowBox[{"{", RowBox[{ "7", ",", "32", ",", "41", ",", "49", ",", "52", ",", "57", ",", "66", ",", "81", ",", "96", ",", "98"}], "}"}]}], "}"}], ",", RowBox[{"{", RowBox[{"QuickSort", ",", RowBox[{"{", RowBox[{ "7", ",", "32", ",", "41", ",", "49", ",", "52", ",", "57", ",", "66", ",", "81", ",", "96", ",", "98"}], "}"}]}], "}"}], ",", RowBox[{"{", RowBox[{"MergeSort", ",", RowBox[{"{", RowBox[{ "7", ",", "32", ",", "41", ",", "49", ",", "52", ",", "57", ",", "66", ",", "81", ",", "96", ",", "98"}], "}"}]}], "}"}], ",", RowBox[{"{", RowBox[{"SelectionSort", ",", RowBox[{"{", RowBox[{ "7", ",", "32", ",", "41", ",", "49", ",", "52", ",", "57", ",", "66", ",", "81", ",", "96", ",", "98"}], "}"}]}], "}"}]}], "}"}]], "Output", CellChangeTimes->{ 3.476030252596303*^9, {3.476030336758738*^9, 3.476030345181306*^9}, { 3.476030457965784*^9, 3.476030473326867*^9}, 3.4760308375310926`*^9, 3.4760313101844263`*^9}] }, Open ]], Cell[CellGroupData[{ Cell[BoxData[ RowBox[{"TableForm", "[", RowBox[{ RowBox[{ RowBox[{"{", RowBox[{ RowBox[{"#", "[", RowBox[{"[", "1", "]"}], "]"}], ",", RowBox[{"Grid", "[", RowBox[{ RowBox[{"Transpose", "[", RowBox[{"Join", "[", RowBox[{ RowBox[{"{", RowBox[{"{", RowBox[{ "\"\<\>\"", ",", "\"\\"", ",", "\"\\"", ",", "\"\\"", ",", "\"\\"", ",", "\"\\""}], "}"}], "}"}], ",", RowBox[{"Transpose", "[", RowBox[{"Join", "[", RowBox[{ RowBox[{"{", RowBox[{"{", RowBox[{"0", ",", "1", ",", "2", ",", "3", ",", "4"}], "}"}], "}"}], ",", RowBox[{"(", RowBox[{ RowBox[{ RowBox[{"(", RowBox[{ RowBox[{ RowBox[{"#", "[", RowBox[{"[", "2", "]"}], "]"}], "&"}], "/@", "#"}], ")"}], "&"}], "/@", RowBox[{"#", "[", RowBox[{"[", "2", "]"}], "]"}]}], ")"}]}], "]"}], "]"}]}], "]"}], "]"}], ",", RowBox[{"Frame", "\[Rule]", "All"}]}], "]"}]}], "}"}], "&"}], "/@", RowBox[{"ParallelTable", "[", RowBox[{ RowBox[{"{", RowBox[{"fn", ",", RowBox[{"millionTrials", "[", "fn", "]"}]}], "}"}], ",", RowBox[{"{", RowBox[{"fn", ",", RowBox[{"{", RowBox[{ "Sort", ",", "BubbleSort", ",", "QuickSort", ",", "MergeSort", ",", "SelectionSort"}], "}"}]}], "}"}]}], "]"}]}], "]"}]], "Input", CellChangeTimes->{{3.476031387256392*^9, 3.476031412324305*^9}, { 3.476031474160199*^9, 3.476031559817968*^9}, {3.476031590777235*^9, 3.476031660719821*^9}, {3.476031801930662*^9, 3.476031896939395*^9}, { 3.476031927035462*^9, 3.476031946741764*^9}, {3.476032233183627*^9, 3.476032242069923*^9}, {3.4760322808505793`*^9, 3.4760322817058783`*^9}}], Cell[BoxData[ TagBox[GridBox[{ {"Sort", TagBox[GridBox[{ {"\<\"\"\>", "0", "1", "2", "3", "4"}, {"\<\"first\"\>", "18", "12", "12", "12", "46"}, {"\<\"second\"\>", "18", "24", "18", "18", "24"}, {"\<\"third\"\>", "20", "20", "26", "20", "12"}, {"\<\"fourth\"\>", "22", "22", "22", "28", "6"}, {"\<\"fifth\"\>", "22", "22", "22", "22", "12"} }, AutoDelete->False, GridBoxFrame->{"Columns" -> {{True}}, "Rows" -> {{True}}}, GridBoxItemSize->{"Columns" -> {{Automatic}}, "Rows" -> {{Automatic}}}], "Grid"]}, {"BubbleSort", TagBox[GridBox[{ {"\<\"\"\>", "0", "1", "2", "3", "4"}, {"\<\"first\"\>", "36", "28", "20", "10", "6"}, {"\<\"second\"\>", "28", "32", "22", "12", "6"}, {"\<\"third\"\>", "20", "22", "32", "18", "10"}, {"\<\"fourth\"\>", "12", "12", "18", "38", "20"}, {"\<\"fifth\"\>", "6", "6", "10", "20", "60"} }, AutoDelete->False, GridBoxFrame->{"Columns" -> {{True}}, "Rows" -> {{True}}}, GridBoxItemSize->{"Columns" -> {{Automatic}}, "Rows" -> {{Automatic}}}], "Grid"]}, {"QuickSort", TagBox[GridBox[{ {"\<\"\"\>", "0", "1", "2", "3", "4"}, {"\<\"first\"\>", "20", "20", "20", "20", "20"}, {"\<\"second\"\>", "20", "20", "20", "20", "20"}, {"\<\"third\"\>", "20", "20", "20", "20", "20"}, {"\<\"fourth\"\>", "20", "20", "20", "20", "20"}, {"\<\"fifth\"\>", "20", "20", "20", "20", "20"} }, AutoDelete->False, GridBoxFrame->{"Columns" -> {{True}}, "Rows" -> {{True}}}, GridBoxItemSize->{"Columns" -> {{Automatic}}, "Rows" -> {{Automatic}}}], "Grid"]}, {"MergeSort", TagBox[GridBox[{ {"\<\"\"\>", "0", "1", "2", "3", "4"}, {"\<\"first\"\>", "24", "24", "26", "12", "12"}, {"\<\"second\"\>", "26", "24", "18", "16", "16"}, {"\<\"third\"\>", "18", "18", "22", "20", "20"}, {"\<\"fourth\"\>", "16", "16", "18", "26", "26"}, {"\<\"fifth\"\>", "16", "16", "18", "26", "26"} }, AutoDelete->False, GridBoxFrame->{"Columns" -> {{True}}, "Rows" -> {{True}}}, GridBoxItemSize->{"Columns" -> {{Automatic}}, "Rows" -> {{Automatic}}}], "Grid"]}, {"SelectionSort", TagBox[GridBox[{ {"\<\"\"\>", "0", "1", "2", "3", "4"}, {"\<\"first\"\>", "6", "6", "12", "26", "50"}, {"\<\"second\"\>", "12", "12", "20", "32", "24"}, {"\<\"third\"\>", "20", "20", "26", "20", "12"}, {"\<\"fourth\"\>", "30", "30", "20", "12", "6"}, {"\<\"fifth\"\>", "30", "30", "20", "12", "6"} }, AutoDelete->False, GridBoxFrame->{"Columns" -> {{True}}, "Rows" -> {{True}}}, GridBoxItemSize->{"Columns" -> {{Automatic}}, "Rows" -> {{Automatic}}}], "Grid"]} }, GridBoxAlignment->{ "Columns" -> {{Left}}, "ColumnsIndexed" -> {}, "Rows" -> {{Baseline}}, "RowsIndexed" -> {}}, GridBoxSpacings->{"Columns" -> { Offset[0.27999999999999997`], { Offset[0.7]}, Offset[0.27999999999999997`]}, "ColumnsIndexed" -> {}, "Rows" -> { Offset[0.2], { Offset[0.4]}, Offset[0.2]}, "RowsIndexed" -> {}}], Function[BoxForm`e$, TableForm[BoxForm`e$]]]], "Output", CellChangeTimes->{{3.476031391668824*^9, 3.476031412740394*^9}, { 3.476031495656117*^9, 3.4760315125512257`*^9}, {3.476031611296451*^9, 3.476031661361497*^9}, 3.476031792708502*^9, 3.476031861813427*^9, 3.476031897611174*^9, 3.476031947591045*^9, 3.476032070948991*^9, 3.476032739937044*^9}] }, Open ]] }, WindowSize->{640, 750}, WindowMargins->{{16, Automatic}, {Automatic, 5}}, FrontEndVersion->"7.0 for Mac OS X x86 (32-bit) (February 18, 2009)", StyleDefinitions->"Default.nb" ] (* End of Notebook Content *) (* Internal cache information *) (*CellTagsOutline CellTagsIndex->{} *) (*CellTagsIndex CellTagsIndex->{} *) (*NotebookFileOutline Notebook[{ Cell[545, 20, 20229, 546, 1108, "Input"], Cell[CellGroupData[{ Cell[20799, 570, 771, 23, 58, "Input"], Cell[21573, 595, 1366, 36, 88, "Output"] }, Open ]], Cell[CellGroupData[{ Cell[22976, 636, 2093, 54, 118, "Input"], Cell[25072, 692, 3645, 84, 585, "Output"] }, Open ]] } ] *) (* End of internal cache information *)