Sorting and Searching

Common Sorting Algorithms

Sorting is the process of arranging elements in a specific order, typically ascending or descending. Efficient sorting algorithms are crucial for various applications, including database management, data analysis, and optimizing search operations. Several algorithms exist, each with its own time and space complexity characteristics.

1. Bubble Sort

Bubble Sort is one of the simplest sorting algorithms. It repeatedly steps through the list, compares adjacent elements, and swaps them if they are in the wrong order. The pass through the list is repeated until the list is sorted. Larger elements "bubble" up to the end of the list.

Algorithm Steps:

1. Start from the first element.
2. Compare the current element with the next element.
3. If the current element is greater than the next element, swap them.
4. Move to the next element and repeat step 2 and 3 until the end of the list is reached. This completes one pass.
5. Repeat the passes until no swaps are needed in a pass, indicating the list is sorted.

Example: Consider the array [5, 1, 4, 2, 8]

Pass 1:

• (5, 1) -> swap -> [1, 5, 4, 2, 8]
• (5, 4) -> swap -> [1, 4, 5, 2, 8]
• (5, 2) -> swap -> [1, 4, 2, 5, 8]
• (5, 8) -> no swap -> [1, 4, 2, 5, 8]

Pass 2:

• (1, 4) -> no swap -> [1, 4, 2, 5, 8]
• (4, 2) -> swap -> [1, 2, 4, 5, 8]
• (4, 5) -> no swap -> [1, 2, 4, 5, 8]
• (5, 8) -> no swap -> [1, 2, 4, 5, 8]

Pass 3:

• (1, 2) -> no swap -> [1, 2, 4, 5, 8]
• (2, 4) -> no swap -> [1, 2, 4, 5, 8]
• (4, 5) -> no swap -> [1, 2, 4, 5, 8]
• (5, 8) -> no swap -> [1, 2, 4, 5, 8]

The array is sorted: [1, 2, 4, 5, 8].

Time Complexity: O(n²) in the worst and average case. O(n) in the best case (already sorted).

Space Complexity: O(1) as it sorts in-place.

2. Selection Sort

Selection Sort works by repeatedly finding the minimum element from the unsorted part of the list and putting it at the beginning. The list is divided into two parts: a sorted sublist built from left to right, and a sublist of the remaining unsorted elements.

Algorithm Steps:

1. Find the minimum element in the unsorted array.
2. Swap it with the first element of the unsorted array.
3. Move the boundary of the unsorted sublist one element to the right.
4. Repeat steps 1-3 until the entire array is sorted.

Example: Consider the array [64, 25, 12, 22, 11]

Iteration 1:

• Minimum element is 11. Swap 11 with 64. Array becomes [11, 25, 12, 22, 64].

Iteration 2:

• Minimum element in the remaining unsorted part [25, 12, 22, 64] is 12. Swap 12 with 25. Array becomes [11, 12, 25, 22, 64].

Iteration 3:

• Minimum element in [25, 22, 64] is 22. Swap 22 with 25. Array becomes [11, 12, 22, 25, 64].

Iteration 4:

• Minimum element in [25, 64] is 25. Swap 25 with 25 (no change). Array remains [11, 12, 22, 25, 64].

The array is sorted: [11, 12, 22, 25, 64].

Time Complexity: O(n²) in all cases (best, average, worst) because it always performs n*(n-1)/2 comparisons.

Space Complexity: O(1) as it sorts in-place.

3. Insertion Sort

Insertion Sort builds the final sorted array one item at a time. It is much less efficient on large lists than more advanced algorithms such as quicksort, heapsort, or merge sort. However, it has some advantages: it is simple to implement, efficient for small data sets, and efficient for data sets that are already substantially sorted.

Algorithm Steps:

1. Iterate from arr[1] to arr[n].
2. For each element (key), compare it with its predecessor.
3. If the key element is smaller than its predecessor, shift the predecessor to the right and continue comparing with the preceding element.
4. Repeat this process until the correct position for the key element is found.
5. Insert the key element into its correct position.

