Sorting with Examples & Time Complexity for SDET

 

🔺 LinkedIn:https://www.linkedin.com/in/sidharth-shukla-77b53145/
🔺 Telegram Group: https://t.me/+FTf_NPb--GQ2ODhl

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. It has poor time complexity and is not suitable for large datasets. 

 

Selection Sort: 

 Selection sort divides the input list into two parts: the sorted part and the unsorted part. It repeatedly selects the smallest (or largest) element from the unsorted part and moves it to the sorted part. It has a time complexity of O(n^2). 

 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. It has a time complexity of O(n^2). 

 Merge Sort: 

 Merge sort is a divide-and-conquer algorithm that divides an array into two halves, sorts them separately, and then merges the sorted halves to produce a sorted array. It has a time complexity of O(n log n) and is stable. 

 Quick Sort: 

 Quick sort is also a divide-and-conquer algorithm that picks an element as a pivot and partitions the array around the pivot. It has an average time complexity of O(n log n) but can degrade to O(n^2) in the worst case. 

 Heap Sort: 

 Heap sort is based on the binary heap data structure. It builds a max-heap (or min-heap), repeatedly extracts the maximum (or minimum) element, and rebuilds the heap. It has a time complexity of O(n log n).

Sure, let's start with a Java code example for each sorting algorithm and explain their time and space complexities. We'll use the same array of integers for all the sorting algorithms.

Here's the array we'll use:

int[] arr = {5, 2, 9, 1, 5};

Bubble Sort:

public static void bubbleSort(int[] arr) {
    int n = arr.length;
    boolean swapped;
    do {
        swapped = false;
        for (int i = 1; i < n; i++) {
            if (arr[i - 1] > arr[i]) {
                // Swap arr[i-1] and arr[i]
                int temp = arr[i - 1];
                arr[i - 1] = arr[i];
                arr[i] = temp;
                swapped = true;
            }
        }
        n--;
    } while (swapped);
}

Time Complexity: O(n^2) - In the worst case, where the array is reverse-sorted, it takes n * (n-1) / 2 comparisons and swaps.

Space Complexity: O(1) - Bubble sort sorts the array in-place, so it doesn't require additional memory.

Selection Sort:

public static void selectionSort(int[] arr) {
    int n = arr.length;
    for (int i = 0; i < n - 1; i++) {
        int minIndex = i;
        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }
        // Swap arr[i] and arr[minIndex]
        int temp = arr[i];
        arr[i] = arr[minIndex];
        arr[minIndex] = temp;
    }
}

Time Complexity: O(n^2) - It always takes n * (n-1) / 2 comparisons and n swaps.

Space Complexity: O(1) - Similar to bubble sort, it sorts the array in-place.

Insertion Sort:

public static void insertionSort(int[] arr) {
    int n = arr.length;
    for (int i = 1; i < n; i++) {
        int key = arr[i];
        int j = i - 1;
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
}

Time Complexity: O(n^2) - In the worst case, where the array is reverse-sorted, it takes n * (n-1) / 2 comparisons and swaps.

Space Complexity: O(1) - Like the previous two algorithms, it sorts the array in-place.

Merge Sort:

public static void mergeSort(int[] arr, int left, int right) {
    if (left < right) {
        int mid = left + (right - left) / 2;
        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);
        merge(arr, left, mid, right);
    }
}

public static void merge(int[] arr, int left, int mid, int right) {
    int n1 = mid - left + 1;
    int n2 = right - mid;

    int[] leftArr = new int[n1];
    int[] rightArr = new int[n2];

    for (int i = 0; i < n1; i++) {
        leftArr[i] = arr[left + i];
    }
    for (int i = 0; i < n2; i++) {
        rightArr[i] = arr[mid + 1 + i];
    }

    int i = 0, j = 0;
    int k = left;
    while (i < n1 && j < n2) {
        if (leftArr[i] <= rightArr[j]) {
            arr[k] = leftArr[i];
            i++;
        } else {
            arr[k] = rightArr[j];
            j++;
        }
        k++;
    }

    while (i < n1) {
        arr[k] = leftArr[i];
        i++;
        k++;
    }

    while (j < n2) {
        arr[k] = rightArr[j];
        j++;
        k++;
    }
}

Time Complexity: O(n log n) - Merge sort has a time complexity of O(n log n) for all cases.

Space Complexity: O(n) - It requires additional memory for temporary arrays during the merge process.

Quick Sort:

