DSA in Java Searching and Sorting

Searching

Searching is the process of finding the location or presence of a specific element (called the “key”) within a data structure such as an array, list, or tree.

It is a fundamental operation in data structures, used to retrieve data efficiently.

Types of Searching Techniques:

Linear Search (Sequential Search):

 In Linear Search, each element of the list is sequentially compared with the key until the key is found or the end of the list is reached.

Algorithm Steps:

• Start from the first element.

• Compare each element with the key.

• If the key matches, return the index.

• If the end is reached without a match, report “element not found”.

Time Complexity:

• Best Case: O(1) (if key is the first element)

• Worst Case: O(n) (if key is last or not present)

• Average Case: O(n)

Space Complexity: O(1)

Advantages:

• Simple to implement.

• Can be applied to unsorted or sorted lists.

Disadvantages:

• Inefficient for large datasets.

Binary Search:

Description:
Binary Search is applicable only to sorted lists. It works by repeatedly dividing the list into two halves and comparing the key with the middle element.

Algorithm Steps:

• Calculate the middle index.

• If the key equals the middle element, return index.

• If the key is less, search the left half.

• If the key is greater, search the right half.

• Repeat until the key is found or sublist is empty.

Time Complexity:

• Best Case: O(1)

• Worst Case: O(log n)

• Average Case: O(log n)

Space Complexity:

• Iterative: O(1)

• Recursive: O(log n) (due to function call stack)

Advantages:

• Very efficient for large, sorted datasets.

Disadvantages:

• Requires the list to be sorted prior to searching.

Comparison: Linear Search vs Binary Search

Applications of Searching:

Database Systems (record retrieval)
Information retrieval systems (search engines)
Spell-checkers (dictionary search)
Pattern matching algorithms (e.g., KMP, Rabin-Karp)
Gaming and AI (state space search)

Limitations of Searching:

Linear Search: Inefficient for large datasets.
Binary Search: Requires data to be sorted beforehand.

Sorting

Sorting is the process of arranging data elements (numbers, characters, or objects) in a specific order, either ascending or descending.

Sorting is a fundamental operation in computer science used to simplify tasks like searching, merging, and data representation.

Types of Sorting Techniques:

Bubble Sort:

 Adjacent elements are repeatedly compared and swapped if they are in the wrong order. After each pass, the largest element “bubbles” to its correct position.

Time Complexity:

• Best Case: O(n) (already sorted)

• Average Case: O(n²)

• Worst Case: O(n²)

Space Complexity: O(1)
Stability: Yes

Advantages:

• Simple and easy to understand.

Disadvantages:

• Very inefficient for large datasets.

Selection Sort:

Description:
In every pass, the smallest (or largest) element is selected from the unsorted part and placed at its correct position.

Time Complexity:

• Best, Average, Worst Case: O(n²)

Space Complexity: O(1)
Stability: No

Advantages:

• Easy to implement.

• Works well on small lists.

Disadvantages:

• Performs poorly on large data sets.

Insertion Sort:

 Builds the sorted array by inserting each new element into its correct position among previously sorted elements.

Time Complexity:

• Best Case: O(n) (when nearly sorted)

• Average & Worst Case: O(n²)

Space Complexity: O(1)
Stability: Yes

Advantages:

• Efficient for small or nearly sorted datasets.

Disadvantages:

• Inefficient for large datasets.

Merge Sort (Divide and Conquer):

The array is divided into halves, each half is sorted recursively, and then the sorted halves are merged.

 Time Complexity:

• Best, Average, Worst Case: O(n log n)

Space Complexity: O(n) (due to temporary arrays)
Stability: Yes

Advantages:

• Consistent performance.

• Very efficient for large data sets.

Disadvantages:

• Requires extra memory (O(n)).

Quick Sort (Divide and Conquer):

 A pivot element is chosen to partition the array into two parts, and these parts are sorted recursively.

Time Complexity:

• Best, Average Case: O(n log n)

• Worst Case: O(n²) (rare, depends on pivot selection)