Example: Consider the array [12, 11, 13, 5, 6]

Iteration 1 (element 11):

• 11 < 12. Shift 12 to the right. Insert 11. Array: [11, 12, 13, 5, 6].

Iteration 2 (element 13):

• 13 > 12. No shift needed. Array: [11, 12, 13, 5, 6].

Iteration 3 (element 5):

• 5 < 13. Shift 13. Array: [11, 12, 5, 13, 6].
• 5 < 12. Shift 12. Array: [11, 5, 12, 13, 6].
• 5 < 11. Shift 11. Array: [5, 11, 12, 13, 6]. Insert 5. Array: [5, 11, 12, 13, 6].

Iteration 4 (element 6):

• 6 < 13. Shift 13. Array: [5, 11, 12, 6, 13].
• 6 < 12. Shift 12. Array: [5, 11, 6, 12, 13].
• 6 < 11. Shift 11. Array: [5, 6, 11, 12, 13]. Insert 6. Array: [5, 6, 11, 12, 13].

The array is sorted: [5, 6, 11, 12, 13].

Time Complexity: O(n²) in the worst and average case. O(n) in the best case (already sorted).

Space Complexity: O(1) as it sorts in-place.

4. Merge Sort

Merge Sort is a divide and conquer algorithm. It divides the input array into two halves, calls itself for the two halves, and then merges the two sorted halves. This process continues recursively until the base case (an array with zero or one element) is reached.

Algorithm Steps:

1. If the array has more than one element, split it into two halves.
2. Recursively sort the two halves using Merge Sort.
3. Merge the two sorted halves into a single sorted array.

The merging process involves comparing elements from the two sorted halves and placing the smaller element into a temporary array. Once one half is exhausted, the remaining elements of the other half are appended.

Example: Consider the array [38, 27, 43, 3, 9, 82, 10]

The array is recursively divided until single elements are reached:

• [38], [27], [43], [3], [9], [82], [10]

Then, they are merged and sorted:

• Merge [38], [27] -> [27, 38]
• Merge [43], [3] -> [3, 43]
• Merge [9], [82] -> [9, 82]
• Merge [10] (single element)

Continue merging:

• Merge [27, 38], [3, 43] -> [3, 27, 38, 43]
• Merge [9, 82], [10] -> [9, 10, 82]

Finally, merge the two larger sorted arrays:

• Merge [3, 27, 38, 43], [9, 10, 82] -> [3, 9, 10, 27, 38, 43, 82]

The array is sorted: [3, 9, 10, 27, 38, 43, 82].

Time Complexity: O(n log n) in all cases (best, average, worst). The dividing step takes O(log n) time, and the merging step takes O(n) time.

Space Complexity: O(n) due to the temporary array used for merging.

5. Quick Sort

Quick Sort is another efficient divide and conquer sorting algorithm. It picks an element as a 'pivot' and partitions the given array around the picked pivot. The pivot is placed at its correct sorted position. Elements smaller than the pivot are moved to its left, and elements greater than the pivot are moved to its right.

Algorithm Steps:

1. Choose a pivot element from the array.
2. Partition the array: Rearrange the elements such that all elements smaller than the pivot come before the pivot, and all elements greater than the pivot come after it. The pivot is now in its final sorted position.
3. Recursively apply the above steps to the sub-array of elements before the pivot and the sub-array of elements after the pivot.

Example: Consider the array [10, 80, 30, 90, 40, 50, 70]

Let's choose the last element (70) as the pivot.

Partitioning:

• Initialize index of smaller element (i) to -1.
• Iterate through the array from the first element up to (but not including) the pivot.
• If an element is smaller than the pivot, increment i and swap arr[i] with the current element.
• After the loop, swap arr[i+1] with the pivot. The pivot is now at index i+1.

Initial: [10, 80, 30, 90, 40, 50, 70], i = -1

