Sorting

In the previous article, I discussed the brief idea behind quicksort. However, I wasn’t clear about the details, therefore creating much trouble for my own implementation of the quick sort. This article will build on top of the ideas discussed in the previous article. More specifically, it will focus more on the details of the implementation of quick sort. Specifically, we shall be discussing quicksort with 3-way partitioning. I also have to give a shout out to my friends Anis and Bruce....

I apologize for the poor quality of this article. To be honest, writing this article was a huge mess. I spent a lot of time writing the article, but then I realized that I didn’t really get the details right. The idea was correct, but I vaguely described the implementation. When I went on to write the code, I realized that quick sort is actually all about details. Vaguely understanding the idea of quicksort makes it hard to implement it correctly – I spent hours debugging my code....

Idea One way of sorting a list is that we iterate through the list, and for every iteration, we pick out the least item and move it to the front. Suppose below is the list that we want to sort. 1 9 7 5 4 6 8 10 3 2 Firstly, we find out the least item in the entire list through iteration. In this case, the least item is $1$, which happens to be the first item of the list....

Suppose that we are given the following list: 1 9 7 5 4 6 8 10 3 2 The idea of bubble sort is that we iterate through the entire list several times, and for each time, we swap the adjacent values if their relative position is not correct. So, for the first iteration, we start looking at 1 and 9, and find out that their relative position is correct. We then go on to look at 9 and 7, and find that their relative position is incorrect....

In merge sort, our goal was to make sure that the first $i$ items are sorted and are the least items. However, the process of finding the least item in each iteration is actually quite expensive - you’ll have to iterate through the whole least. Hence, an alternative idea would be to simply make sure that the first $i$ items are sorted, and nothing more. Therefore, we do not need to search for the least item....

This week’s lectures mainly focused on the different sorting techniques. Below is a table detailing the techniques. Technique Big-Omega Big-Theta Big-O Bubble Sort $O(n)$ $O(n^2)$ $O(n^2)$ Selection Sort $O(n^2)$ $O(n^2)$ $O(n^2)$ Insertion Sort $O(n)$ $O(n^2)$ $O(n^2)$ Merge Sort $O(n\log n)$ $O(n\log n)$ $O(n\log n)$

Suppose we have a list 1 9 7 5 4 6 8 10 3 2 and our goal is to sort the list. Merge sort’s idea is to divide the list into small segments and recombine them. Here, we have the list sorted. Code Java Implementation public class MergeSort{ public void sort(int[] nums) { copy(nums, _sort(nums));; } static void copy(int[] arr1, int[] arr2) { assert arr1.length == arr2.length: "trying to copy two arrays that do not have the same size"; for (int i = 0; i < arr1....