{"id":26,"date":"2023-02-10T12:19:04","date_gmt":"2023-02-10T12:19:04","guid":{"rendered":"https:\/\/blogs.oregonstate.edu\/easterdr\/?p=26"},"modified":"2023-02-10T12:19:04","modified_gmt":"2023-02-10T12:19:04","slug":"sort-algorithms","status":"publish","type":"post","link":"https:\/\/blogs.oregonstate.edu\/easterdr\/2023\/02\/10\/sort-algorithms\/","title":{"rendered":"Sort Algorithms"},"content":{"rendered":"\n<p>Recently, I worked on a sort visualizer project that displays various sorting algorithms and I will be talking about some of the algorithms I used. <\/p>\n\n\n\n<p>So, what&#8217;s a sort algorithm?<\/p>\n\n\n\n<p><em>A sort algorithm is used to arrange a given array or list of elements in a specific order.<\/em> <\/p>\n\n\n\n<p>The algorithms I will go over are:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>merge sort<\/li>\n\n\n\n<li>quick sort<\/li>\n\n\n\n<li>bubble sort<\/li>\n\n\n\n<li>tim sort<\/li>\n\n\n\n<li>heap sort<\/li>\n<\/ul>\n\n\n\n<p><strong><em>Merge Sort<\/em><\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>divides an array into smaller subarrays, sorts each subarray and then merges the sorted subarrays back together to form the final sorted array. <\/li>\n<\/ul>\n\n\n\n<p>Let&#8217;s take an example:<\/p>\n\n\n\n<figure class=\"wp-block-image size-full\"><img loading=\"lazy\" decoding=\"async\" width=\"657\" height=\"646\" src=\"https:\/\/osu-wams-blogs-uploads.s3.amazonaws.com\/blogs.dir\/6519\/files\/2023\/02\/image.png\" alt=\"\" class=\"wp-image-28\" srcset=\"https:\/\/osu-wams-blogs-uploads.s3.amazonaws.com\/blogs.dir\/6519\/files\/2023\/02\/image.png 657w, https:\/\/osu-wams-blogs-uploads.s3.amazonaws.com\/blogs.dir\/6519\/files\/2023\/02\/image-300x295.png 300w\" sizes=\"auto, (max-width: 657px) 100vw, 657px\" \/><figcaption class=\"wp-element-caption\">Credit: https:\/\/www.geeksforgeeks.org\/merge-sort\/<\/figcaption><\/figure>\n\n\n\n<figure class=\"wp-block-image\"><img loading=\"lazy\" decoding=\"async\" width=\"802\" height=\"632\" src=\"https:\/\/osu-wams-blogs-uploads.s3.amazonaws.com\/blogs.dir\/6519\/files\/2023\/02\/Screen-Recording-2023-02-10-at-1.54.57-AM.gif\" alt=\"\" class=\"wp-image-29\" \/><figcaption class=\"wp-element-caption\">a visual depiction of merge sort from my project<\/figcaption><\/figure>\n\n\n\n<p><strong><em>QuickSort<\/em><\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Similar to merge sort, quickSort is also a divide and conquer algorithm. It selects a &#8216;pivot&#8217; element from the array and partitions the array around the &#8216;pivot&#8217; element. There are several methods of picking the &#8216;pivot&#8217; element. You can select the first element, last element, random element, or even the median. <\/li>\n<\/ul>\n\n\n\n<figure class=\"wp-block-image size-full\"><img loading=\"lazy\" decoding=\"async\" width=\"703\" height=\"312\" src=\"https:\/\/osu-wams-blogs-uploads.s3.amazonaws.com\/blogs.dir\/6519\/files\/2023\/02\/image-1.png\" alt=\"\" class=\"wp-image-30\" srcset=\"https:\/\/osu-wams-blogs-uploads.s3.amazonaws.com\/blogs.dir\/6519\/files\/2023\/02\/image-1.png 703w, https:\/\/osu-wams-blogs-uploads.s3.amazonaws.com\/blogs.dir\/6519\/files\/2023\/02\/image-1-300x133.png 300w\" sizes=\"auto, (max-width: 703px) 100vw, 703px\" \/><figcaption class=\"wp-element-caption\">Credit: https:\/\/www.geeksforgeeks.org\/quick-sort\/<\/figcaption><\/figure>\n\n\n\n<figure class=\"wp-block-image size-full\"><img loading=\"lazy\" decoding=\"async\" width=\"802\" height=\"632\" src=\"https:\/\/osu-wams-blogs-uploads.s3.amazonaws.com\/blogs.dir\/6519\/files\/2023\/02\/Screen-Recording-2023-02-10-at-3.23.15-AM.gif\" alt=\"\" class=\"wp-image-32\" \/><figcaption class=\"wp-element-caption\">a visual depiction of quickSort from my project<\/figcaption><\/figure>\n\n\n\n<p><strong><em>Bubble sort<\/em><\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>The simplest sorting algorithm that works by repeatedly comparing two adjacent elements and swapping them if they are not in order.<\/li>\n<\/ul>\n\n\n\n<figure class=\"wp-block-image size-full is-resized\"><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/osu-wams-blogs-uploads.s3.amazonaws.com\/blogs.dir\/6519\/files\/2023\/02\/image-2.png\" alt=\"\" class=\"wp-image-33\" width=\"555\" height=\"646\" srcset=\"https:\/\/osu-wams-blogs-uploads.s3.amazonaws.com\/blogs.dir\/6519\/files\/2023\/02\/image-2.png 391w, https:\/\/osu-wams-blogs-uploads.s3.amazonaws.com\/blogs.dir\/6519\/files\/2023\/02\/image-2-258x300.png 258w\" sizes=\"auto, (max-width: 555px) 100vw, 555px\" \/><figcaption class=\"wp-element-caption\">Credit: https:\/\/www.geeksforgeeks.org\/bubble-sort\/<\/figcaption><\/figure>\n\n\n\n<figure class=\"wp-block-image size-full\"><img loading=\"lazy\" decoding=\"async\" width=\"802\" height=\"632\" src=\"https:\/\/osu-wams-blogs-uploads.s3.amazonaws.com\/blogs.dir\/6519\/files\/2023\/02\/Screen-Recording-2023-02-10-at-3.34.07-AM.gif\" alt=\"\" class=\"wp-image-34\" \/><figcaption class=\"wp-element-caption\">a visual depiction of bubble sort from my project<\/figcaption><\/figure>\n\n\n\n<p><strong><em>TimSort<\/em><\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>TimSort is a sorting algorithm adapted from merge sort and insertion sort. The array is broken down into runs. The size of the run varies from 32 to 64 depending on the array size. The merge function performs well when size subarrays are powers of 2. Each run is sorted using insertion sort. Any array with a size smaller than 64 is sorted just using insertion sort. All runs are then merged one by one using merge sort. <\/li>\n\n\n\n<li>A fun fact about timSort is that it is used in Java&#8217;s Array.sort() as well as Python&#8217;s sorted() and sort()<\/li>\n<\/ul>\n\n\n\n<p>In this example, the size of the run is 4.<\/p>\n\n\n\n<figure class=\"wp-block-image size-full\"><img loading=\"lazy\" decoding=\"async\" width=\"765\" height=\"513\" src=\"https:\/\/osu-wams-blogs-uploads.s3.amazonaws.com\/blogs.dir\/6519\/files\/2023\/02\/image-3.png\" alt=\"\" class=\"wp-image-35\" srcset=\"https:\/\/osu-wams-blogs-uploads.s3.amazonaws.com\/blogs.dir\/6519\/files\/2023\/02\/image-3.png 765w, https:\/\/osu-wams-blogs-uploads.s3.amazonaws.com\/blogs.dir\/6519\/files\/2023\/02\/image-3-300x201.png 300w\" sizes=\"auto, (max-width: 765px) 100vw, 765px\" \/><figcaption class=\"wp-element-caption\">Credit: https:\/\/www.educative.io\/answers\/what-is-timsort<\/figcaption><\/figure>\n\n\n\n<figure class=\"wp-block-image size-full\"><img loading=\"lazy\" decoding=\"async\" width=\"802\" height=\"632\" src=\"https:\/\/osu-wams-blogs-uploads.s3.amazonaws.com\/blogs.dir\/6519\/files\/2023\/02\/Screen-Recording-2023-02-10-at-3.51.49-AM-1.gif\" alt=\"\" class=\"wp-image-37\" \/><figcaption class=\"wp-element-caption\">a visual depiction of timSort from my project<\/figcaption><\/figure>\n\n\n\n<p><strong><em>Heap sort<\/em><\/strong><\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Heap Sort sorts an array by building a binary heap data structure from the elements of the array and then repeatedly extracting the maximum element from the heap and moving that to the end of the array, reducing the size of the heap by one each time until the heap is empty.<\/li>\n<\/ul>\n\n\n\n<figure class=\"wp-block-image size-large is-resized\"><img loading=\"lazy\" decoding=\"async\" src=\"https:\/\/osu-wams-blogs-uploads.s3.amazonaws.com\/blogs.dir\/6519\/files\/2023\/02\/image-4-420x1024.png\" alt=\"\" class=\"wp-image-38\" width=\"393\" height=\"958\" srcset=\"https:\/\/osu-wams-blogs-uploads.s3.amazonaws.com\/blogs.dir\/6519\/files\/2023\/02\/image-4-420x1024.png 420w, https:\/\/osu-wams-blogs-uploads.s3.amazonaws.com\/blogs.dir\/6519\/files\/2023\/02\/image-4-123x300.png 123w, https:\/\/osu-wams-blogs-uploads.s3.amazonaws.com\/blogs.dir\/6519\/files\/2023\/02\/image-4-768x1871.png 768w, https:\/\/osu-wams-blogs-uploads.s3.amazonaws.com\/blogs.dir\/6519\/files\/2023\/02\/image-4-631x1536.png 631w, https:\/\/osu-wams-blogs-uploads.s3.amazonaws.com\/blogs.dir\/6519\/files\/2023\/02\/image-4.png 780w\" sizes=\"auto, (max-width: 393px) 100vw, 393px\" \/><figcaption class=\"wp-element-caption\">Credit: https:\/\/www.hackerearth.com\/practice\/algorithms\/sorting\/heap-sort\/tutorial\/<\/figcaption><\/figure>\n\n\n\n<figure class=\"wp-block-image size-full\"><img loading=\"lazy\" decoding=\"async\" width=\"802\" height=\"632\" src=\"https:\/\/osu-wams-blogs-uploads.s3.amazonaws.com\/blogs.dir\/6519\/files\/2023\/02\/Screen-Recording-2023-02-10-at-4.03.04-AM.gif\" alt=\"\" class=\"wp-image-40\" \/><figcaption class=\"wp-element-caption\">a visual depiction of heap sort from my project<\/figcaption><\/figure>\n\n\n\n<p><strong><em>Conclusion<\/em><\/strong><\/p>\n\n\n\n<p>There are many sorting algorithms out there and we didn&#8217;t even cover non-comparison-based sorting algorithms. In this article, we went over several comparison-based sorting algorithms with bubble sort being the most inefficient and quickSort and timSort being the most efficient. I hope this gave you a better understanding and a visual of how sorting algorithms operate. <\/p>\n\n\n\n<p>You can check out my project <a href=\"https:\/\/visualize-alg0.herokuapp.com\/\" data-type=\"URL\" data-id=\"https:\/\/visualize-alg0.herokuapp.com\/\" target=\"_blank\" rel=\"noreferrer noopener\">here<\/a><\/p>\n\n\n\n<p><a href=\"https:\/\/github.com\/RinaMoto\/algovisualizer\" data-type=\"URL\" data-id=\"https:\/\/github.com\/RinaMoto\/algovisualizer\" target=\"_blank\" rel=\"noreferrer noopener\">Github repo<\/a><\/p>\n\n\n\n<p>Thanks for reading!<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Recently, I worked on a sort visualizer project that displays various sorting algorithms and I will be talking about some of the algorithms I used. So, what&#8217;s a sort algorithm? A sort algorithm is used to arrange a given array or list of elements in a specific order. The algorithms I will go over are: [&hellip;]<\/p>\n","protected":false},"author":13207,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[],"class_list":["post-26","post","type-post","status-publish","format-standard","hentry","category-uncategorized"],"_links":{"self":[{"href":"https:\/\/blogs.oregonstate.edu\/easterdr\/wp-json\/wp\/v2\/posts\/26","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/blogs.oregonstate.edu\/easterdr\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/blogs.oregonstate.edu\/easterdr\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/blogs.oregonstate.edu\/easterdr\/wp-json\/wp\/v2\/users\/13207"}],"replies":[{"embeddable":true,"href":"https:\/\/blogs.oregonstate.edu\/easterdr\/wp-json\/wp\/v2\/comments?post=26"}],"version-history":[{"count":2,"href":"https:\/\/blogs.oregonstate.edu\/easterdr\/wp-json\/wp\/v2\/posts\/26\/revisions"}],"predecessor-version":[{"id":41,"href":"https:\/\/blogs.oregonstate.edu\/easterdr\/wp-json\/wp\/v2\/posts\/26\/revisions\/41"}],"wp:attachment":[{"href":"https:\/\/blogs.oregonstate.edu\/easterdr\/wp-json\/wp\/v2\/media?parent=26"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/blogs.oregonstate.edu\/easterdr\/wp-json\/wp\/v2\/categories?post=26"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/blogs.oregonstate.edu\/easterdr\/wp-json\/wp\/v2\/tags?post=26"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}