public static void quickSort(int[] arr, int low, int high) {
    if (low < high) {
        int pivotIndex = partition(arr, low, high);
        quickSort(arr, low, pivotIndex - 1);
        quickSort(arr, pivotIndex + 1, high);
    }
}

public static int partition(int[] arr, int low, int high) {
    int pivot = arr[high];
    int i = low - 1;
    for (int j = low; j < high; j++) {
        if (arr[j] < pivot) {
            i++;
            // Swap arr[i] and arr[j]
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }
    // Swap arr[i+1] and arr[high] (pivot)
    int temp = arr[i + 1];
    arr[i + 1] = arr[high];
    arr[high] = temp;
    return i + 1;
}

Time Complexity: O(n log n) on average, but it can degrade to O(n^2) in the worst case.

Space Complexity: O(log n) - It uses a recursive call stack, so the space complexity depends on the recursion depth.

Heap Sort:

public static void heapSort(int[] arr) {
    int n = arr.length;

    // Build a max heap
    for (int i = n / 2 - 1; i >= 0; i--) {
        heapify(arr, n, i);
    }

    // Extract elements one by one from the heap
    for (int i = n - 1; i > 0; i--) {
        int temp = arr[0];
        arr[0] = arr[i];
        arr[i] = temp;
        heapify(arr, i, 0);
    }
}

public static void heapify(int[] arr, int n, int i) {
    int largest = i;
    int left = 2 * i + 1;
    int right = 2 * i + 2;

    if (left < n && arr[left] > arr[largest]) {
        largest = left;
    }

    if (right < n && arr[right] > arr[largest]) {
        largest = right;
    }

    if (largest != i) {
        int swap = arr[i];
        arr[i] = arr[largest];
        arr[largest] = swap;

        heapify(arr, n, largest);
    }
}

Time Complexity: O(n log n) - Heap sort has a time complexity of O(n log n) for all cases.

Space Complexity: O(1) - It sorts the array in-place, so it doesn't require additional memory.

These are the Java implementations of the mentioned sorting algorithms along with their time and space complexities. Depending on your specific requirements and the characteristics of your data, you can choose the most suitable sorting algorithm.

Sure, here are the time complexities of the sorting algorithms from best to worst:

1. Merge Sort:

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

2. Heap Sort:

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

3. Quick Sort:

   • Best Case: O(n log n)
   • Average Case: O(n log n)
   • Worst Case: O(n^2) (can be improved with randomized pivot selection)

4. Insertion Sort:

   • Best Case: O(n) (already sorted)
   • Average Case: O(n^2)
   • Worst Case: O(n^2)

5. Selection Sort:

   • Best Case: O(n^2)
   • Average Case: O(n^2)
   • Worst Case: O(n^2)

6. Bubble Sort:

   • Best Case: O(n) (already sorted)
   • Average Case: O(n^2)
   • Worst Case: O(n^2)

It's important to note that the "best case" time complexities for Insertion Sort and Bubble Sort are more favorable when the input data is nearly sorted. In contrast, Merge Sort, Heap Sort, and Quick Sort maintain their efficiency across various data distributions.

Therefore, the choice of sorting algorithm should take into consideration the specific characteristics of your data and the expected usage scenarios.

***
E2E API Sessions with Postman, RestAssured, Design Patterns, Architectures, GIT, Jenkins, Framework Design from Scratch: https://lnkd.in/g9r99y8k
***

🤝For SDET or Automation Testing trainings along with career guidance, mock interviews, design patterns, Generative AI : https://lnkd.in/giCxnJJ7

***

🚀 End-to-End Automation & SDET Training:

Boost your testing career with specialized Automation Testing & SDET workshops designed for product companies! Explore API, UI, Mobile, Jenkins, GIT, Docker, and the exciting world of Generative AI. Dive into a unique learning journey featuring personalized 1:1 guidance, interactive mock sessions, and collaborative pair programming, all guided by expert Sidharth Shukla . 🌟 Check out the demo now! Demo Session

Enrol Here → https://topmate.io/sidharth_shukla/110008

+++++++

#testing #automation #qa #testautomation #career #softwaretesting #qualityassurance #qaautomation #software #testingtips #assert #testng #sdet #technology #sidpost

 SDET Interview Question and Answers

TestNG Interview questions and answers

Jenkins Interview Questions and Answers

Appium Interview Questions and Answers

Selenium Interview Questions and answers

Java Coding Interview Questions and Answers

GIT Interview Questions and Answers