Searching and Sorting Algorithms

Explore linear search by sequentially scanning an array with a single for loop, comparing each element to the target, breaking when found, and understanding best and worst case complexities.

Learn to implement a linear search by reading an array size and elements, scanning for a target, and reporting its one-based position when found or not found.

Learn how binary search finds a key in a sorted array by comparing it to the middle element and halving the left and right halves, revealing logarithmic complexity.

Learn to implement binary search iteratively in C++ (or any language) using first and last indices, a while loop, and mid calculation to handle found, less, or greater cases.

Explore recursive implementation of binary search, using array, key, and first and last indices, with base cases returning index or -1 and left or right recursive calls.

Learn jump search, skip elements by jumping blocks of size sqrt(n) and then linearly search within the block to locate the key, achieving about sqrt(n) time.

Explore jump search implementation: compute block size with the square root of the array, jump through blocks, adjust pointers, and handle found or not-found outcomes with flags.

Demonstrate bubble sort by comparing adjacent elements, swapping when out of order, and moving the largest element to the last position across passes to sort an array in ascending order.

This lecture demonstrates bubble sort with a numeric example, showing comparisons and swaps that move elements toward increasing order, placing the largest element at the end after the first pass.

Implement bubble sort by writing a swap-by-reference function, using two pointers, and iterating with outer and inner loops until no swaps occur, then print the sorted array.

Explore selection sort by selecting the minimum element in the unsorted portion and placing it at the current position, using three pointers to guide passes and swaps, with time-space tradeoffs.

Implement the selection sort algorithm in C++ by writing a swap function, using three indices to find the minimum element, and swapping at the end of each pass.

Explore count sort, a linear-time sorting method that uses a frequency array to count occurrences and reconstruct the sorted output, best for small, limited ranges like ASCII.

Learn to implement count sort in C++, by finding the maximum value, building a count array, tallying occurrences, and producing a sorted output in order.

Bucket sort uses an array of linked lists as buckets to group elements by value, then traverses buckets to produce a sorted sequence, suitable for small ranges.

Explore the implementation of bucket sort in C++ by building an array of pointers to nodes forming linked-list buckets, using dynamic memory and node structures to store data and links.

Implement bucket sort by organizing data into buckets comprised of linked lists, traverse to the end of each list to insert new nodes, and manage next pointers for complete traversal.

explains radix sort by distributing numbers into buckets using digits and performing passes equal to the maximum digit count in base ten.

Break down how to extract each digit of a number, including the last digit via modulo ten, using division by ten from least to most significant, to support radix sort.

Implement radix sort in C++ by distributing numbers into digit-based buckets and performing multiple passes using powers of ten to extract digits, driven by the maximum value's digit count.

Insert an element into a sorted array by creating space and shifting elements to the right until the correct position is found, then insert the key.

Demystify the insertion sort algorithm by taking each element as a key, shifting larger elements to the right, and inserting the key to grow a sorted subarray.

Explore insertion sort by stepping through the array, selecting each element as a key, shifting larger elements to the right, and inserting the key at its correct position.