Sorting for SDET and Developers

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(n2).

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(n2).

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.

?? I've developed an Interview Q&A Package specifically designed to help you succeed in Automation Testing and SDET interviews, complete with a tailored resume format. https://lnkd.in/gJrBGExe

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(n2) 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.

??YouTube channel: https://lnkd.in/gHJ5BDJZ

Here’s the array we’ll use for examples:

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(n2) — 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.

API Testing Interview Q&A with Examples: https://youtu.be/kk15BAHCoNM?si=vSzYX18FpwjjnhwT

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(n2) — 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(n2) — 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.

?? Struggling with coding rounds in automation and SDET? Join me for a pair programming session to enhance your skills: https://lnkd.in/gVcgW69e

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.

Project-Based API Automation with Jenkins & GIT Course: https://topmate.io/sidharth_shukla/411810

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(n2) 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:

Merge Sort:

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

Heap Sort:

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

Quick Sort:

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

Insertion Sort:

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

Selection Sort:

• Best Case: O(n2)
• Average Case: O(n2)
• Worst Case: O(n2)

Bubble Sort:

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

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.

End to End SDET/Automation Training Package with 1:1 Guidance by MAANG SDET

Trainer Details: https://www.dhirubhai.net/in/sidharth-shukla-77b53145/

Are you aspiring to excel in the SDET role or automation job positions within leading product companies?

Look no further!

We have designed comprehensive training sessions tailored specifically for you. Our program includes 1:1 career guidance, mock interviews, pair programming sessions, and much more — all bundled into one amazing package. I have also created a session on how to use ChatGPT for Test Automation with example code and prompt engineering

End to End SDET/Automation Course with 1:1 guidance by MAANG SDET :https://topmate.io/sidharth_shukla/110008

?? Schedule 1:1 call

Schedule 1:1 call for career guidance, interview preparation and mock interview, pair programming, SDET training and many more.

?? Services offered:

• ?? Career guidance
• - ?? Mock Interviews
• - ?? Job support in complex issue
• - ?? Resume and LinkedIn profile help
• - ?? Automation Framework Design Help
• - ?? SDET training sessions, Pair programming Sessions
• - ?? End to end Mentorship for SDETBOOK Session Here: https://topmate.io/sidharth_shukla

YouTube Channel

Subscribe to YouTube channel to learn and grow in Automation-SDET Career with real time project examples.

https://www.youtube.com/channel/UCwuAfFzAIAKU9qVYBVHiT3A

#AutomationTesting #SDET #BlogPost #Learning #AutomationSkills #testing #sidpost #testautomation #qaautomation #qa #automation #software #technology #career #softwaretesting #automation #testing #ui #sidpost #qa #qualityassurance #testautomation #qaautomation

************************************************

??AUTHOR: LinkedIn Profile

************************************************

#testing #automation #qualityassurance #testautomation #qa #qaautomation #interviewquestions #career #software #framework #selenium #technology #testers #linkedinconnection #sidpost