Space Complexity: O(log n) (for recursion stack)
Stability: No

Advantages:

• Faster in practice compared to other sorting methods.

• In-place sorting.

Disadvantages:

• Worst-case time complexity can degrade to O(n²).

Complexity Comparison Table:

Applications of Sorting:

Data Searching: Speeds up binary search.
Data Processing: Eases tasks like merging, reporting.
Databases: Indexing, range queries.
Graphics: Z-buffer algorithms in rendering.

Limitations:

Bubble, Selection, Insertion Sorts are slow for large datasets.
Merge Sort requires additional space.
Quick Sort worst-case performance is poor if the pivot is badly chosen.

Linear Search

Linear Search, also known as Sequential Search, is the simplest search algorithm that checks every element in the list one by one from the beginning to the end until the required element (key) is found or the list ends.

Algorithm Steps:

• Start from the first element of the array.

• Compare the key with the current element.

• If a match is found, return the index.

• Otherwise, move to the next element.

• If the end of the array is reached and no match is found, return “element not found”.

C Program Example:

#include <stdio.h>

int linearSearch(int arr[], int n, int key) {

    for(int i = 0; i < n; i++) {

        if(arr[i] == key)

            return i; // Element found at index i

    }

    return -1; // Element not found

}

int main() {

    int arr[] = {5, 8, 3, 9, 4};

    int key = 9;

    int n = sizeof(arr)/sizeof(arr[0]);

    int result = linearSearch(arr, n, key);

    if(result == -1)

        printf(“Element not found.”);

    else

        printf(“Element found at index: %d”, result);

    return 0;

}

Time Complexity:

Space Complexity: O(1)

Advantages:

Easy to understand and implement.
Works on both sorted and unsorted data.
No extra space required.

Disadvantages:

Slow for large datasets.
Inefficient compared to Binary Search for sorted data.

Applications:

Useful when the list is small or unsorted.
Searching in arrays, linked lists, or simple files.
Suitable for searching data in real-time applications where data is limited.

Binary Search

Binary Search is an efficient searching algorithm that finds the position of a target (key) element in a sorted list or array by repeatedly dividing the search interval into two halves.

Binary Search works only if the data is sorted (ascending or descending order).
It is based on the Divide and Conquer strategy.

Working Principle:

• Determine the middle element of the array.

• Compare the target (key) with the middle element:

• If the key is equal to the middle element — search successful.

• If the key is smaller — search the left sub-array.

• If the key is greater — search the right sub-array.

• Repeat this process until the key is found or the sub-array size becomes zero.

Algorithm (Ascending Order):

1. Initialize low = 0, high = n – 1.
2. Repeat until low > high:
3. mid = (low + high) / 2
4. If key == arr[mid], return mid.
5. If key < arr[mid], set high = mid – 1.
6. If key > arr[mid], set low = mid + 1.
7. If not found, return -1.

C Program (Iterative Version):

#include <stdio.h>

int binarySearch(int arr[], int n, int key) {

    int low = 0, high = n – 1, mid;

    while (low <= high) {

        mid = (low + high) / 2;

        if (arr[mid] == key)

            return mid; // Element found

        else if (arr[mid] < key)

            low = mid + 1; // Search in right half

        else

            high = mid – 1; // Search in left half

    }

    return -1; // Element not found

}

int main() {

    int arr[] = {2, 5, 8, 12, 16, 23, 38};

    int n = sizeof(arr)/sizeof(arr[0]);

    int key = 16;

    int result = binarySearch(arr, n, key);

    if(result == -1)

        printf(“Element not found.”);

    else

        printf(“Element found at index: %d”, result);

    return 0;

}

Time Complexity:

Space Complexity:

• O(1) for iterative version

• O(log n) for recursive version

Advantages:

Very fast for large datasets compared to Linear Search.
Time complexity O(log n) ensures quick execution.
Simple to implement for sorted data.

Disadvantages:

Works only on sorted data.
Requires pre-processing (sorting) if data is unsorted.

Applications:

