Insertion Sort Algorithm in Descending Order
Below I have listed my code for insertion sort algorithm that sorts in ascending order. I cannot for the life of me figure out how to turn it into descending order. I'm sure it is simple, but I need help. Thanks in advance.
Code:
// -----------------------------------------------------------------
// Sorts the specified array of objects using the insertion
// sort algorithm.
// -----------------------------------------------------------------
public static void insertionSort(Comparable[] list) {
for (int index = 1; index < list.length; index++) {
Comparable key = list[index];
int position = index;
// Shift larger values to the left
while (position > 0 && key.compareTo(list[position - 1]) < 0) {
list[position] = list[position - 1];
position--;
}
list[position] = key;
}
}
Re: Insertion Sort Algorithm in Descending Order
Take a piece of paper and write down how the indexes work for this sort. Work out the logic for how this sort works.
Then think about how to work the sort in the opposite order.
Where would the indexes start and where would the elements be moved to.
Re: Insertion Sort Algorithm in Descending Order
This is part of an input program. It works as simply as typing in how many integers there will be, and then, typing in the integers. The code that I listed above successfully sorts them in ascending order. I have been working on switching things around for 4 hours this afternoon to no avail. That is why I resorted to posting. I have hit a wall.
Re: Insertion Sort Algorithm in Descending Order
Have you worked out how the posted code works?
Can you write the logic in pseudo code to describe the steps the code takes?
What is there about it that sorts in ascending order? Where does the index start as it moves through the array?
Where and why are the elements moved as the index changes.
When you get that down and understood, reverse the logic and order to do it the other way.
Re: Insertion Sort Algorithm in Descending Order
I am not sure if I understand full how this code works. I tried looking at it logically and reversing what I thought I understood, and it didn't work. This code was just given to me without explanation which is why I'm having such a difficult time understanding it. Can you point me in the right directions with a more direct answer please?
Re: Insertion Sort Algorithm in Descending Order
Quote:
I am not sure if I understand full how this code works.
That is the first then you should work on.
You can't rewrite code without understanding what it does.
Use a piece of paper and a pencil, create a list of words or numbers to sort and work out how the code does its thing.
Re: Insertion Sort Algorithm in Descending Order
I know what the code does that is not what I meant. I understand that it inserts each number input into its correct place in order. I just cannot figure out how to reverse this code to descend it. I have tried as best as I can, and that is why I came here for help. Not being rude, but I am not looking for more riddles or questions to accompany it.
Re: Insertion Sort Algorithm in Descending Order
I'm trying to suggest ways for you to figure out how the existing code works.
Can you list the steps in the sort algorithm? Have you used a piece of paper and a pencil to work out the logic?
If you can't do that then we'll have to work through the code to show you the what it does.
When you understand that, then you should be able to use the same kind of logic to work out how to change the sort order.
Re: Insertion Sort Algorithm in Descending Order
I do not know what you mean about using paper and pencil to work out the logic. I am not a java programmer, and I will never be around this material again in 2 more weeks. I am better at Java programming that a lot of my classmates, but my teachers reads powerpoints; that's it. I have not been taught a thing and have had to teach myself all semester. This is the first thing I do not understand of the semester. I just came here to ask for help. I'm not trying to come off as a jerk, but I am just tired of this class and mostly its teacher.
Re: Insertion Sort Algorithm in Descending Order
Quote:
I do not know what you mean about using paper and pencil to work out the logic.
You draw a list of objects to be sorted and set pointers to the elements as per what the code does.
You redraw the list as the code moves objects in the list. You redraw the pointer as the code changes the values of the index variables.
Re: Insertion Sort Algorithm in Descending Order
Never mind, I'll go somewhere else for help.
Re: Insertion Sort Algorithm in Descending Order
You need to show a little effort. We don't write code for students. They are expected to write their own code.
We will help anyone to get their code to work, but it will be the student doing the coding.
Re: Insertion Sort Algorithm in Descending Order
Just imagine a Comparable that, when you feed it two numbers to compare, it 'thinks' that it has to compare the negative of those numbers, i.e. you feed it a and b and the Comparable 'thinks' it needs to compare -a and -b.
kind regards,
Jos