• 10 < 70: i=0, swap(arr[0], arr[0]) -> [10, 80, 30, 90, 40, 50, 70]
• 80 > 70: no swap
• 30 < 70: i=1, swap(arr[1], arr[2]) -> [10, 30, 80, 90, 40, 50, 70]
• 90 > 70: no swap
• 40 < 70: i=2, swap(arr[2], arr[4]) -> [10, 30, 40, 90, 80, 50, 70]
• 50 < 70: i=3, swap(arr[3], arr[5]) -> [10, 30, 40, 50, 80, 90, 70]

After loop, swap arr[i+1] (arr[4]) with pivot (arr[6]): swap(arr[4], arr[6]) -> [10, 30, 40, 50, 70, 90, 80]. Pivot (70) is at index 4.

Now recursively sort the left part [10, 30, 40, 50] and the right part [90, 80].

Time Complexity:

• Best Case: O(n log n) - when the pivot always divides the array into two nearly equal halves.
• Average Case: O(n log n).
• Worst Case: O(n²) - when the pivot is always the smallest or largest element (e.g., already sorted array and picking first/last element as pivot).

Space Complexity: O(log n) on average due to recursion stack. O(n) in the worst case.

Searching Algorithms

Searching is the process of finding a specific element (key) within a data structure. The efficiency of a search algorithm depends on the data structure and whether it is sorted or not.

1. Linear Search (Sequential Search)

Linear Search is the simplest searching algorithm. It sequentially checks each element of the list until a match is found or the whole list has been searched. It works on any type of list, sorted or unsorted.

Algorithm Steps:

1. Start from the first element of the list.
2. Compare the current element with the target value.
3. If they match, return the index of the current element.
4. If they do not match, move to the next element.
5. Repeat steps 2-4 until the end of the list is reached.
6. If the target value is not found after searching the entire list, return an indicator that the element is not present (e.g., -1).

Example: Search for 5 in the list [3, 7, 5, 9, 1]

• Compare 3 with 5. No match.
• Compare 7 with 5. No match.
• Compare 5 with 5. Match found! Return index 2.

Time Complexity:

• Best Case: O(1) - when the element is found at the first position.
• Worst Case: O(n) - when the element is at the last position or not present.
• Average Case: O(n).

Space Complexity: O(1).

2. Binary Search

Binary Search is an efficient algorithm for finding an item from a sorted list of items. It works by repeatedly dividing the search interval in half. Begin with an interval covering the whole list. If the value of the search key is less than the item in the middle of the interval, narrow the interval to the lower half. Otherwise, narrow it to the upper half. Repeatedly check until the value is found or the interval is empty.

Prerequisite: The list MUST be sorted.

Algorithm Steps:

1. Initialize low = 0 and high = n-1 (where n is the number of elements).
2. While low <= high:
• Calculate mid = (low + high) / 2 (integer division).
• If arr[mid] == key, return mid (element found).
• If arr[mid] < key, the key might be in the right half. Set low = mid + 1.
• If arr[mid] > key, the key might be in the left half. Set high = mid - 1.
3. If the loop finishes without finding the key, return -1 (element not found).

Example: Search for 23 in the sorted array [2, 3, 4, 10, 40, 43, 45, 50, 60, 70]

n = 10. low = 0, high = 9.

Iteration 1:

• mid = (0 + 9) / 2 = 4. arr[4] = 40.
• 40 > 23. So, the key must be in the left half. Set high = mid - 1 = 4 - 1 = 3.
• Now, low = 0, high = 3.

Iteration 2:

• mid = (0 + 3) / 2 = 1. arr[1] = 3.
• 3 < 23. So, the key must be in the right half. Set low = mid + 1 = 1 + 1 = 2.
• Now, low = 2, high = 3.

Iteration 3:

• mid = (2 + 3) / 2 = 2. arr[2] = 4.
• 4 < 23. So, the key must be in the right half. Set low = mid + 1 = 2 + 1 = 3.
• Now, low = 3, high = 3.

Iteration 4:

• mid = (3 + 3) / 2 = 3. arr[3] = 10.
• 10 < 23. So, the key must be in the right half. Set low = mid + 1 = 3 + 1 = 4.
• Now, low = 4, high = 3.

Since low (4) is now greater than high (3), the loop terminates. The element 23 is not found.

Let's try searching for 40 in the same array.

n = 10. low = 0, high = 9.

Iteration 1:

• mid = (0 + 9) / 2 = 4. arr[4] = 40.
• arr[mid] == key. Match found! Return index 4.

Time Complexity:

• Best Case: O(1) - when the element is found at the middle position in the first check.
• Worst Case: O(log n) - when the element is found at the last possible step or not present.
• Average Case: O(log n).

Space Complexity: O(1) for iterative implementation. O(log n) for recursive implementation due to call stack.

Hashing

Hashing is a technique used to index and retrieve keys in a data structure, such as a hash table. It involves using a hash function to compute an index, also known as a hash code, into an array of bucket or slots. The goal is to make data retrieval as fast as possible (ideally O(1) on average).

1. Hash Table

A hash table (or hash map) is a data structure that implements an associative array abstract data type, a structure that can map keys to values. It uses a hash function to compute an index into an array of buckets or slots, from which the desired value can be found.

2. Hash Function

A hash function is a function that maps data of arbitrary size to data of a fixed size. The values returned by a hash function are called hash codes, hash values, or simply hashes. A good hash function should:

• Be deterministic: The same key should always produce the same hash code.
• Be efficient to compute.
• Distribute keys uniformly across the hash table to minimize collisions.
• Handle different types of keys (e.g., strings, integers).

Common Hash Function Techniques:

• Division Method: h(k) = k mod m, where k is the key and m is the size of the hash table.
• Multiplication Method: h(k) = floor(m * (k * A mod 1)), where A is a constant between 0 and 1.
• Universal Hashing: A family of hash functions is chosen, and a function is randomly selected from the family at runtime. This helps in achieving good average-case performance regardless of the input.

3. Collisions

A collision occurs when two different keys hash to the same index in the hash table. Since only one element can occupy a slot, collisions must be handled. Common collision resolution techniques include:

4. Collision Resolution Techniques

a) Separate Chaining:

In separate chaining, each bucket in the hash table stores a pointer to a linked list (or another data structure like a balanced binary search tree) of all elements that hash to that bucket. When a collision occurs, the new element is simply added to the linked list at that index.

• Pros: Simple to implement, handles high load factors well.
• Cons: Requires extra memory for linked list nodes, performance can degrade to O(n) in the worst case (all keys hash to the same bucket).

b) Open Addressing:

In open addressing, all elements are stored directly within the hash table array itself. When a collision occurs, the algorithm probes for an alternative empty slot according to a specific probing sequence.

Types of Open Addressing:

• Linear Probing: If slot h(k) is occupied, try h(k)+1, h(k)+2, ..., wrapping around the table if necessary. This can lead to primary clustering, where occupied slots tend to form long runs.
• Quadratic Probing: If slot h(k) is occupied, try h(k) + 1², h(k) + 2², h(k) + 3², ... This helps reduce primary clustering but can lead to secondary clustering (keys that initially hash to the same location follow the same probe sequence).
• Double Hashing: Uses a second hash function to determine the step size for probing. If h1(k) is occupied, try h1(k) + h2(k), h1(k) + 2*h2(k), h1(k) + 3*h2(k), ... This generally provides the best distribution and avoids clustering issues effectively.

Load Factor (α):

The load factor is defined as α = n / m, where n is the number of elements and m is the number of slots in the hash table. It represents how full the hash table is. For open addressing, the load factor must be less than 1. For separate chaining, it can be greater than 1.

Time Complexity of Hashing:

• Average Case (Insertion, Deletion, Search): O(1) - assuming a good hash function and collision resolution strategy.
• Worst Case (Insertion, Deletion, Search): O(n) - occurs with poor hash functions or excessive collisions (e.g., all keys hashing to the same slot in separate chaining, or primary/secondary clustering in open addressing).