Algorithms and Object Oriented Programming – Part 1

Search Algorithms

Linear Search, also known as sequential search, is a simple algorithm for finding a particular value in a list or array. The basic steps involves in iterating over each and every element of the list, until you find the required item. Time Complexity – O(n) where n is the total number of elements in your list.

Linear search is useful for searching small or unsorted data sets, or for searching for a specific element in an unordered list. For example, a linear search algorithm can be used to find an element or filter by certain criteria in a small list of unsorted elements, eg. find all the even numbers in a list.

Here is the example code of linear search implemented in object-oriented style:

class LinearSearchImpl {
    int[] arr;
    
    // Constructor that initializes the array
    LinearSearchImpl(int[] arr) {
        this.arr = arr;
    }
    
    // Method that performs the linear search for "target"
    int linearSearch(int target) {
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] == target) {
                return i;
            }
        }
        return -1; // target value not found in the array
    }
}

// Example usage
int[] arr = {1, 2, 3, 4, 5};
LinearSearchImpl search = new LinearSearchImpl(arr);
int index = search.linearSearch(3); // returns 2

Binary Search : Binary search is a more efficient algorithm for searching a sorted array. Here are the basic steps involved:

1. Start with the middle element of the sorted array.
   • If the middle element matches the target value, stop the search and return the index of the middle element.
   • If the middle element is greater than the target value, search the left half of the array.
   • If the middle element is less than the target value, search the right half of the array.
2. Repeat step 1 until either the target value is found or there are no more elements to search.
3. If the target value is not found after all elements have been searched, return -1 indicating that the value is not in the array.

Binary search is used when searching large, sorted data sets or arrays, where the elements are ordered. It is commonly used in computer science, such as in searching for a specific record in a database, or in searching for a word in a dictionary. Binary search can also be used in game development for collision detection, or in mathematical computations to find roots or solve equations.

The time complexity of Binary Search is O(log₂ n ) since the number of search elements reduces to half with every iteration.

class BinarySearchImpl {
    int[] arr;
    
    // Constructor that initializes the sorted array
    BinarySearchImpl(int[] arr) {
        this.arr = arr;
    }
    
