Overview of Common Sorting Algorithms and Basic Data Structures

Bubble Sort

Idea: repeatedly swap adjacent elements so that the larger one moves toward the end; after the first pass the maximum value is at the array's last position. For an array of n elements, n-1 passes are required.

Implementation key points: two nested for loops, the outer loop controls the number of passes, the inner loop controls the number of comparisons; after each pass the comparison count should decrease by one.

Selection Sort

Idea: find the largest element in the unsorted portion and swap it with the last element of that portion. When only one element remains, no further selection is needed, so n-1 passes are required.

Implementation key points: two for loops, the outer loop controls the passes, the inner loop finds the current maximum and then swaps it with the last element of the current unsorted segment.

Insertion Sort

Idea: treat the first element as a sorted sub‑array, then insert each subsequent element into its correct position within the sorted part by shifting larger elements to the right; when only one element remains, no insertion is needed, so n-1 passes are required.

Implementation: an outer for loop iterates over the array, and an inner while loop finds the appropriate insertion position (ensuring the index does not go below zero) and shifts elements as needed.

Quick Sort

Prerequisite: understanding recursion.

Idea: choose a pivot element, place all smaller elements to its left and larger elements to its right; after one partition the array is split into two sub‑arrays that can be sorted recursively.

Implementation: select the middle element as pivot, use two indices L and R to represent the current left and right bounds, repeatedly compare and swap elements that are on the wrong side of the pivot, then recursively sort the sub‑arrays L … pivot‑1 and pivot+1 … R .

Merge Sort

Prerequisite: understanding recursion.

Idea: repeatedly split the array into two sorted halves and then merge them back together to produce a fully sorted array.

Implementation: the first pass treats each pair of elements as two already‑sorted sub‑arrays and merges them; this process is repeated, progressively merging larger sorted sections until the whole array is sorted.

Heap Sort

Prerequisite: understanding binary trees.

Idea: build a max‑heap where each parent node is larger than its children; after the heap is built, repeatedly swap the root (maximum) with the last element of the heap and reduce the heap size, restoring the heap property each time.

Implementation: if either child of a node is larger than the node, swap them; after a swap, continue heapifying the affected subtree until the parent‑greater‑than‑children condition holds for all nodes.

Shell Sort

Idea: an enhanced version of insertion sort that first sorts elements far apart (using a gap), making the array partially ordered; a final insertion sort then finishes the job with fewer moves.

Implementation: the gap is repeatedly halved (e.g., gap = gap / 2 ) and for each gap a standard insertion sort is performed on the sub‑arrays formed by that spacing.

Radix Sort (Bucket Sort)

Idea: distribute numbers into buckets according to each digit (units, tens, hundreds, etc.), collect them in order, and repeat for the next more significant digit until the most significant digit has been processed.

Implementation: first find the maximum value to determine the number of digit passes ( max/10 as the loop condition); for each pass, place numbers into the appropriate digit bucket and then retrieve them in bucket order.

Recursion

Recursion is heavily used in algorithms; quick sort and merge sort both rely on it.

To use recursion you must define two things: the termination condition (base case) and the recursive expression (the rule that reduces the problem).

Technique: split the problem into two parts (the whole and a sub‑problem), which helps to derive the recursive expression.

Example: Tower of Hanoi implementation.

Basic Data Structures

Linked list, queue, binary tree, and stack are fundamental data structures. Each has typical algorithmic interview questions, such as:

LeetCode 206: Reverse Linked List

LeetCode 20: Valid Parentheses (e.g., []{}{]}{( )

LeetCode 104: Maximum Depth of Binary Tree

LeetCode 102: Binary Tree Level Order Traversal

While advanced structures like tries, red‑black trees, or graphs are not required for most entry‑level interviews, you should be comfortable implementing linked lists, queues, binary trees, and stacks.

Conclusion

The code examples for sorting algorithms and data structures are written for clarity rather than optimal performance; each line is heavily commented to aid understanding.