Robley Gori

Well-tested and documented code is maintainable and cleaner for the development team. In this article, we'll focus on the Unittest framework and write unit tests for Python code.

Unit Testing in Python with Unittest

Like many other popular languages, JavaScript conveniently comes with a built-in method for sorting arrays. While the end result is the same, the various JavaScript engines implement this method using different sort algorithms:
<ul>
<li>V8: Quicksort or Insertion Sort (for smaller arrays)</li>
<li>Firefox: Merge sort</li>
<li>Safari: Quicksort, Merge Sort, or Selection Sort (depending on the type of array)</li>
</ul>
The implementation doesn't really matter for the calling code, but it's interesting to see these sorting algorithms used in practice after learning about them for so long in CS intro classes.
This sort function is available as a prototype method on the <code>Array</code> class:
<pre><code class="hljs">Array.sort([compareFunc])
</code></pre>
In true JavaScript fashion, a callback is passed to this function which is used to tell the sorting algorithm how two elements compare to each other. The <code>compareFunc</code> should have two parameters, <code>a</code> and <code>b</code>, and works like this:
<ul>
<li>If <code>compareFunc</code> returns 0 then the elements are treated as equal</li>
<li>If <code>compareFunc</code> returns 1 then <code>b</code> is sorted before <code>a</code></li>
<li>If <code>compareFunc</code> returns -1 then <code>a</code> is sorted before <code>b</code></li>
</ul>
The function doesn't necessarily need to return 1 or -1, just as long as the numbers returned are 0, above 0, or below 0. So a comparator function like <code>(a, b) =&gt; a - b;</code> is perfectly valid.
If the <code>compareFunc</code> is not given then the elements are converted to strings and then sorted alphabetically. This makes sorting strings trivial. However, while sorting numbers seems like it should be straight forward, it can actually be a bit confusing here:
<pre><code class="hljs">&gt; let nums = [3, 2, 6, 50, 10];
&gt; nums.sort()
[ 10, 2, 3, 50, 6 ]
</code></pre>
As you can see, the numbers aren't in the order you would have expected. This is because, as mentioned earlier, that the default sorting method is to convert the elements to strings before doing the comparison. And as a string, &quot;50&quot; comes before &quot;6&quot;, which is why 50 isn't last in the array. To sort this array correctly, try the following instead:
<pre><code class="hljs">&gt; let nums = [3, 2, 6, 50, 10];
&gt; nums.sort((a, b) =&gt; a - b);
[ 2, 3, 6, 10, 50 ]
</code></pre>
Note: It's important to keep in mind that this method sorts in-place, which means that the original array is actually sorted and no copy is made. So, while the <code>.sort()</code> method does return the sorted array, you don't actually need to assign it to anything since the array that it is called on is sorted.
If you want to reverse the order of the sorting, just switch around the comparison of <code>a</code> and <code>b</code>. So if we want the numbers to be in descending order, you'd do the following:
<pre><code class="hljs">&gt; let nums = [3, 2, 6, 50, 10];
&gt; nums.sort((a, b) =&gt; b - a);
[ 50, 10, 6, 3, 2 ]
</code></pre>
<h2 id="sortingarrayofobjects">Sorting Array of Objects</h2>
Using a comparator function like this makes it extremely easy to sort custom objects in JavaScript. For example, let's say we have the following list of user data:
<pre><code class="hljs">let users = [
 {name: &#x27;Scotty&#x27;, age: &#x27;18&#x27;},
 {name: &#x27;Tommy&#x27;, age: &#x27;21&#x27;},
 {name: &#x27;Sally&#x27;, age: &#x27;71&#x27;},
 {name: &#x27;Billy&#x27;, age: &#x27;18&#x27;},
 {name: &#x27;Timmy&#x27;, age: &#x27;21&#x27;}
];
</code></pre>
This isn't something that the sorting algorithm can just interpret and sort itself. The order also highly depends on the application. What if we want to sort by age and then name? To do so, we could provide a comparator that combines the two:
<pre><code class="hljs">users.sort((a, b) =&gt; {
 let keyA = a.age + a.name;
 let keyB = b.age + b.name;
 if (keyA &lt; keyB) return -1;
 if (keyA &gt; keyB) return 1;
 return 0;
});
</code></pre>
This will result in the following sorted array:
<pre><code class="hljs">[ { name: 'Billy', age: '18' },
 { name: 'Scotty', age: '18' },
 { name: 'Timmy', age: '21' },
 { name: 'Tommy', age: '21' },
 { name: 'Sally', age: '71' } ]
</code></pre>
Notice that all of the users are now sorted by age. And as intended, those users with the same age are then sorted by name, like Billy and Scotty.
<h2 id="conclusion">Conclusion</h2>
In this short article we saw how to use the built-in <code>.sort()</code> method to easily sort arrays in JavaScript. This applies to any type of data, including strings, numbers, or even objects. The sort order is determined by the <code>compareFun</code> callback method, which is what allows you to determine the sort order or what object properties determine the sort order.

Scott Robinson

Like many other languages, JavaScript offers convenience methods for sorting arrays. While the result is the same, the JavaScript engines implement different algorithms, which we'll cover in this article.

Sorting Arrays in JavaScript

<h2 id="introduction">Introduction</h2>
Sorting is a crucial aspect of digesting data. For us humans, it's much more natural to sort things that have something in common like the date of publishing, alphabetical order, articles belonging to an author, from smallest to largest, etc. This makes it a lot easier to comprehend the data as it's logically connected rather than dispersed all around.
And just as important, sorted arrays are easier for computers to work with. For example, a sorted array can be searched much faster, like with the <a rel="nofollow noopener" target="_blank" href="https://en.wikipedia.org/wiki/Binary_search_algorithm">binary search</a> algorithm, which runs in O(logn) time. An algorithm like this just doesn't work without a sorted array.
<h2 id="insertionsort">Insertion Sort</h2>
Insertion Sort is one of the simpler sorting algorithms, which works considerably faster on smaller collections than the introductory <a target="_blank" href="/bubble-sort-in-java">Bubble Sort</a> and even Selection Sort even though they're all simple quadratic (O(n2) algorithms.
It's great for nearly sorted and small collections (~10 elements) which makes it extremely useful when used in combination with other, more advanced sorting algorithms such as Quicksort or <a target="_blank" href="/merge-sort-in-java">Merge Sort</a>. Java's official <code>sort()</code> implementation from the Collections API used a Dual Pivot Quicksort, though resorted to Insertion Sort for collections of size <code>7</code>.
It is generally implemented imperatively (though it can also be recursive), and represents an in-place, stable algorithm that works wonders on small datasets.
This means that it preserves the relative order of duplicate elements after sorting (in-place) and doesn't require any additional memory for sorting with a constant O(1) space complexity (stable).
Insertion Sort works a lot like humans sort cards in their hands by dividing the collection into two parts - sorted and unsorted.
It then traverses the unsorted partition and inserts each element in their relative correct place in the sorted array.
Here's a visual representation of how it works:
<img src="https://stackabuse.s3.amazonaws.com/media/insertion-sort-in-java.gif" alt="insertion sort gif">
If this doesn't make much sense now, it's explained step-by-step in the implementation below alongside the code.
<h2 id="implementation">Implementation</h2>
That being said, let's go ahead and implement the algorithm on primitive integer arrays and a collection of objects with a custom <code>compareTo()</code> method to define comparison criteria.
We could also implement the <code>Comparable</code> interface and overridde the <code>compareTo()</code> method for defining the comparison criteria, and using the Collections API, simply calling the <code>sort()</code> method provided there. However, that way, we don't implement our own sorting logic.
<h3 id="sortingarrays">Sorting Arrays</h3>
Sorting primitive integer arrays is quick and straightforward using Insertion Sort:
<pre><code class="hljs">public static void insertionSort(int array[]) {
 for (int j = 1; j &lt; array.length; j++) {
 int current = array[j];
 int i = j-1;
 while ((i &gt; -1) &amp;&amp; (array[i] &gt; current)) {
 array[i+1] = array[i];
 i--;
 }
 array[i+1] = current;
 }
}
</code></pre>
The iteration starts on the second element (the first one is by default considered sorted), and compares the first element of the unsorted array with the last element of the sorted array.
The unsorted element is &quot;safe-kept&quot; in the variable <code>current</code> and if the highest element in the sorted array is bigger than the <code>current</code> variable - the adequate portion of the sorted array is shifted to the right.
Please note that they're not swapped, it's shifted to the right and now both <code>array[j]</code> (accessed through <code>array[i+1]</code>) and <code>array[i]</code> hold the same value.
Then, regardless of whether a portion of the sorted array is shifted to the right, we set the <code>array[j]</code> to <code>current</code>, effectively inserting the safe-kept integer into its right place.
If the <code>current</code> element isn't smaller than the biggest sorted element (i.e. it's bigger), it's simply inserted at the end where it belongs.
Let's go ahead and populate a small array of integers and then sort it:
<pre><code class="hljs">int[] array = new int[]{1, 7, 5, 6, 9, 4, 2, 3};
insertionSort(array);
System.out.println(Arrays.toString(array));
</code></pre>
Running this piece of code will yield:
<pre><code class="hljs">[1, 2, 3, 4, 5, 6, 7, 9]
</code></pre>
<h3 id="sortingarraylists">Sorting ArrayLists</h3>
Sorting an <code>ArrayList</code> is a more practical/real-world example that you'll probably encounter a lot more often than primitive integers.
Since we're sorting objects depending on certain criteria, let's first define a class for our <code>Element</code> of a collection:
<pre><code class="hljs">public class Element {
 private int id;

 public Element(int id) {
 this.id = id;
 }

 // Getters and setters

 public int compareTo(Element element) {
 int res = 0;
 if (this.id &lt; element.getId()) {
 res = -1;
 }
 if (this.id &gt; element.getId()) {
 res = 1;
 }
 return res;
 }
}
</code></pre>
It contains a <code>compareTo()</code> method which accepts another <code>Element</code> to be compared to. In this mundane implementation, their <code>id</code>s are being compared, though here is where you can get creative.
Let's rework the algorithm to sort these objects instead:
<pre><code class="hljs">public static void insertionSortArrayList(List&lt;Element&gt; list) {
 for (int j = 1; j &lt; list.size(); j++) {
 Element current = list.get(j);
 int i = j-1;
 while ((i &gt; -1) &amp;&amp; ((list.get(i).compareTo(current)) == 1)) {
 list.set(i+1, list.get(i));
 i--;
 }
 list.set(i+1, current);
 }
}
</code></pre>
Not much has changed, expect for using the methods provided by a <code>List</code> and comparing the elements with our custom <code>compareTo()</code> method. Here, we check if the result of the comparison is <code>1</code> since that means that the first element is bigger than the second as defined in our method.
Now, let's populate an <code>ArrayList</code> with some elements and shuffle it:
<pre><code class="hljs">List&lt;Element&gt; list = new ArrayList&lt;&gt;();

// Create elements w/ IDs 0-24
for (int i = 0; i &lt; 25; i++) {
 list.add(new Element(i));
}

// Move the elements to a random order
Collections.shuffle(list);
</code></pre>
And now, let's sort that list:
<pre><code class="hljs">// Print list before sorting
list.forEach(e -&gt; System.out.print(e.getId() + &quot;, &quot;));

// Sort the list
insertionSortArrayList(list);

System.out.println();

// Print sorted list
list.forEach(e -&gt; System.out.print(e.getId() + &quot;, &quot;));
</code></pre>
This piece of code will yield us:
<pre><code class="hljs">4, 2, 6, 7, 0, 5, 9, 1, 8, 3,
0, 1, 2, 3, 4, 5, 6, 7, 8, 9,
</code></pre>
<h2 id="timecomplexity">Time Complexity</h2>
The time complexity, both average and worst of Insertion sort is O(n2) which is fairly terrible. There are much better time complexities available through other, more advanced sorting algorithms, though what makes Insertion Sort stand out is how fast it is on nearly sorted and small collections.
Let's try timing it through 5 runs of small collections and 5 runs of large collections.
<pre><code class="hljs">List&lt;Element&gt; list = new ArrayList&lt;&gt;();
for (int i = 0; i &lt; 10; i++) {
 list.add(new Element(i));
}

Collections.shuffle(list);

// Print shuffled list
list.forEach(e -&gt; System.out.print(e.getId() + &quot;, &quot;));

long startTime1 = System.nanoTime();
insertionSort.insertionSortArrayList(list);
long endTime1 = System.nanoTime();

// Print sorted collection
list.forEach(e -&gt; System.out.print(e.getId() + &quot;, &quot;));
System.out.println();

// Print runtime in nanoseconds
System.out.println(&quot;Insertion Sort runtime: &quot; + (endTime1 - startTime1));
</code></pre>
<table class="table table-striped" style="white-space:nowrap; font-size:15px;">
 <tr>
 <th>Insertion Sort (10)</th>
 <th>Time(s)</th>
 <th></th>
 </tr>
 <tr>
 <td>First Run</td>
 <td>0.000058</td>
 </tr>
 <tr>
 <td>Second Run</td>
 <td>0.000085</td>
 </tr>
 <tr>
 <td>Third Run</td>
 <td>0.000073</td>
 </tr>
 <tr>
 <td>Fourth Run</td>
 <td>0.000060</td>
 </tr>
 <tr>
 <td>Fifth Run</td>
 <td>0.000073</td>
 </tr>
</table>
<table class="table table-striped" style="white-space:nowrap; font-size:15px;">
 <tr>
 <th>Insertion Sort (10k)</th>
 <th>time(s)</th>
 <th></th>
 </tr>
 <tr>
 <td>First Run</td>
 <td>0.091</td>
 </tr>
 <tr>
 <td>Second Run</td>
 <td>0.125</td>
 </tr>
 <tr>
 <td>Third Run</td>
 <td>0.104</td>
 </tr>
 <tr>
 <td>Fourth Run</td>
 <td>0.108</td>
 </tr>
 <tr>
 <td>Fifth Run</td>
 <td>0.123</td>
 </tr>
</table>
Compared to Bubble Sort which has the same time complexity, Insertion Sort is ~5 times faster.
<h2 id="conclusion">Conclusion</h2>
Insertion Sort is one of the simpler sorting algorithms, which works considerably faster on smaller collections than the introductory Bubble Sort and even Selection Sort even though they're all simple quadratic (O(n2) algorithms.
It's great for nearly sorted and small collections (~10 elements) which makes it extremely useful when used in combination with other, more advanced sorting algorithms such as Quicksort or Merge Sort.
It is generally implemented imperatively (though it can also be recursive), and represents an in-place, stable algorithm that works wonders on small datasets.
This means that it preserves the relative order of duplicate elements (in-place) and doesn't require any additional memory for sorting with a constant O(1) space complexity (stable).!

David Landup

Insertion Sort is a simple sorting algorithm that works wonders on small arrays. It's often used alongside Quicksort and Merge Sort in the final stages. In this article, we'll implement Insertion Sort in Java.

Insertion Sort in Java

<h3 id="introduction">Introduction</h3>
If you're majoring in Computer Science, Insertion Sort is most likely one of the first sorting algorithms you have heard of. It is intuitive and easy to <a href="#implementation">implement</a>, but it's very slow on large arrays and is rarely used to sort them.
Insertion Sort is very simple and intuitive to implement, which is one of the reasons it's generally taught at an early stage in programming. It's a stable, in-place algorithm, that works really well for nearly-sorted or small arrays.
Let's elaborate these terms:
<ul>
<li>In-place: Requires a small, constant additional space (no matter the input size of the collection), but rewrites the original memory locations of the elements in the collection.</li>
<li>Stable: The algorithm maintains the relative order of equal objects from the initial array. In other words, say your company's employee database returns &quot;Dave Watson&quot; and &quot;Dave Brown&quot; as two employees, in that specific order. If you were to sort them by their (shared) first name, a stable algorithm would guarantee that this order remains unchanged.</li>
</ul>

 <div class="alert alert-note">
 <div class="flex">
 
 <div class="flex-shrink-0 mr-3">
 <img src="/assets/images/icon-information-circle-solid.svg" class="icon" aria-hidden="true" />
 </div>
 
 <div class="w-full">
 Note: Insertion Sort doesn't need to know the entire array in advance before sorting. The algorithm can receive one element at a time. This is great if we want to add more elements to be sorted - the algorithm only inserts that element in its proper place without &quot;re-doing&quot; the whole sort.

 </div>
 </div>
 </div>
 Insertion Sort is used rather often in practice, because of how efficient it is for small (~10 items) data sets. We will talk more about that <a href="#insertionsortinpractice">later</a>.
<h3 id="theideabehindtheinsertionsort">The Idea Behind the Insertion Sort</h3>
Insertion sort is often illustrated by comparing it to sorting a hand of cards while playing rummy. For those of you unfamiliar with the game, most players want the cards in their hand sorted in ascending order so they can quickly see which combinations they have at their disposal.
The dealer deals out 14 cards to you, you pick them up one by one and put them in your hand in the right order. During this entire process, your hand holds the sorted &quot;subarray&quot; of your cards, while the remaining face-down cards on the table are unsorted - from which you take cards one by one, and put them in your hand.
<blockquote>
In that manner, the Insertion sort partitions an array into a &quot;sorted&quot; subarray and an &quot;unsorted&quot; subarray. In the beginning, the sorted subarray contains only the first element of our original array.
</blockquote>
The first element in the unsorted array is evaluated so that we can insert it into its proper place in the sorted subarray. The insertion is done by moving all elements larger than the new element one position to the right. Continue doing this until our entire array is sorted, as simple as that.

 <div class="alert alert-note">
 <div class="flex">
 
 <div class="flex-shrink-0 mr-3">
 <img src="/assets/images/icon-information-circle-solid.svg" class="icon" aria-hidden="true" />
 </div>
 
 <div class="w-full">
 Note: Keep in mind that when we say an element is larger or smaller than another element - it doesn't necessarily mean larger or smaller integers.
We can define the words &quot;larger&quot; and &quot;smaller&quot; however we like when using custom objects. For example, point A can be &quot;larger&quot; than point B if it's further away from the center of the coordinate system.

 </div>
 </div>
 </div>
 We will mark the sorted subarray with bolded numbers, and use the following array to illustrate the algorithm:
<ul>
<li>8, 5, 4, 10, 9</li>
</ul>
The first step would be to &quot;add&quot; 8 to our sorted subarray.
<ul>
<li>8, 5, 4, 10, 9</li>
</ul>
Now we take a look at the first unsorted element - 5. We keep that value in a separate variable, for example <code>current</code>, for safe-keeping. 5 is less than 8. We move 8 one place to the right, effectively overwriting the 5 that was previously stored there (hence the separate variable for safekeeping):
<ul>
<li>8, 8, 4, 10, 9 (<code>current</code> = 5)</li>
</ul>
5 is lesser than all the elements in our sorted subarray, so we insert it into the first position:
<ul>
<li>5, 8, 4, 10, 9</li>
</ul>
Next, we look at number 4. We save that value in the <code>current</code>. 4 is less than 8 so we move 8 to the right, and do the same with 5.
<ul>
<li>5, 5, 8, 10, 9 (<code>current</code> = 4)</li>
</ul>
Again we've encountered an element lesser than our entire sorted subarray, so we put it in the first position:
<ul>
<li>4, 5, 8, 10, 9</li>
</ul>
10 is greater than our rightmost element in the sorted subarray and is therefore larger than any of the elements to the left of 8. So we simply move on to the next element:
<ul>
<li>4, 5, 8, 10, 9</li>
</ul>
9 is less than 10, so we move 10 to the right:
<ul>
<li>4, 5, 8, 10, 10 (<code>current</code> = 9)</li>
</ul>
However, 9 is greater than 8, so we simply insert 9 right after 8.
<ul>
<li>4, 5, 8, 9, 10</li>
</ul>
<h3 id="howtoimplementbubblesortinpython">How to Implement Bubble Sort in Python</h3>
As we have previously mentioned, Insertion Sort is fairly easy to implement. We'll implement it first on a simple array of integers and then on some custom objects.
In practice, it's much more likely that you'll be working with objects and sorting them based on certain criteria.
<h4 id="sortingarrays">Sorting Arrays</h4>
<pre><code class="hljs">def insertion_sort(array):

 # We start from 1 since the first element is trivially sorted
 for index in range(1, len(array)):
 currentValue = array[index]
 currentPosition = index

 # As long as we haven&#x27;t reached the beginning and there is an element
 # in our sorted array larger than the one we&#x27;re trying to insert - move
 # that element to the right
 while currentPosition &gt; 0 and array[currentPosition - 1] &gt; currentValue:
 array[currentPosition] = array[currentPosition -1]
 currentPosition = currentPosition - 1


 # We have either reached the beginning of the array or we have found
 # an element of the sorted array that is smaller than the element
 # we&#x27;re trying to insert at index currentPosition - 1.
 # Either way - we insert the element at currentPosition
 array[currentPosition] = currentValue
</code></pre>
Let's populate a simple array and sort it:
<pre><code class="hljs">array = [4, 22, 41, 40, 27, 30, 36, 16, 42, 37, 14, 39, 3, 6, 34, 9, 21, 2, 29, 47]
insertion_sort(array)
print(&quot;sorted array: &quot; + str(array))
</code></pre>
Output:
<pre><code class="hljs">sorted array: [2, 3, 4, 6, 9, 14, 16, 21, 22, 27, 29, 30, 34, 36, 37, 39, 40, 41, 42, 47]
</code></pre>

 <div class="alert alert-note">
 <div class="flex">
 
 <div class="flex-shrink-0 mr-3">
 <img src="/assets/images/icon-information-circle-solid.svg" class="icon" aria-hidden="true" />
 </div>
 
 <div class="w-full">
 Note: It would have been technically incorrect if we reversed the order of conditions in our <code>while</code> loop. That is, if we first checked whether <code>array[currentPosition-1] &gt; currentValue</code> before checking whether <code>currentPosition &gt; 0</code>.

 </div>
 </div>
 </div>
 This would mean that if we did indeed reach the 0th element, we would first check whether <code>array[-1] &gt; currentValue</code>. In Python, this is &quot;fine&quot;, although technically incorrect, since it wouldn't cause the loop to end prematurely or continue when it shouldn't.
This is because if we had reached the zeroth element, the second condition of <code>currentPosition &gt; 0</code> would fail regardless of the first condition, and cause the loop to break. In Python <code>array[-1] &gt; currentValue</code> is equivalent to <code>array[len(array) - 2] &gt; currentValue</code> and the interpreter wouldn't complain, but this is not a comparison we actually want to happen.
This reversed order of conditions is a bad idea. In a lot of cases, it can lead to unexpected results that can be hard to debug because there is no syntactic or semantic error. Most programming languages would &quot;complain&quot; for trying to access the <code>-1</code>st element, but Python won't complain and it's easy to miss such a mistake.
<blockquote>
The takeaway advice from this is to always check whether the index is valid before using it to access elements.
</blockquote>
<h4 id="sortingcustomobjects">Sorting Custom Objects</h4>
We've mentioned before that we can define &quot;greater than&quot; and &quot;lesser than&quot; however we want - that the definition doesn't need to rely solely on integers. There are several ways we can change our algorithm to work with custom objects.
We could redefine the actual comparison operators for our custom class and keep the same algorithm code as above. However, that would mean that we'd need to <a target="_blank" href="/overloading-functions-and-operators-in-python">overload those operators</a> if we wanted to sort the objects of our class in a different way.
Arguably the best way to use Insertion Sort for custom classes is to pass another argument to the <code>insertion_sort()</code> method - specifically a comparison method. The most convenient way to do this is by using a custom <a target="_blank" href="/lambda-functions-in-python/">lambda function</a> when calling the sorting method.
In this implementation, we'll sort points where a &quot;smaller&quot; point is the one with a lower <code>x</code> coordinate.
First, we'll define our <code>Point</code> class:
<pre><code class="hljs">class Point:
 def __init__(self, x, y):
 self.x = x
 self.y = y

 def __str__(self):
 return str.format(&quot;({},{})&quot;, self.x, self.y)
</code></pre>
Then we make a slight change to our <code>insertion_sort</code> method to accommodate custom sorting:
<pre><code class="hljs">def insertion_sort(array, compare_function):
 for index in range(1, len(array)):
 currentValue = array[index]
 currentPosition = index

 while currentPosition &gt; 0 and compare_function(array[currentPosition - 1], currentValue):
 array[currentPosition] = array[currentPosition - 1]
 currentPosition = currentPosition - 1

 array[currentPosition] = currentValue
</code></pre>
Finally, we test the program:
<pre><code class="hljs">A = Point(1,2)
B = Point(4,4)
C = Point(3,1)
D = Point(10,0)

array = [A,B,C,D]

# We sort by the x coordinate, ascending
insertion_sort(array, lambda a, b: a.x &gt; b.x)

for point in array:
 print(point)
</code></pre>
We get the output:
<pre><code class="hljs">(1,2)
(3,1)
(4,4)
(10,0)
</code></pre>
This algorithm will now work for any type of array, as long as we provide an appropriate comparison function.
<h3 id="insertionsortinpractice">Insertion Sort in Practice</h3>
Insertion sort may seem like a slow algorithm, and indeed in most cases, it is too slow for any practical use with its O(n2) time complexity. However, as we've mentioned, it's very efficient on small arrays and on nearly sorted arrays.
This makes Insertion Sort very relevant for use in combination with algorithms that work well on large data sets.
For example, Java used a Dual Pivot <a target="_blank" href="/quicksort-in-python">Quick Sort</a> as the primary sorting algorithm but used Insertion Sort whenever the array (or subarray created by Quick Sort) had less than 7 elements.
Another efficient combination is simply ignoring all small subarrays created by Quick Sort, and then passing the final, nearly-sorted array, through Insertion Sort.
Another place where Insertion Sort left its mark is with a very popular algorithm called Shell Sort. Shell Sort works by calling Insertion Sort to sort pairs of elements far apart from each other, then incrementally reducing the gap between elements to be compared.
Essentially it makes a lot of Insertion Sort calls to first small, and then nearly-sorted larger arrays, harnessing all the advantages it can.
<h3 id="conclusion">Conclusion</h3>
Insertion Sort is a very simple, generally inefficient algorithm that nonetheless has several specific advantages that make it relevant even after many other, generally more efficient algorithms have been developed.
It remains a great algorithm for introducing future software developers into the world of sorting algorithms and is still used in practice for specific scenarios in which it shines.

Olivera Popović

Dimitrije Stamenic

Insertion Sort is a simple sorting algorithm that works wonders on small collections. It often used alongside Quicksort and Merge Sort in the final stages. In this article, we'll implement Insertion Sort in Python.

Insertion Sort in Python

Git is a great tool for tracking all of the files in a project, whether you have only a few to track or thousands. But just because a file exists in your project doesn't mean you automatically want to keep track of it and its changes over the lifetime of the project.
In this article we'll see a bit of background on why it's important to tell Git to ignore certain files, how to actually do it, and some best practices.
<h2 id="whyusegitignore">Why use .gitignore?</h2>
Manually ignoring files that you don't want to track is manageable on a small-scale project, but as soon as your project starts to grow and include tens or hundreds of non-version controlled files, it can then become a big problem. These files will start to clutter the &quot;Untracked files&quot; list, which may cause you to overlook legitimate files that need to be in the repo.
To help with this problem, Git has an &quot;ignore&quot; mechanism in the form of a file called <code>.gitignore</code>. With this file and very simple pattern matching, you can tell Git which types of files you want it to ignore and not track in your repo. If a filename in your project matches one of the patterns in the <code>.gitignore</code> file then Git won't attempt to track the file and it won't show up in the &quot;Untracked files&quot; list.
<h2 id="whatfilestoignore">What Files to Ignore</h2>
A lot of this comes down to personal preference, but in general I tend to follow these general rules on which files to not track:
<ul>
<li>System files (i.e. Mac's <code>.DS_Store</code>)</li>
<li>App configuration files (i.e. <code>app.config</code>, <code>.env</code>, etc.)</li>
<li>Build artifacts (i.e. <code>*.pyc</code>)</li>
<li>Installed dependencies (i.e. <code>node_modules</code>)</li>
<li>Non-documenation and personal text files (i.e. <code>todo.txt</code>)</li>
<li>Application data and logs (i.e. <code>*.log</code>, <code>*.sqlite</code>, etc.)</li>
</ul>
There are quite a few other files types that are often ignored, but a lot of this comes down to personal preference, like the following:
<ul>
<li>Dev configuration files (i.e. <code>.jshintrc</code>)</li>
<li>Generated or minified source code (i.e. <code>*.min.js</code>)</li>
<li><code>.gitignore</code></li>
</ul>
Yes, even tracking of the <code>.gitignore</code> file itself is debated.
The advice given here may change depending on who you talk to, so you may want to take some of this with a grain of salt. Everyone has their opinions on what should or shouldn't be tracked, so your best option is to review both sides of the debate and then make a decision for yourself based on what's best for your project.
<h2 id="usinggitignore">Using .gitignore</h2>
The basics of using this ignore feature are pretty straight forward, which is what we'll go over in this section.
For the sake of our example, let's say we have a new project with the following untracked files:
<pre><code class="hljs">$ git status
On branch master

Initial commit

Untracked files:
 (use &quot;git add &lt;file&gt;...&quot; to include in what will be committed)

 .DS_Store
 .env-dev
 .env-prod
 index.js
 node_modules/
 package-lock.json
 package.json
</code></pre>
It's a bit pointless to track the <code>.DS_Store</code> and <code>node_modules/</code> files in our repo, so we'll want to ignore these. To do so, we'll first create a file in the project's root directory named <code>.gitignore</code>:
<pre><code class="hljs">$ touch .gitignore
</code></pre>
The simplest way to ignore a file, and most common, is to simply add the full filename to the ignore file. So to ignore the above files, for example, we'll want to add the following:
<pre><code class="hljs">.DS_Store
node_modules
</code></pre>
Once saved, Git will now show us the following untracked files:
<pre><code class="hljs">$ git status

...

Untracked files:
 (use &quot;git add &lt;file&gt;...&quot; to include in what will be committed)

 .env-dev
 .env-prod
 .gitignore
 index.js
 package-lock.json
 package.json
</code></pre>
Both <code>.DS_Store</code> and <code>node_modules</code> are now gone from the &quot;Untracked files&quot; list, but we still have a few that we want to get rid of, <code>.env-dev</code> and <code>.env-prod</code>. To avoid having to explicitly add each to <code>.gitignore</code> (especially if we have to add more of these files for test and staging environments), we'll use a wildcard:
<pre><code class="hljs">.DS_Store
node_modules
.env-*
</code></pre>
And now our &quot;Untracked files&quot; list has been reduced even further:
<pre><code class="hljs">$ git status

...

Untracked files:
 (use &quot;git add &lt;file&gt;...&quot; to include in what will be committed)

 .gitignore
 index.js
 package-lock.json
 package.json
</code></pre>
The wildcard character (<code>*</code>) will match anything except for a slash. And using two wildcard characters in a row (<code>**</code>) followed by a slash will match your pattern in all directories. So, for example, <code>public/**/*.min.js</code> will ignore all minified JavaScript files in the <code>public</code> directory, regardless of how many directories deep they are.
The Git ignore mechanism also supports some simple <a rel="nofollow noopener" target="_blank" href="https://en.wikipedia.org/wiki/Regular_expression">regular expression</a>-like syntax, with some extra syntax of its own:
<ul>
<li><code>[a-zA-Z]</code>: Match a range of characters</li>
<li><code>?</code>: Match 0 or 1 occurrences of the preceding element</li>
<li><code>!</code>: Negates the match or preceding character</li>
</ul>
Git also allows you to add comments to this file, which start with a <code>#</code>. This is very useful for organizing the file or adding explanations about why certain patterns were added.
<h2 id="hierarchyofgitignorefiles">Hierarchy of .gitignore Files</h2>
Git actually checks more than just the local <code>.gitignore</code> file for which files it should ignore. As we've seen so far, the most common location is to place a <code>.gitignore</code> file in the root directory of your project. Another option is to have a <code>.gitignore</code> file nested in a directory in your project. While less common in practice, this can be useful for applying an entire ignore file on a subdirectory that has many rules of its own.
Another useful feature is a global ignore file. This is typically a <code>.gitignore</code> file placed in your home directory:
<pre><code class="hljs">$ touch ~/.gitignore
</code></pre>
If needed, you can change the location of this global file using the following command:
<pre><code class="hljs">$ git config --global core.excludesFile ~/.gitignore
</code></pre>
Any patterns placed in this file should be for file types that you are positive you'll never want to track, like the <code>.DS_Store</code> file for you Mac users. It's easy to forget about this global ignore file, which can cause a lot of confusion or problems when you miss committing a file because it was ignored globally.
<h2 id="committingignoredfiles">Committing Ignored Files</h2>
Let's say you have an exception you want to make for a file that's usually ignored, but for whatever reason this project in particular needs it. In cases like this you have a few options:
<ol>
<li>Tell Git to not ignore this file by prefixing the file name with a <code>!</code> in .gitignore, i.e. <code>!.env</code>. This will override any global ignore files or ignore files in parent directories.</li>
<li>Use the <code>--force</code> option (or <code>-f</code> flag) when staging your files, i.e. <code>git add .env --force</code></li>
</ol>
<h2 id="conclusion">Conclusion</h2>
In this article we saw how Git provides a mechanism for us to tell it which files should not be tracked in our repo, preventing us from having to manually prevent files from being added. This is a powerful feature that provides a rich syntax, as well as a hierarchy to better control which files are ignored and which aren't.

Manually ignoring files is manageable on a small project. This task gets out of hand as soon as your project gets big, which can cause many manual errors and issues with your build. In this article, we'll see how to use .gitignore to ignore files we want to be omitted from the repo.

Git: Ignore Files with .gitignore

Dan Nelson

Dimensionality reduction selects the most important components of the feature space, preserving them, to combat overfitting. In this article, we'll reduce the dimensions of several datasets using a wide variety of techniques in Python using Scikit-Learn.

Dimensionality Reduction in Python with Scikit-Learn

<h2 id="introduction">Introduction</h2>
Sorting is a crucial aspect of digesting data. For us humans, it's much more natural to sort things that have something in common like the date of publishing, alphabetical order, articles belonging to an author, from smallest to largest, etc. This makes it a lot easier to comprehend the data as it's logically connected rather than dispersed all around.
And just as important, sorted arrays are easier for computers to work with. For example, a sorted array can be searched much faster, like with the <a rel="nofollow noopener" target="_blank" href="https://en.wikipedia.org/wiki/Binary_search_algorithm">binary search</a> algorithm, which runs in O(logn) time. An algorithm like this just doesn't work without a sorted array.
<h2 id="mergesort">Merge Sort</h2>
Merge sort is a divide-and-conquer algorithm, which recursively calls itself on halved portions of the initial collection.
That being said, it sounds a lot like <a rel="nofollow noopener" target="_blank" href="https://en.wikipedia.org/wiki/Quicksort">Quicksort</a>, which also partitions the collection and then recursively calls itself on the partitioned collections (which are typically halves).
The main difference is the fact that Quicksort is an internal, in-place sorting algorithm while Merge Sort is an external, out-of-place sorting algorithm.
This is typically done with collections which are too large to load into memory, and we load them chunk by chunk as they're needed. So Merge Sort doesn't need to store the whole collection into the memory from which it can easily and randomly access each and every element at any given time. Rather, the collection can be stored at an external place, such as a disk (or much longer ago - tape), from which required elements are loaded.
That being said, Merge Sort has to deal with making such loading and unloading optimal as it can get quite slow with big collections.
As mentioned above, Merge Sort is an &quot;out-of-place&quot; sorting algorithm. What this means is that Merge Sort does not sort and store the elements in the memory addresses of the collection given to it, but instead it creates and returns a completely new collection that is the sorted version of the one provided to it.
This is an important distinction because of memory usage. For very large arrays this would be a disadvantage because the data will be duplicated, which can memory problems on some systems.
Here's a visual representation of how it works:
<img src="https://s3.amazonaws.com/stackabuse/media/sorting-algorithms-in-java-1.png" alt="merge sort visual representation">
<h2 id="implementation">Implementation</h2>
To fascilitate the algorithm, we'll be using two methods - <code>mergeSort()</code> which will partition the collection and recursivelly call itself, and its helper method, <code>merge()</code> which will merge the results in the correct order.
Let's start off with <code>mergeSort()</code>:
<pre><code class="hljs">public static void mergeSort(int[] array, int low, int high) {
 if (high &lt;= low) return;

 int mid = (low+high)/2;
 mergeSort(array, low, mid);
 mergeSort(array, mid+1, high);
 merge(array, low, mid, high);
}
</code></pre>
This part is pretty straightforward - we provide an array to be sorted and it's <code>low</code> and <code>high</code> pointers. If the <code>high</code> pointer ends up being lower or equal to the <code>low</code> pointer, we simply <code>return</code>.
Otherwise, we partition the array into two halves and call <code>mergeSort</code> from the start of the array to the middle, and then call it from the middle to the end.
Ultimately, we call the <code>merge()</code> method, which merges the results into a sorted array:
<pre><code class="hljs">public static void merge(int[] array, int low, int mid, int high) {
 // Creating temporary subarrays
 int leftArray[] = new int[mid - low + 1];
 int rightArray[] = new int[high - mid];

 // Copying our subarrays into temporaries
 for (int i = 0; i &lt; leftArray.length; i++)
 leftArray[i] = array[low + i];
 for (int i = 0; i &lt; rightArray.length; i++)
 rightArray[i] = array[mid + i + 1];

 // Iterators containing current index of temp subarrays
 int leftIndex = 0;
 int rightIndex = 0;

 // Copying from leftArray and rightArray back into array
 for (int i = low; i &lt; high + 1; i++) {
 // If there are still uncopied elements in R and L, copy minimum of the two
 if (leftIndex &lt; leftArray.length &amp;&amp; rightIndex &lt; rightArray.length) {
 if (leftArray[leftIndex] &lt; rightArray[rightIndex]) {
 array[i] = leftArray[leftIndex];
 leftIndex++;
 } else {
 array[i] = rightArray[rightIndex];
 rightIndex++;
 }
 } else if (leftIndex &lt; leftArray.length) {
 // If all elements have been copied from rightArray, copy rest of leftArray
 array[i] = leftArray[leftIndex];
 leftIndex++;
 } else if (rightIndex &lt; rightArray.length) {
 // If all elements have been copied from leftArray, copy rest of rightArray
 array[i] = rightArray[rightIndex];
 rightIndex++;
 }
 }
}
</code></pre>
Running the following piece of code:
<pre><code class="hljs">int[] array = new int[]{5, 6, 7, 2, 4, 1, 7};
mergeSort(array, 0, array.length-1);
System.out.println(Arrays.toString(array));
</code></pre>
Will yield us a sorted array:
<pre><code class="hljs">[1, 2, 4, 5, 6, 7, 7]
</code></pre>
<h2 id="timecomplexity">Time Complexity</h2>
The average and worst-case time complexity of Merge Sort is O(nlogn), which is fair for a sorting algorithm. Here's how it performed after sorting an array containing 10,000 integers in random order:
<pre><code class="hljs">int[] array = new int[10000];
for (int i = 0; i &lt; array.length; i++) {
 array[i] = i;
}

// Shuffle array
Collections.shuffle(Arrays.asList(array));

// Print shuffled collection
for (int i = 0; i &lt; array.length; i++) {
 System.out.println(array[i]);
}

long startTime = System.nanoTime();
mergeSort(array, 0, array.lenth-1);
long endTime = System.nanoTime();

// Print sorted collection
for (int i = 0; i &lt; array.length; i++) {
 System.out.println(array[i]);
}

System.out.println();

// Print runtime in nanoseconds
System.out.println(&quot;Merge Sort runtime: &quot; + (endTime - startTime));
</code></pre>
And here are the results in seconds after running it 10 times:
<table class="table table-striped" style="white-space:nowrap; font-size:15px;">
 <tr>
 <th>time(s)</th>
 <th>Merge Sort</th>
 <th></th>
 </tr>
 <tr>
 <td>First Run</td>
 <td>0.00551</td>
 </tr>
 <tr>
 <td>Second Run</td>
 <td>0.00852</td>
 </tr>
 <tr>
 <td>Third Run</td>
 <td>0.00765</td>
 </tr>
 <tr>
 <td>Fourth Run</td>
 <td>0.00543</td>
 </tr>
 <tr>
 <td>Fifth Run</td>
 <td>0.00886</td>
 </tr>
 <tr>
 <td>Sixth Run</td>
 <td>0.00946</td>
 </tr>
 <tr>
 <td>Seventh Run</td>
 <td>0.00575</td>
 </tr>
 <tr>
 <td>Eight Run</td>
 <td>0.00765</td>
 </tr>
 <tr>
 <td>Ninth Run</td>
 <td>0.00677</td>
 </tr>
 <tr>
 <td>Tenth Run</td>
 <td>0.00550</td>
 </tr>
</table>
With an average run-time of 0.006s, it's pretty quick.
<h2 id="conclusion">Conclusion</h2>
Merge sort is a divide-and-conquer algorithm, which recursively calls itself on halved portions of the initial collection.
Another thing to note is that Merge Sort is an &quot;out-of-place&quot; sorting algorithm. This means that it does require extra space to store the elements its sorting, which can cause problems for memory-constrained systems. This is one trade-off of using this algorithm.
Although it's one of the quickest and most efficient sorting algorithms with the average time complexity of O(nlogn), right alongside Quicksort, Timsort, and Heapsort.me

Merge Sort is a classic divide-and-conquer algorithm that recursively calls itself on halved portions of the initial collection. In this article, we'll implement Merge Sort in Java and compare it to Quicksort.

Merge Sort in Java

Muhammad Junaid Khalid

Using cURL in Python with PycURL

Quicksort is one of the most widespread sorting algorithm due to the relative simplicity of implementation and efficient performance. In this article, we'll implement Quicksort in Python.