Skip to main content

Posts

Sieve of Eratosthenes

The Sieve of Eratosthenes is an ancient algorithm for finding all prime numbers up to a given limit. It was devised by the Greek mathematician Eratosthenes around 200 BCE, and it is still used today in various applications, such as cryptography and computer science. The basic idea of the Sieve of Eratosthenes is to eliminate all composite numbers (i.e., non-prime numbers) in a range of numbers from 2 to some upper limit. To do this, we start by marking all the numbers from 2 to the limit as potential primes. We then iterate through the list of numbers, starting with 2, and for each prime number we encounter, we mark all its multiples as composite. This process is repeated for each subsequent prime number until we reach the end of the list. At the end of this process, all the unmarked numbers that remain are primes. This is because any composite number in the list would have been marked as a multiple of some smaller prime number, and thus eliminated from the list. For example, if we sta
Post a Comment
Read more
Recent posts

Shell Sort

Shell sort is a sorting algorithm developed by Donald Shell in 1959. It is an extension of the insertion sort algorithm and is classified as an in-place comparison sort. Shell sort aims to improve the performance of insertion sort by sorting elements that are far apart from each other first, thus reducing the number of comparisons needed to sort the entire array. The algorithm works by first dividing the array into smaller subarrays, each containing elements that are a certain gap apart. The gap is typically initialized to be the length of the array divided by 2, and is then halved in each iteration until it becomes 1. The subarrays are then sorted using insertion sort, which sorts elements within each subarray by comparing adjacent elements and swapping them if they are in the wrong order. The key idea behind Shell sort is that insertion sort performs poorly on arrays that are almost sorted, but works well on small arrays. By sorting the subarrays with larger gaps first, the algorithm
Post a Comment
Read more

Bubble Sort

   Bubble sort is a simple sorting algorithm that works by repeatedly swapping adjacent elements if they are in the wrong order. It is named after the way bubbles rise to the top of a liquid, as it sorts the array by repeatedly moving the largest or smallest elements to the top of the array. The algorithm works by iterating through the array, comparing each adjacent pair of elements and swapping them if they are in the wrong order. This process is repeated until the array is fully sorted. Let's say we have an array of integers [5, 3, 8, 4, 2]. The first pass of the algorithm would compare 5 and 3, swap them to get [3, 5, 8, 4, 2]. It would then compare 5 and 8 and not swap them, as they are in the correct order. It would then compare 8 and 4, swap them to get [3, 5, 4, 8, 2]. It would then compare 8 and 2, swap them to get [3, 5, 4, 2, 8]. The first pass is now complete, and the largest element, 8, is at the end of the array. The second pass would start with comparing 3 and 5, not
Post a Comment
Read more

Pigeonhole Sort

Pigeonhole sort is a sorting algorithm that works by distributing elements of an input sequence into a set of pigeonholes or buckets. It is an efficient sorting algorithm for small ranges of values where the number of elements to be sorted is roughly the same as the range of values. Pigeonhole sort is an example of a bucket sort algorithm. The pigeonhole sort algorithm works by first determining the range of values in the input sequence. This range is used to create a set of pigeonholes or buckets, each of which can hold one or more elements from the input sequence. Each element in the input sequence is then placed into its corresponding pigeonhole based on its value. If two or more elements have the same value, they can be placed in the same pigeonhole. Once all the elements have been placed into their corresponding pigeonholes, the elements are sorted within each pigeonhole. Finally, the sorted elements are combined into a single output sequence. Pigeonhole sort has a time complexity
Post a Comment
Read more

Comb Sort

Comb sort is a sorting algorithm that was first proposed by Włodzimierz Dobosiewicz in 1980. The algorithm is a variation of bubble sort, and it is designed to improve upon the performance of bubble sort by using a larger gap between elements during the comparison phase of the algorithm. The basic idea behind comb sort is to compare elements that are separated by a large gap, and gradually reduce the gap between elements until the gap is equal to 1. The gap between elements is known as the "comb" in comb sort, and it is initially set to be the size of the input array being sorted. The size of the comb is then reduced by a factor known as the shrink factor, which is typically set to 1.3. During each pass of the algorithm, elements that are separated by the current gap are compared and swapped if they are out of order. The gap between elements is then reduced by the shrink factor, and the process is repeated until the gap is equal to 1. Once the gap is equal to 1, the algorithm
Post a Comment
Read more

Radix Sort

Radix sort is a sorting algorithm that operates by sorting the elements of an array by examining their digits. It is based on the idea of distributing elements into buckets according to the value of a specific digit. This process is repeated for each digit, starting from the least significant to the most significant digit. The algorithm starts by selecting a digit position and grouping the elements based on their value at that position. For example, if the selected digit position is the ones place, all elements with a 0 in the ones place are grouped together, followed by all elements with a 1 in the ones place, and so on. After grouping the elements, the algorithm concatenates the buckets in the order they were created, resulting in a partially sorted array. This process is repeated for each digit position until the entire array is sorted. Radix sort has a linear time complexity of O(kn), where k is the maximum number of digits in any element and n is the number of elements in the arra
2 comments
Read more

Counting Sort

Counting sort is a sorting algorithm that operates by counting the frequency of each element in the input array, and then using these frequencies to compute the final sorted output. The algorithm works by first creating an array of counters, with each counter corresponding to a distinct element in the input array. The counters are initialized to zero, and then the input array is scanned once to count the number of occurrences of each element. This count information is stored in the corresponding counter in the counter array. Once the count information is obtained, the algorithm uses it to determine the final position of each element in the sorted output array. This is done by iterating over the counter array, and for each counter value, writing the corresponding element to the sorted output array the appropriate number of times. The time complexity of counting sort is O(n+k), where n is the length of the input array and k is the range of the elements. The space complexity is also O(n+k
2 comments
Read more