Database record searching.
File system lookups.
Standard libraries in C++, Java, Python use Binary Search for internal functions.

Selection Sort

Selection Sort is a simple sorting algorithm that divides the array into two parts: the sorted part at the beginning and the unsorted part at the end.
In every iteration, the algorithm selects the smallest (or largest) element from the unsorted part and moves it to the sorted part.

Working Principle:

• Start with the first element.

• Find the smallest (or largest) element in the unsorted portion.

• Swap it with the first unsorted element.

• Move the boundary of the sorted portion by one position to the right.

• Repeat until the entire array is sorted.

Algorithm Steps:

• Repeat for each position from 0 to n-2:

• Assume the element at index i is the minimum.

• Compare this element with the rest of the array to find the true minimum.

• Swap the found minimum with the element at index i.

C Program Example:

#include <stdio.h>

void selectionSort(int arr[], int n) {

    int i, j, minIndex, temp;

    for(i = 0; i < n-1; i++) {

        minIndex = i;

        for(j = i+1; j < n; j++) {

            if(arr[j] < arr[minIndex])

                minIndex = j;

        }

        // Swap the found minimum with the first element

        temp = arr[minIndex];

        arr[minIndex] = arr[i];

        arr[i] = temp;

    }

}

int main() {

    int arr[] = {29, 10, 14, 37, 13};

    int n = sizeof(arr)/sizeof(arr[0]);

    selectionSort(arr, n);

    printf(“Sorted array: “);

    for(int i = 0; i < n; i++)

        printf(“%d “, arr[i]);

    return 0;

}

Time Complexity:

Space Complexity: O(1) (In-place sorting)
Stability: Not stable in standard implementation.

Advantages:

Very simple to understand and implement.
Performs well on small datasets.
Requires no additional memory.

 Disadvantages:

Inefficient for large datasets (time complexity O(n²)).
Performs the same number of comparisons regardless of the initial order of data.

Applications:

Suitable for small datasets where simplicity is preferred over performance.
When memory space is strictly limited.
Useful when data swapping cost is high and minimizing the number of swaps is important.

Insertion Sort

Insertion Sort is a simple comparison-based sorting algorithm that builds the final sorted array one element at a time.
It is much like the way we sort playing cards in our hands — by taking one card at a time and inserting it at the correct position relative to the already sorted cards.

Working Principle:

The list is divided into two parts:

• Sorted part (initially containing the first element)

• Unsorted part (contains the rest of the elements)

Each element from the unsorted part is picked and inserted into its correct position in the sorted part.

Algorithm Steps:

• Start from the second element (index 1).

• Compare it with the elements before it.

• Move all elements greater than the key to one position ahead.

• Insert the key at its correct position.

• Repeat until the entire array is sorted.

C Program Example:

#include <stdio.h>

void insertionSort(int arr[], int n) {

    int i, key, j;

    for(i = 1; i < n; i++) {

        key = arr[i];

        j = i – 1;

        // Move elements greater than key to one position ahead

        while(j >= 0 && arr[j] > key) {

            arr[j + 1] = arr[j];

            j = j – 1;

        }

        arr[j + 1] = key; // Insert key at correct position

    }

}

int main() {

    int arr[] = {12, 11, 13, 5, 6};

    int n = sizeof(arr)/sizeof(arr[0]);

    insertionSort(arr, n);

    printf(“Sorted array: “);

    for(int i = 0; i < n; i++)

        printf(“%d “, arr[i]);

    return 0;

}

Time Complexity:

Space Complexity: O(1) (in-place sorting)
Stability: Yes (does not change the order of equal elements)

Advantages:

Very simple to understand and implement.
Efficient for small datasets.
Stable sort — preserves the order of equal elements.
Performs well on nearly sorted data.

Disadvantages:

Inefficient for large datasets (O(n²) time).
Not suitable when data size is very large.

Applications:

Suitable for small or nearly sorted datasets.
Used in adaptive sorting algorithms.
often used in teaching sorting concepts.

Quick Sort