    // Method that performs the binary search
    int binarySearch(int target) {
        int left = 0;
        int right = arr.length - 1;
        
        while (left <= right) {
            int mid = left + (right - left) / 2;
            
            if (arr[mid] == target) {
                return mid;
            } else if (arr[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        
        return -1; // target value not found in the sorted array
    }
}

// Example usage
int[] arr = {1, 2, 3, 4, 5};
BinarySearchImpl search = new BinarySearchImpl(arr);
int index = search.binarySearch(3); // returns 2

Sorting Algorithms

Bubble Sort : Bubble Sort is a simple sorting algorithm that 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. Here are the steps for Bubble Sort. Here are steps involved in a simple bubble sort algorithm:

1. Starting from the beginning of the array, compare adjacent elements in pairs.
2. If the first element is greater than the second element, swap them.
3. Move on to the next pair of elements and repeat step 2.
4. Continue iterating through the array until no more swaps are needed.

Bubble sort has high time complexity of O(n²) and is not suitable for large datasets.

class BubbleSort {
    private int[] data;

    // Constructor that initializes the object with input data
    public BubbleSort(int[] input) {
        this.data = input;
    }
  
  // Bubble sort algorithm implementation
    public int[] bubbleSort() {
        int n = this.data.length;
        for (int i = 0; i < n-1; i++) {
               // n passes for n elements.
            for (int j = 0; j < n-i-1; j++) {
                if (this.data[j] > this.data[j+1]) {
                    int temp = this.data[j];
                    this.data[j] = this.data[j+1];
                    this.data[j+1] = temp;
                }
            }
        }
        return this.data;
    }
}

// Example usage:
int[] arr = {5, 2, 9, 3, 8, 6};
BubbleSort.bubbleSort(arr);
System.out.println(Arrays.toString(arr)); // Output: [2, 3, 5, 6, 8, 9]

Insertion Sort :

The insertion sort algorithm sorts an array by comparing each element with the elements before it, and then placing the current element in its proper position within the sorted portion of the array. Here are the steps of the insertion sort algorithm:

1. Iterate through the array from the second element to the last element.
2. At each iteration, select the current element to be inserted into the sorted portion of the array.
3. Compare the current element with the elements before it in the sorted portion of the array.
4. If the current element is smaller than the previous element, swap them.
5. Repeat step 4 until the current element is in its correct position within the sorted portion of the array.
6. Continue iterating through the array until all elements have been inserted into the sorted portion of the array.

The time complexity of the insertion sort algorithm is O(n^2), where n is the number of elements in the array.

public class InsertionSort {
    private int[] data;

    // Constructor that initializes the object with input data
    public InsertionSort(int[] input) {
        this.data = input;
    }

    // Insertion sort algorithm implementation
    public int[] sort() {
        int n = this.data.length;
        for (int i = 1; i < n; i++) {
            int key = this.data[i];
            int j = i - 1;
            while (j >= 0 && this.data[j] > key) {
                this.data[j + 1] = this.data[j];
                j = j - 1;
            }
            this.data[j + 1] = key;
        }
        return this.data;
    }
}

Selection Sort :

Selection sort is a simple sorting algorithm that sorts an array by repeatedly finding the minimum element from the unsorted portion of the array and swapping it with the first element of the unsorted portion. Here are the steps of the selection sort algorithm:

1. Iterate through the array from the first element to the second-to-last element.
2. At each iteration, select the current element as the minimum element.
3. Iterate through the remaining unsorted portion of the array to find the smallest element.
4. If the smallest element is smaller than the current element, swap them.
5. Repeat steps 2-4 until all elements have been sorted.

The time complexity of Selection Sort algorithm is O(n^2), where n is the number of elements in the array being sorted. Selection Sort has a space complexity of O(1), which means that it sorts the array in place and does not require any additional memory allocation beyond the input array itself.

public class SelectionSort {
    private int[] data;

    // Constructor that initializes the object with input data
    public SelectionSort(int[] input) {
        this.data = input;
    }

    // Selection sort algorithm implementation
    public int[] sort() {
        int n = this.data.length;
        for (int i = 0; i < n - 1; i++) {
            int minIndex = i;
            for (int j = i + 1; j < n; j++) {
                if (this.data[j] < this.data[minIndex]) {
                    minIndex = j;
                }
            }
            // Swap elements
            int temp = this.data[minIndex];
            this.data[minIndex] = this.data[i];
            this.data[i] = temp;
        }
        return this.data;
    }
}

Heap Sort :

Heap sort is a comparison-based sorting algorithm that uses the properties of a binary heap to sort an array. Heap Sort uses a data structure called a heap to sort elements in an array. A heap is a complete binary tree where the value of each node is greater than or equal to the values of its children. There are two types of heaps: max heaps and min heaps. In a max heap, the root node has the highest value in the tree, while in a min heap, the root node has the smallest value.

Here are the steps of the heap sort algorithm:

1. Build a binary heap from the input array.
2. Swap the root node with the last node in the heap.
3. Remove the last node from the heap and add it to the sorted portion of the array.
4. Re-heapify the remaining nodes in the heap.
5. Repeat steps 2-4 until all nodes have been added to the sorted portion of the array.

The time complexity of Heap Sort algorithm is O(nlog(n)) in all cases, where n is the number of elements in the array being sorted.

Heap Sort is useful when stability is not a concern, as it is not a stable sorting algorithm. It is also useful when the data set is relatively small, as it has a worst-case time complexity of O(n log n), which is not as efficient as Merge Sort or Quick Sort for large data sets. Heap Sort is often used in embedded systems, where memory is limited and algorithms with low memory overhead are preferred.

public class HeapSort {
    private int[] data;

    // Constructor that initializes the object with input data
    public HeapSort(int[] input) {
        this.data = input;
    }

    // Heap sort algorithm implementation
    public int[] sort() {
        int n = this.data.length;

        // Build a max heap from the input array, 
        // start from the last leaf node index at (n/2-1) and 
        // go all the way up to the root.
        for (int i = n / 2 - 1; i >= 0; i--) {
            heapify(n, i, 0);
        }

        // Extract elements from the heap in sorted order
     // swap the root node (index 0) with the last element in the heap (index i)
        for (int i = n - 1; i >= 0; i--) {
            // Move the root node to the end of the heap
            int temp = this.data[0];
            this.data[0] = this.data[i];
            this.data[i] = temp;

            // Re-heapify the remaining nodes in the heap
            heapify(i, 0, 0);
        }
        return this.data;
    }

    // Re-heapify method to maintain the heap property
    // remove elements from the heap and swap with the last element.
    // this ensures the largest element is at parent node.
    private void heapify(int size, int root, int k) {
        int largest = root;
        int left = 2 * root + 1; // left child node of root
        int right = 2 * root + 2; // right child node of root

    // NOTE: special case Only consider the first k elements if k is specified.
    if (k != 0) { 
        if (i >= k || left >= k || right >= k) 
           return; 
     }

        // Find the largest element among the root, left child, and right child
        if (left < size && this.data[left] > this.data[largest]) {
            largest = left;
        }
        if(right < size && this.data[right] > this.data[largest]){
            largest = right;
        }

        // Swap the root with the largest child if necessary
        if (largest != root) {
            int temp = this.data[root];
            this.data[root] = this.data[largest];
            this.data[largest] = temp;

            // Recursively re-heapify the affected subtree
            heapify(size, largest, 0);
        }
    }
}

Merge Sort : Merge sort is a divide-and-conquer algorithm that sorts an array by recursively dividing it into halves, sorting the halves, and then merging them back together. Here are the steps of the merge sort algorithm:

1. Divide the input array into two halves.
2. Recursively sort the left half of the array.
3. Recursively sort the right half of the array.
4. Merge the sorted left and right halves into a single sorted array.

The time complexity of Merge Sort algorithm is O(nlog(n)) in all cases, where n is the number of elements in the array being sorted. This is because the algorithm divides the input array into two halves, recursively sorts each half, and then merges the two sorted halves back together. The divide-and-conquer approach of the algorithm ensures that the time complexity remains at O(nlog(n)) in all cases, regardless of the distribution of elements in the input array.

In the worst case, Merge Sort requires additional space to store the temporary arrays during the merge step, which increases the space complexity of the algorithm to O(n). However, in most practical applications, the space requirements are not a limiting factor, and the time complexity of O(n*log(n)) makes Merge Sort an efficient and popular choice for sorting arrays.

Merge Sort is widely used in practice, especially for sorting large data sets, such as in database management systems, external sorting, and network sorting. It is also useful in parallel processing and distributed systems, where sorting can be performed simultaneously on different processors or nodes. Merge Sort is preferred when stability, predictable performance, and a worst-case time complexity of O(n log n) are important considerations.

public class MergeSort {
    private int[] data;

    // Constructor that initializes the object with input data
    public MergeSort(int[] input) {
        this.data = input;
    }

    // Merge sort algorithm implementation
    public int[] sort() {
        mergeSort(0, this.data.length - 1);
        return this.data;
    }

    // Recursive merge sort method
    private void mergeSort(int left, int right) {
        if (left < right) {
            // Find the middle index of the array
            int middle = left + (right - left) / 2;

            // Recursively sort the left half of the array
            mergeSort(left, middle);

            // Recursively sort the right half of the array
            mergeSort(middle + 1, right);

            // Merge the sorted left and right halves of the array
            merge(left, middle, right);
        }
    }

    // Merge method to merge the sorted left and right halves of the array
    private void merge(int left, int middle, int right) {
        // Create temporary arrays for the left and right halves of the array
        int[] leftArray = new int[middle + 1 - left];
        int[] rightArray = new int[right - middle];

        // Copy the elements from the left half of the array into the left temporary array
        for (int i = 0; i < leftArray.length; i++) {
            leftArray[i] = this.data[left + i];
        }

        // Copy the elements from the right half of the array into the right temporary array
        for (int i = 0; i < rightArray.length; i++) {
            rightArray[i] = this.data[middle + 1 + i];
        }

        // Merge the left and right temporary arrays back into the original array
        int i = 0;
        int j = 0;
        int k = left;

        while (i < leftArray.length && j < rightArray.length) {
            if (leftArray[i] <= rightArray[j]) {
                this.data[k] = leftArray[i];
                i++;
            } else {
                this.data[k] = rightArray[j];
                j++;
            }
            k++;

Quick Sort :

Quick sort is a divide-and-conquer algorithm that sorts an array by partitioning it into two sub-arrays around a pivot element, recursively sorting the sub-arrays, and then combining them together. Here are the steps of the quick sort algorithm:

1. Choose a pivot element from the array.
2. Partition the array into two sub-arrays: one with elements less than the pivot and another with elements greater than or equal to the pivot.
3. Recursively sort the sub-arrays by repeating steps 1 and 2.
4. Combine the sorted sub-arrays back together to form the final sorted array.

The time complexity of Quick Sort algorithm in the worst case is O(n^2), but on average it has a time complexity of O(nlog(n)). The worst case occurs when the pivot element is always the largest or the smallest element in the array, causing the partitioning to result in sub-arrays of size 1 and n-1. In the average case, the pivot element is chosen such that it partitions the array into two roughly equal-sized sub-arrays, leading to a balanced recursive tree of partitions and an overall time complexity of O(nlog(n)). However, in the best case, the pivot element always partitions the array into two equal-sized sub-arrays, resulting in a time complexity of O(n*log(n)) as well.

Quick Sort is also widely used in practice, especially in situations where the data set is large or when the efficiency of the algorithm is critical. It is commonly used in software libraries and programming languages, such as the C++ STL and Java’s Arrays.sort() method. Quick Sort is preferred when space complexity is important, as it is an in-place sorting algorithm that requires only O(log n) space. Quick Sort also has a best-case time complexity of O(n log n) and is efficient for average-case scenarios.

public class QuickSort {
    private int[] data;

    // Constructor that initializes the object with input data
    public QuickSort(int[] input) {
        this.data = input;
    }

    // Quick sort algorithm implementation
    public int[] sort() {
        quickSort(0, this.data.length - 1);
        return this.data;
    }

    // Recursive quick sort method
    private void quickSort(int left, int right) {
        if (left < right) {
            // Partition the array and get the pivot index
            int pivotIndex = partition(left, right);

            // Recursively sort the left and right sub-arrays
            quickSort(left, pivotIndex - 1);
            quickSort(pivotIndex + 1, right);
        }
    }

    // Partition method to partition the array into two sub-arrays around a pivot element
    private int partition(int left, int right) {
        // Choose the rightmost element as the pivot element
        int pivot = this.data[right];
        int i = left - 1;

        // Iterate over the array and swap elements to create the partition
        for (int j = left; j < right; j++) {
            if (this.data[j] < pivot) {
                i++;
                swap(i, j);
            }
        }

        // Place the pivot element at its final position in the partition
        swap(i + 1, right);

        // Return the index of the pivot element
        return i + 1;
    }

    // Swap method to swap two elements in the array
    private void swap(int i, int j) {
        int temp = this.data[i];
        this.data[i] = this.data[j];
        this.data[j] = temp;
    }
}