sortingdata-structuresbubble-sortinsertion-sortselection-sort

Which sorting algorithm is efficient?


Which sorting algorithm work efficient for these two arrays:


Solution

  • Here is a little JavaScript snippet that has implementations for the three sorting methods, and which reports on the number of comparisons and number of swaps they perform.

    This is done for the two arrays you have provided. You can run it here:

    function swap(arr, i, j, stats) {
        if (i === j) return;
        stats.swaps++;
        [arr[i], arr[j]] = [arr[j], arr[i]]
    }
    
    function isGreater(arr, i, j, stats) {
        stats.comparisons++;
        return arr[i] > arr[j];
    }
    
    function bubbleSort(arr) {
        let stats = { comparisons: 0, swaps: 0 };
        for (let i = 1; i < arr.length; i++) {
            let prevSwaps = stats.swaps;
            for (let j = 0; j < arr.length - i; j++) {
                if (isGreater(arr, j, j + 1, stats)) {
                    swap(arr, j, j + 1, stats);
                }
            }
            if (prevSwaps === stats.swaps) break;
        }
        return stats;
    }
    
    function insertionSort(arr) {
        let stats = { comparisons: 0, swaps: 0 };
        for (let i = 1; i < arr.length; i++) {
            for (let j = i - 1; j >= 0; j--) {
                if (!isGreater(arr, j, j + 1, stats)) break;
                swap(arr, j, j + 1, stats);
            }
        }
        return stats;
    }
    
    function selectionSort(arr) {
        let stats = { comparisons: 0, swaps: 0 };
        for (let i = 0; i < arr.length; i++) {
            let j = i;
            for (let k = i + 1; k < arr.length; k++) {
                if (isGreater(arr, j, k, stats)) j = k;
            }
            swap(arr, i, j, stats);
        }
        return stats;
    }
    
    function displaySortingStats(arr) {
        console.log("sorting ", ...arr, ":");
        const stats = {
           insertionSort: insertionSort([...arr]),
           selectionSort: selectionSort([...arr]),
           bubbleSort: bubbleSort([...arr]),
        }
        console.log(stats);
    }
    
    displaySortingStats([16,22,11,62,45,37,62,45,3,17]);
    displaySortingStats([3,6,9,12,15,17,20,22,29,35]);

    These are the results:

    Input Sorting algorithm #Comparisons #Swaps
    arr1 insertion sort 28 21
    selection sort 45 7
    bubble sort 45 21
    arr2 insertion sort 9 0
    selection sort 45 0
    bubble sort 9 0

    Depending on what you count, either insertion sort or selection sort is best for arr1, and for arr2 both insertion sort and bubble sort perform equally well.