-3

Which sorting algorithm work efficient for these two arrays:

  • Insertion Sort

  • Selection Sort

  • Bubble Sort

     int arr1={16,22,11,62,45,37,62,45,3,17};

 int arr2={3,6,9,12,15,17,20,22,29,35};
Improve this question
3
  • 2
    This looks like an assignment to test your knowledge about material you have been taught. Take your time to try sorting each array, yourself, and you will be able to answer the question. Commented Oct 2, 2022 at 17:42
  • You need to sort the array separately or merge and sort ? Commented Oct 2, 2022 at 17:42
  • Which tool I use for dry run I try on paper but its very large and time taken so which tool or software I use for dry run it? Commented Oct 2, 2022 at 18:06

1 Answer 1

Reset to default
0

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.

Improve this answer
Sign up to request clarification or add additional context in comments.

12 Comments

Why it show 0 swaps for arr2?
Because arr2 is already sorted? Why would you expect any swaps?
And how I can easily check it through dry run? I have try on paper but it too long and time taken is any through which I can easily dry run it?
What do you mean with "dry run"? Didn't you run the snippet?
Mean check how execute statement one by one and how change array in every iteration
|

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.