Problems on Linear Search

1. First repeating element
2. Bigger than given
3. K- closest elements
4. Pairs equal to k
5. Minimum something
6. Kth smallest number
7. Distinct elements
8. Closest pair
9. Ceiling in a sorted array
10. Floor in a sorted array
11. First occurrence of an element
12. Pairs with constant difference
13. Missing in arithmetic progression
14. Search small ones
15. Search in a sorted array

Comments

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,...

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...

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...

codesprint with rishav

Search This Blog