Quick Sort is a highly efficient sorting algorithm based on the Divide and Conquer technique.
It works by partitioning the array into two sub-arrays, such that all elements in the left sub-array are less than or equal to a chosen element called the pivot, and all elements in the right sub-array are greater than the pivot.
These sub-arrays are then sorted recursively.

Working Principle:

• Choose a pivot element from the array.

• Partition the array into two parts:

• Elements smaller than or equal to pivot on the left.

• Elements greater than pivot on the right.

• Recursively apply Quick Sort to the left and right sub-arrays.

• Combine the sorted parts to get the final sorted array.

Algorithm Steps:

• If the array has one or zero elements, return (already sorted).

• Choose a pivot (commonly the first, last, or middle element).

• Rearrange the array such that:

• Elements < pivot are to the left.

• Elements > pivot are to the right.

• Recursively apply steps 1–3 to the sub-arrays.

C Program Example:

#include <stdio.h>

void swap(int* a, int* b) {

    int t = *a;

    *a = *b;

    *b = t;

}

int partition(int arr[], int low, int high) {

    int pivot = arr[high]; // pivot element

    int i = (low – 1);

    for(int j = low; j <= high – 1; j++) {

        if(arr[j] < pivot) {

            i++;

            swap(&arr[i], &arr[j]);

        }

    }

    swap(&arr[i + 1], &arr[high]);

    return (i + 1);

}

void quickSort(int arr[], int low, int high) {

    if(low < high) {

        int pi = partition(arr, low, high);

        quickSort(arr, low, pi – 1);  // Left sub-array

        quickSort(arr, pi + 1, high); // Right sub-array

    }

}

int main() {

    int arr[] = {10, 7, 8, 9, 1, 5};

    int n = sizeof(arr)/sizeof(arr[0]);

    quickSort(arr, 0, n – 1);

    printf(“Sorted array: “);

    for(int i = 0; i < n; i++)

        printf(“%d “, arr[i]);

    return 0;

}

Time Complexity:

Space Complexity: O(log n) (for recursive stack)
Stability: Not stable (can be made stable with modifications)

Advantages:

Very fast for large datasets.
In-place sorting — requires very little additional memory.
Generally faster than other O(n log n) algorithms like Merge Sort.

Disadvantages:

Worst-case time complexity is O(n²) (though rare with good pivot selection).
Not stable by default.

Applications:

Widely used in system libraries (C++, Java, Python).
Effective for large, unsorted datasets.
Used in file sorting, database systems, and real-time systems.

Merge Sort

Merge Sort is an efficient, stable, and comparison-based Divide and Conquer sorting algorithm.
It divides the input array into two halves, recursively sorts each half, and then merges the sorted halves to produce the sorted result.

Working Principle:

Divide: Split the array into two halves.
Conquer: Recursively sort both halves.
Combine: Merge the two sorted halves into a single sorted array.

Algorithm Steps:

• If the array has one or no elements, it is already sorted.

• Find the middle point to divide the array into two halves.

• Recursively apply Merge Sort to the left and right halves.

• Merge the two sorted halves to produce the sorted array.

C Program Example:

#include <stdio.h>

void merge(int arr[], int left, int mid, int right) {

    int i, j, k;

    int n1 = mid – left + 1; // Size of left sub-array

    int n2 = right – mid;    // Size of right sub-array

    int L[n1], R[n2]; // Temporary arrays

    // Copy data to temp arrays L[] and R[]

    for(i = 0; i < n1; i++)

        L[i] = arr[left + i];

    for(j = 0; j < n2; j++)

        R[j] = arr[mid + 1 + j];

    i = 0; j = 0; k = left;

    // Merge the temp arrays back into arr[]

    while(i < n1 && j < n2) {

        if(L[i] <= R[j]) {

            arr[k] = L[i];

            i++;

        }

        else {

            arr[k] = R[j];

            j++;

        }

        k++;

    }

    // Copy remaining elements

    while(i < n1) {

        arr[k] = L[i];

        i++; k++;

    }

    while(j < n2) {

        arr[k] = R[j];

        j++; k++;

    }

}

