Number of comparisons in an insertion sort

  • Thread starter nicnicman
  • Start date
  • Tags
    Sort
In summary, the insertion sort uses n-1 comparisons to sort a list in ascending order, regardless of the order of the original list. The ellipsis (...) represents a descending order in the given list.
  • #1
nicnicman
136
0

Homework Statement


How many comparisons does the insertion sort use to sort the list n, n-1, ...2, 1?


Homework Equations





The Attempt at a Solution


Insertion sort compares every element with every other element in the list, but I'm unsure what this question is asking. Why does it jump from n, n-1 to 2, 1?

Thanks for any suggestions.
 
Physics news on Phys.org
  • #2
nicnicman said:

Homework Statement


How many comparisons does the insertion sort use to sort the list n, n-1, ...2, 1?


Homework Equations





The Attempt at a Solution


Insertion sort compares every element with every other element in the list, but I'm unsure what this question is asking. Why does it jump from n, n-1 to 2, 1?

Thanks for any suggestions.

What jump? Do you not understand what the ellipsis stands for ?
 
  • #3
Yes, but usually there is an order like 1, 2, . . . , n. I guess I just don't see the order here.
 
  • #4
SO you feel that 1, 2, ... n is ordered but the reverse is not?
 
  • #5
n, n-1, ...2, 1 means the list in reversed order. After the sort routine is finished, the order will be 1, 2, 3, ..., n - 1, n
 
  • #6
Oh, okay. I see now. Thanks.
 
  • #7
So would the answer be n - 1?
 
  • #8
Never mind it would be n - 1 passes, not comparisons.
 
  • #9
Actually, after thinking about a bit more, wouldn't the insertion sort also make n - 1 comparisons since the list is already in descending order.

Sorry for all the posts.
 
  • #10
nicnicman said:
Actually, after thinking about a bit more, wouldn't the insertion sort also make n - 1 comparisons since the list is already in descending order.
But you want the list to be in ascending order, right?
 
  • #11
Right. So, if you had a list 3, 2, 1 the comparisons would go like this:

Comparison 1. compare 2 and 3, we have 2, 3, 1
Comparison 2. compare 1 and 2 , we have 1, 2, 3

Done, with 2 comparisons, or n - 1.

Please, correct me if I'm wrong.
 
Last edited:
  • #12
I'm still not entirely sure of my answer and I was hoping someone would offer some advice.

Thanks for any suggestions.
 
  • #13
nicnicman said:
Right. So, if you had a list 3, 2, 1 the comparisons would go like this:

Comparison 1. compare 2 and 3, we have 2, 3, 1
Comparison 2. compare 1 and 2 , we have 1, 2, 3

Done, with 2 comparisons, or n - 1.

Please, correct me if I'm wrong.

Your list is too short to really give you any insight. How about if the list is 5, 4, 3, 2, 1?
 
  • #14
That was the exact list I tried it with first. I only used a smaller list here for simplification. Anyway, with the longer list I got the same results: n-1.
 

1. What is an insertion sort?

An insertion sort is a sorting algorithm that works by dividing the input array into two subarrays - a sorted subarray and an unsorted subarray. Initially, the sorted subarray contains the first element of the input array, and the unsorted subarray contains the remaining elements. The algorithm then iterates through the unsorted subarray, taking one element at a time and inserting it into the correct position in the sorted subarray.

2. How does an insertion sort work?

An insertion sort works by iterating through the unsorted subarray, starting from the second element. Each element is then compared to the previous elements in the sorted subarray, and if it is smaller, it is inserted into the correct position in the sorted subarray. This process continues until all elements in the unsorted subarray have been inserted into the sorted subarray, resulting in a fully sorted array.

3. What is the time complexity of an insertion sort?

The time complexity of an insertion sort is O(n^2), where n is the number of elements in the input array. This means that the time it takes to sort an array using insertion sort increases quadratically as the number of elements in the input array increases.

4. How many comparisons are made in an insertion sort?

The number of comparisons made in an insertion sort depends on the input array. In the best case, when the input array is already sorted, the algorithm makes n-1 comparisons, where n is the number of elements in the array. In the worst case, when the input array is in reverse sorted order, the algorithm makes n*(n-1)/2 comparisons. On average, an insertion sort makes n*(n-1)/4 comparisons.

5. Can the number of comparisons in an insertion sort be reduced?

The number of comparisons in an insertion sort can be reduced by implementing a variation of the algorithm called binary insertion sort. This algorithm uses a binary search to find the correct position for each element in the sorted subarray, reducing the number of comparisons to log(n) for each element. This results in a total of n*log(n) comparisons, improving the time complexity to O(n*log(n)).

Similar threads

  • Engineering and Comp Sci Homework Help
Replies
1
Views
810
  • Engineering and Comp Sci Homework Help
Replies
7
Views
5K
  • Engineering and Comp Sci Homework Help
Replies
2
Views
2K
  • Engineering and Comp Sci Homework Help
Replies
5
Views
2K
  • Engineering and Comp Sci Homework Help
Replies
1
Views
3K
  • Engineering and Comp Sci Homework Help
Replies
22
Views
2K
  • Engineering and Comp Sci Homework Help
Replies
12
Views
4K
  • Engineering and Comp Sci Homework Help
Replies
12
Views
3K
  • Engineering and Comp Sci Homework Help
Replies
2
Views
2K
  • Engineering and Comp Sci Homework Help
Replies
8
Views
1K
Back
Top