{"id":123,"date":"2014-03-26T04:07:35","date_gmt":"2014-03-26T12:07:35","guid":{"rendered":"http:\/\/www.tech.dimprash.com\/?p=123"},"modified":"2014-03-26T07:12:35","modified_gmt":"2014-03-26T15:12:35","slug":"sorting-algorithms","status":"publish","type":"post","link":"http:\/\/www.tech.dimprash.com\/?p=123","title":{"rendered":"Sorting Algorithms"},"content":{"rendered":"<p><strong>1) Merge Sort<\/strong><br \/>\n<iframe loading=\"lazy\" title=\"Algorithms Lesson 3: Merge Sort\" width=\"660\" height=\"495\" src=\"https:\/\/www.youtube.com\/embed\/GCae1WNvnZM?feature=oembed\" frameborder=\"0\" allow=\"accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture; web-share\" referrerpolicy=\"strict-origin-when-cross-origin\" allowfullscreen><\/iframe><\/p>\n<p>&#8211; O(n log n) comparison based sorting algorithm (best case, worst case, avg case)<br \/>\n&#8211; Produces a stable sort (implementation preserves the input order of equal elements in the sorted output)<br \/>\n&#8211; Top Down Implementation and Bottom Up Implementation<br \/>\n&#8211; Is more efficient at handling slow-to-access sequential media. Merge sort is often the best choice for sorting a linked list<br \/>\n&#8211; Uses more memory (2n locations)<br \/>\n&#8211; Can be parallelized<\/p>\n<p><strong>2) Quick Sort<\/strong><br \/>\n&#8211; Avg O(n log n) , Worst Case O(n ^ 2)<br \/>\n&#8211; Is comparison based sorting<br \/>\n&#8211; In place partioning algorithm and hence uses O(log n) additional space<br \/>\n&#8211; Can be parallelized (like mergesort)<br \/>\n&#8211; Depending on implementation may or may not be a stable sort<br \/>\n&#8211; Low memory required<br \/>\n&#8211; Useful in cases where data is in RAM, not useful in cases where data lives on disk (In that case use merge sort)<br \/>\n&#8211; usually faster than mergesort<br \/>\n&#8211; The worst-case running time for quicksort is O(n2), which is unacceptable for large data sets and can be deliberately triggered given enough knowledge of the implementation, creating a security risk<\/p>\n<p>QuickSort is more popular than Merge Sort because it:<\/p>\n<p>Is in-place (MergeSort requires tons of extra memory).<br \/>\nHas a small hidden constant<\/p>\n<p><iframe loading=\"lazy\" title=\"Algorithms Lesson 4: Quicksort\" width=\"660\" height=\"495\" src=\"https:\/\/www.youtube.com\/embed\/y_G9BkAm6B8?feature=oembed\" frameborder=\"0\" allow=\"accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture; web-share\" referrerpolicy=\"strict-origin-when-cross-origin\" allowfullscreen><\/iframe><\/p>\n<p><strong>3) Heap Sort<\/strong><br \/>\n<iframe loading=\"lazy\" title=\"Algorithms Lesson 9: Heaps\" width=\"660\" height=\"495\" src=\"https:\/\/www.youtube.com\/embed\/v1YUApMYXO4?feature=oembed\" frameborder=\"0\" allow=\"accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture; web-share\" referrerpolicy=\"strict-origin-when-cross-origin\" allowfullscreen><\/iframe><br \/>\n<iframe loading=\"lazy\" title=\"Algorithms Lesson 10: Heapsort\" width=\"660\" height=\"495\" src=\"https:\/\/www.youtube.com\/embed\/6NB0GHY11Iw?feature=oembed\" frameborder=\"0\" allow=\"accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture; web-share\" referrerpolicy=\"strict-origin-when-cross-origin\" allowfullscreen><\/iframe><\/p>\n<p>&#8211; Heapsort is part of the selection sort family. Is a comparison based sorting algo.<br \/>\n&#8211; it has the advantage of a more favorable worst-case O(n log n) runtime<br \/>\n&#8211; Heapsort is an in-place algorithm, but it is not a stable sort<br \/>\n&#8211; Quicksort is typically faster than Heapsort,  but the worst-case running time for quicksort is O(n2), which is unacceptable for large data sets and can be deliberately triggered given enough knowledge of the implementation, creating a security risk<br \/>\n&#8211; Merge sort requires ?(n) auxiliary space, but heapsort requires only a constant amount. <\/p>\n<p>Merge sort has several advantages over heapsort:<br \/>\nMerge sort on arrays has considerably better data cache performance, often outperforming heapsort on modern desktop computers because merge sort frequently accesses contiguous memory locations (good locality of reference); heapsort references are spread throughout the heap.<br \/>\nHeapsort is not a stable sort; merge sort is stable.<br \/>\nMerge sort parallelizes well and can achieve close to linear speedup with a trivial implementation; heapsort is not an obvious candidate for a parallel algorithm.<br \/>\n4) Intro Sort<\/p>\n","protected":false},"excerpt":{"rendered":"<p>1) Merge Sort &#8211; O(n log n) comparison based sorting algorithm (best case, worst case, avg case) &#8211; Produces a stable sort (implementation preserves the input order of equal elements in the sorted output) &#8211; Top Down Implementation and Bottom Up Implementation &#8211; Is more efficient at handling slow-to-access sequential media. Merge sort is often &hellip; <a href=\"http:\/\/www.tech.dimprash.com\/?p=123\" class=\"more-link\">Continue reading <span class=\"screen-reader-text\">Sorting Algorithms<\/span><\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[],"class_list":["post-123","post","type-post","status-publish","format-standard","hentry","category-uncategorized"],"_links":{"self":[{"href":"http:\/\/www.tech.dimprash.com\/index.php?rest_route=\/wp\/v2\/posts\/123","targetHints":{"allow":["GET"]}}],"collection":[{"href":"http:\/\/www.tech.dimprash.com\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/www.tech.dimprash.com\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/www.tech.dimprash.com\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/www.tech.dimprash.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=123"}],"version-history":[{"count":4,"href":"http:\/\/www.tech.dimprash.com\/index.php?rest_route=\/wp\/v2\/posts\/123\/revisions"}],"predecessor-version":[{"id":127,"href":"http:\/\/www.tech.dimprash.com\/index.php?rest_route=\/wp\/v2\/posts\/123\/revisions\/127"}],"wp:attachment":[{"href":"http:\/\/www.tech.dimprash.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=123"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/www.tech.dimprash.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=123"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/www.tech.dimprash.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=123"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}