My software development journey
In one of my previous posts, we have seen how a linked list can be sorted using bubble sort approach. In this post we will see how we can sort a linked list using insertion sort algorithm. Like bubble sort this approach will also take O(n2) time. Here is the strategy for linked list insertion…
In the last post, the basic use of STL sort() method is explained. In this post, I will discuss some more options available with this method. We have seen in the previous post that sort takes the beginning and ending of the array as arguments. sort( array.begin(), array.end() ); In addition to those parameters, it…
Sorting is one of the most widely used algorithmic primitive in programming. C++ Standard Template Library (STL) provides an efficient implementation of the sort algorithm. It is always better to use this algorithm instead of writing our own implementation because of the following benefits. It’s performance would surely be better than your own implementation. It’s…
Given two sorted arrays A, B of lengths m, n respectively. How to merge them into a single sorted array?. Let us assume that A has sufficient space (m+n) for result array. For example let A = [1, 3, 5, 7, 9], and B = [2, 4, 6, 8, 10]. The function should return A…
Given an array of N distinct values, how to find the number of pairs with a difference of K? For example, given an array [3, 1, 4, 2, 5] and K= 2, there are 3 pairs with a difference of 2. Namely {1,3}, {2,4}, {3,5}. One obvious solution could be to examine each possible pair…
Given a sorted linked list write a program to insert data into it’s correct position. For example consider the following linked list 1 -> 3 -> 4 -> 5 Inserting 2 should change the list to 1 -> 2 -> 3 -> 4 -> 5 Inserting 0 should change it to 0 -> 1 ->…
Given K sorted lists, how to merge them into a single sorted list? Let total number of elements in K sorted lists is N. We have to form a single sorted list of length N. For example let us consider the following input lists{4, 19, 27}{1, 6, 50, 73}{9, 45, 59, 67} The output should…
How do we sort a linked list? In this post, we see one such method using bubble sort algorithm. We have discussed the Bubble sort algorithm on arrays in my previous post. The same algorithm is also applicable to singly linked lists as well.We first find the length of the linked list (len). The outer loop…
Counting sort as its name indicates sort a list of integers by counting the occurrence each number appearing in the list. This is possible when the range of integers (particularly small) is given. Unlike comparison based sorting algorithms which run in O( n log n) time in the worst case, Counting sort runs O(n) time.…
We have an array that contains only 0, 1 and 2. We have to write a program to sort this array.For example if the input array is [2,0,1,2,1,0,0,2], the output should be[0,0,0,1,1,2,2,2].As the first thought, we can very well use well known sorting algorithms like Quick sort, or Merge sort or Heap sort. But that…