CODEWITHSUNDEEP
sortingdata-structuresbubble-sortinsertion-sortselection-sort
Shaheer Ahmed
Shaheer Ahmed

Reputation: 19

Which sorting algorithm is efficient?

Which sorting algorithm work efficient for these two arrays:

Upvotes: -3

Views: 110

Answers (1)

trincot
trincot

Reputation: 350766

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.

Upvotes: 0

Related Questions