void mergeSort(int arr[], int left, int right) {

    if(left < right) {

        int mid = left + (right – left) / 2;

        mergeSort(arr, left, mid);      // Sort first half

        mergeSort(arr, mid + 1, right); // Sort second half

        merge(arr, left, mid, right);   // Merge sorted halves

    }

}

int main() {

    int arr[] = {12, 11, 13, 5, 6, 7};

    int n = sizeof(arr)/sizeof(arr[0]);

    mergeSort(arr, 0, n – 1);

    printf(“Sorted array: “);

    for(int i = 0; i < n; i++)

        printf(“%d “, arr[i]);

    return 0;

}

Time Complexity:

Space Complexity: O(n) (due to auxiliary arrays)
Stability: Yes (preserves order of equal elements)

Advantages:

Stable Sorting Algorithm.
Always guarantees O(n log n) time complexity.
Best suited for sorting linked lists and large datasets.

Disadvantages:

Requires extra memory space proportional to the array size (O(n)).
Not as efficient as Quick Sort for small datasets due to overhead of recursive calls and copying data.

Applications:

Used in external sorting where large data cannot fit into memory.
Suitable for sorting linked lists.
Applied in multi-threaded applications.

Shell Sort

Shell Sort is an extended version of Insertion Sort, designed to reduce the total number of shifting operations.
It works by comparing elements separated by a gap and gradually reducing the gap to 1, at which point it becomes an ordinary Insertion Sort.

It is named after Donald L. Shell, who introduced this algorithm in 1959.

Working Principle:

• Choose an initial gap size (typically n/2).

• Sort the elements at this gap (using a modified Insertion Sort).

• Reduce the gap and repeat step 2.

• When the gap reduces to 1, perform a final Insertion Sort.

Algorithm Steps:

• Initialize the gap = n/2.

• Perform a gapped Insertion Sort for this gap size.

• Reduce the gap using a sequence (e.g., gap = gap/2).

• Repeat until gap = 1.

C Program Example:

#include <stdio.h>

void shellSort(int arr[], int n) {

    for(int gap = n/2; gap > 0; gap /= 2) {

        for(int i = gap; i < n; i++) {

            int temp = arr[i];

            int j;

            // Perform gapped insertion sort

            for(j = i; j >= gap && arr[j – gap] > temp; j -= gap) {

                arr[j] = arr[j – gap];

            }

            arr[j] = temp;

        }

    }

}

int main() {

    int arr[] = {12, 34, 54, 2, 3};

    int n = sizeof(arr)/sizeof(arr[0]);

    shellSort(arr, n);

    printf(“Sorted array: “);

    for(int i = 0; i < n; i++)

        printf(“%d “, arr[i]);

    return 0;

}

Time Complexity:

Space Complexity: O(1) (In-place sorting)
Stability: Not stable (relative order of equal elements may change)

Advantages:

Faster than Insertion and Bubble Sort, especially for medium-sized arrays.
Requires no extra space (in-place sorting).
Easy to implement.

Disadvantages:

Performance heavily depends on the gap sequence chosen.
Not as fast as Quick Sort or Merge Sort for very large data sets.
Unstable algorithm.

Applications:

Used in scenarios where memory is limited but faster sorting than Bubble/Insertion is needed.
Suitable for medium-sized data sets.
Useful when in-place sorting is required.

Comparison of Sorting Techniques

Key to Terms:

• Stable: Maintains the relative order of equal elements.

• In-place: Requires only a small, constant amount O(1) of extra storage space.

• Divide & Conquer: Recursively divide the problem into subproblems.

Important Observations:

Quick Sort is fastest in most practical cases but unstable.
Merge Sort is best for linked lists and stability but uses extra space.
Heap Sort is in-place and efficient but not stable.
Shell Sort improves on Insertion but depends on gap sequence.
Counting, Radix, Bucket Sorts are suitable for special cases (non-comparison sorts).

Best Technique Selection (Based on Situation):