Sorting Algorithms from Beginner to Expert

Explore the bubble sort concept, showing how repeated passes compare adjacent elements and swap them to move the largest to the end, with internal sorting versus external sorting.

Learn bubble sort implementation in c++ by stepping through passes, inner loops, and element swapping. Explore array initialization, static versus runtime input, and using size of to determine elements.

Analyze the complexity of bubble sort, including time complexity for best, average, and worst cases, and space complexity, plus optimized bubble sort that detects a sorted list.

Explore the merge sort concept with an example, dividing a list into sublists, sorting them recursively, and merging to form an ascending, fully sorted list.

Merge two sorted lists into one final sorted list by repeatedly comparing the first elements and inserting the smaller, then append the remaining elements when a sublist ends.

Implement merge sort in C++ by dividing a list into left and right sublists, then merging them into a sorted final list.

Analyze the complexity of merge sort, showing that time complexity remains O(n log n) across best, average, and worst cases, while space complexity is O(n).

Explore quicksort, a divide-and-conquer sorting technique that uses a middle element as pivot to partition the list into left and right sublists, then recursively sort each sublist.

Demonstrates quicksort with the first element as pivot, partitioning the array so left values are smaller and right values are greater, with swaps and recursion.

Explore quicksort implementation in c++ using the middle element as the pivot, with partitioning and swapping, and learn recursion for sorting left and right sublists.

Analyze quicksort's time and space complexity, covering best, average, worst cases, driven by pivot choices and partitioning. Understand recursion stack needs and how n log n vs n^2 shapes performance.

Learn how insertion sort builds a sorted list by inserting each element at its proper location, using sequential comparisons and shifting to maintain ascending order, and its stability.

Learn insertion sort implementation in C++ by tracing array initialization, using a temp variable, shifting elements, and inserting the key into its proper position.

Analyze the complexity of insertion sort by time and space, detailing best, worst, and average cases, with O(n) best time and O(n^2) worst and average, plus O(1) space.

Explore selection sort, which finds the minimum element in the unsorted subarray, swaps it into place to build a sorted list in ascending order, and is not a stable sort.

Explore how to implement selection sort in C++, including finding the minimum element and swapping it into place. The lesson demonstrates an unsorted list with iterations, prints, and complexity notes.

Analyze the time and space complexity of selection sort, showing all three cases yield O(n^2) time and O(1) extra space, and explain stability and how to make it stable.

Explore radix sort, a non-competitive, digit-based sorting method using 10 buckets per step. Process numbers from least to most significant digit, preserving order with fifo when buckets hold multiple elements.

Demonstrate the implementation of radix sort in c++ using ten buckets for digits zero through nine, counting occurrences per digit, and building the output across digit-wise passes.

Analyze the time complexity of radix sort, where passes equal the maximum number's digits and each pass processes all elements, and assess its space needs with buckets and extra storage.

Explore heap sort by building and manipulating binary heaps, including complete binary trees, max heaps, and operations like insertion, deletion, and priority queue concepts to sort data efficiently.

Implement heap sort in C++ by building a max heap in place, swapping the root with the end, and heapifying, guided by the main function and array size.

Explain the complexity of heap sort by examining building the heap and extracting elements, with all cases yielding O(n log n) time and O(1) space.

Learn preorder traversal of binary trees by visiting the root, then left and right subtrees, visiting each node exactly once with practical examples.

learn to represent a binary tree with an array, using two dimensions for left and right children, and zeros as nulls to enable preorder traversal.

Explore implementing a preorder traversal in C++ using an array-based binary tree representation, with left and right children encoded in a two-dimensional array, and printing data first.

Learn how in-order traversal processes the left subtree, then the root, then the right, using a recursive pattern on trees, illustrated with a family-tree example.

Implement in order traversal using a 2D array in C++, mirroring preorder with left and right indices, treating missing nodes as zero and using recursion to visit left, root, right.

Master the postorder traversal by recursively processing the left subtree, then the right subtree, and finally the root, and compare it to preorder and inorder.

Implement post order traversal using a two-dimensional array in C++. Represent left and right children with dedicated positions, process left, then right, then root, mirroring pre and in order.

Examine the time-space complexity of binary tree traversals, showing each node is processed once. All three traversals share O(n) time, while space grows with tree height.