The Coding Shala

Home >> Algorithms >> Selection Sort  In this post, we will learn what is Selection Sort Algorithm and how to implement Selection Sort in Java. Selection Sort Algorithm The selection sort algorithm is a sorting algorithm that sorts an array by repeatedly finding minimum element(ascending order)/maximum element(descending order) from the unsorted part and put it at the beginning of the unsorted array. This algorithm maintains two subarrays in a given array, one is sorted and the second is the remaining unsorted subarray. Working of Selection Sort Algorithm We follow the below steps to implement the Selection Sort Algorithm: Step 1. We pick the minimum element from the unsorted subarray. Step 2. Swap it with the first element of the unsorted subarray. Step 3. Now the first element of unsorted subarray becomes a part of the sorted subarray. Here is an example that explains the selection sort algorithm: Array:  64 25 12 22 11     ...

Last Updated: 27-Jan-2021 Home >> Algorithms >> Radix Sort Algorithm  In this post, we will learn what is Radix Sort Algorithm and how to implement Radix Sort in Java. Radix Sort Algorithm As we know sorting algorithms like Merge sort, Quicksort, etc is works in O(N log N) time. They can not do better than NlogN. We have another option as Counting sort that works in a linear time O(n+k) but the limitation in the range is there. We use the Radix sort algorithm when we have elements in the range from 1 to n^2. In the Radix sort algorithm, we do digit by digit sort starting from least significant digit(leftmost) to most significant digit(rightmost). We use counting sort to sort the digits because the range of these digits is less in the range of 0 to 9. Working of Radix Sort Algorithm Radix sort works by sorting the input numbers one digit at a time. let's take an example: input array->  { 127,  324, 173,  4,  38,  217,  134...

Last Updated: 27-Jan-2021 Home >> Algorithms >> Quick Sort Algorithm  In this post, we will learn what is Quick Sort Algorithm and will write a Java program for Quick Sort. Quick Sort Algorithm Quick Sort is one of the most efficient sorting algorithms. If effectively implemented quick sort algorithm is significantly faster than any of the common sorting algorithms. Like Merge Sort, Quicksort is also a classic example of the divide-and-conquer approach. Working of Quick Sort Algorithm In a quick sort algorithm, we follow the divide and conquer approach. The following are the steps used in quicksort: step 1. First, we select a value from the list, called pivot value and it divides the list into two sublists. One sublist contains all the values that are less than the pivot value, another sublist contains the values that are greater than or equal to the pivot value. This process is also called partitioning. we can choose the first/last element in the list as the ...

Last Updated: 20-Jan-2021 Home >> Algorithms >> Merge Sort Algorithm  In this post, we will learn what is Merge Sort Algorithm and how it works. We will write a Java Program for Merge Sort. Merge Sort Algorithm Merge Sort is an efficient and general-purpose sorting algorithm. It is a classic example of the divide-and-conquer algorithm. The merge sort algorithm can be divided into three steps, like all the divide-and-conquer algorithm: step 1. Divide the given unsorted list into several sublists. (Divide) step 2. Sort each of the sublists recursively. (Conquer) Step 3. Merge the sorted sublists to produce a new sorted list. (Combine) Here is an example that explains the working of the merge sort algorithm: The time complexity of Merge Sort Algorithm The time complexity of the merge sort algorithm is O(NlogN), where N is the length of the input list. Merge Sort Algorithm Java Program Java Program:  import java.util.Arrays ; //merger sort //t...

Last Updated: 20-Jan-2021 Home >> Algorithms >> Insertion Sort  In this post, we will learn what is Insertion Sort Algorithm and how it works. We will write a Java program for Insertion Sort. Insertion Sort Algorithm Insertion sort is an algorithm to sort a given array. The Insertion sort works on the principle of inserting an element at a particular position, hence known as Insertion Sort. Working of Insertion Sort Algorithm The Insertion sort works as follows: step 1. We take an element as key starts from index 1. Step 2. we compare all previous elements from the key element index if elements are greater than the key we move them to the next index. Step 3. At last, we insert a key at the index where all the previous elements are less than or equals to the key. Here is an example of the Insertion sort algorithm: Array ->   17 25 31 13 2 key 25    17 25 31 13 2 key 31    17 25 31 13 2 key 13    17 25 31...

Last Updated: 20-Jan-2021 Home >> Algorithms >> Counting Sort  In this post, we will learn what is Counting Sort Algorithm and how it works. We will write a Java program for Counting Sort. Counting Sort Algorithm Counting Sort Algorithm is an algorithm used to sort a given array. We use counting sort if given array elements are in a specific range. It works by counting the number of objects having distinct key values and using those counts we compute an item's index in the final sorted array. Working of Counting Sort Algorithm The following steps we follow for the counting sort algorithm: Step 1. We will iterate through the input once and count the number of times each item occurs. Step 2. Now we modify our count array to pre-compute where each item from the input should go. This step is a little be tricky. We add the previous sum to the current element in the count array. To get more understanding see the below example. Step 3. Now we will use our pre-com...

Last Updated: 20-Jan-2021 Home >> Algorithms >> Bucket Sort  In this post, we will learn what is Bucket Sort Algorithm and will write a Java program to implement Bucket Sort. Bucket Sort Algorithm Bucket Sort is a sorting algorithm. In bucket sort, we create n buckets and insert similar types of elements into the buckets. Bucket sort is mainly useful when input is uniformly distributed over a range. For example, a large set of floating-point numbers are in the range from 0.0 to 1.0 and uniformly distributed across the range. Another example a large set of numbers which are in the range from 1 to 99. In these types of cases, we use the bucket sort algorithm. Working of Bucket Sort Algorithm The following steps need to follow for the Bucket Sort Algorithm: Step 1. First, we create n empty buckets/lists. Step 2. Now for every element arr[i] of given array we insert arr[i] into buckets. Now the main point is how to insert into buckets. How we decide that? If array ...