Implementing a SelectionSort capable of handling array list, linked list, and doubly linked list in java

Question

BACKGROUND: I want to implement a selection sort capable of handling an array list, a linked list, and a doubly linked list. For each list type I have a position{} and list{} class. The position{} class is what holds the list, (i.e. class position{int head; list tail;}). While the LIST{} contains the next(), previous(), end(), Insert(), first() methods and uses position{}, it does not contain the list class itself, the list class itself that constructs the list is called class position{}.

QUESTION: My problem is not with making the selection sort compatible, I have achieved this by only using the commands that are common between he three list abstract data types. My problem is that my selection sort returns the same list and does no sort of sorting. The list printed after the sort is the same as the list printed before the sort. Any help is appreciated.

output before selection sort 2 879 621 229 702 40 243 312 247 46 711 241 after selection sort 2 879 621 229 702 40 243 312 247 46 711 241

My list ADT's are correct, the problem lies in my poor selectionsort.

public static void SelectionSort(LIST A) { 
        POSITION i, j, maxp, temp;
        for(i = A.Previous(A.End()); !i.isEqual(A.First()); i = A.Previous(i)) {
            maxp = i;
            for(j = A.First(); !j.isEqual(i); j = A.Next(j))  {
                if((Integer)A.Select(j) > (Integer)A.Select(maxp)) {
                    maxp = j;
                }     
            }   
            temp = i;
            A.Insert(i, A.Select(maxp));
            A.Insert(maxp, A.Select(temp));
            A.Delete(maxp);
            A.Delete(i);
        }
    }

Michał Kosmulski · Accepted Answer · 2014-04-15 19:05:02Z

1

You're first inserting something at index i, then inserting something at index maxp, then deleting the thing at index maxp and then deleting something at index i. Assuming Insert() and Delete() do what their names imply, this sequence of operations leaves your list in the initial state after each iteration of the loop since the deletions undo the insertions.

As a side note, this code doesn't follow Java's naming conventions which makes it harder to read than it needs to be.

answered Apr 15, 2014 at 19:05

Michał Kosmulski

10.1k1 gold badge34 silver badges53 bronze badges

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

2 Comments

Braithe Warnock Over a year ago

I insert and Delete because by inserting I am causing the list to grow, I don't want that, I want the list to remain the same size. So I must attach a delete to every insert. BTW using the replace() method gives the same result

Michał Kosmulski Over a year ago

@BraitheWarnock But if you insert something and then delete it, you end up just where you started. You have to remove at a different index than the one where you insert, or change the order of operations (since you insert into the list, the same index points to different entries at different times)

Trenin · Accepted Answer · 2014-04-15 19:05:10Z

0

How do the Insert, Select, and Delete methods function? Is it possible that Delete is removing the element you just Inserted?

Have you verified that the isEqual (and methods mentioned above) operator is behaving as expected?

From your algorithm, this is what I infer is happening:

you loop over all the elements, starting at the second last, moving towards the front.
- Locate the maximal element in the subset from 0 to i
- Insert the maximal element found (at index maxp) into the array at index i
- Insert the element originally at index i back into the array at the posistion originally taken by maxp
- Remove the i and maxp

First off, why do you need to remove the elements? Does Insert duplicate the element? If you call Delete on a list with two instances of the element you are trying to delete, which one will it delete? The first? Is this what you want?

Perhaps you need a new method, Replace which replaces the element at the given index instead. Then you wouldn't need to remove it after. Even better would be a Swap method which swaps 2 elements in a List.

An easier to follow solution might even create a new list to store the elements instead of performing the sort in place. While this takes more room, it would be easier to implement in the short term, and once it is working, you can optimize it with an in place sort later.

answered Apr 15, 2014 at 19:05

Trenin

2,0761 gold badge15 silver badges20 bronze badges

1 Comment

Braithe Warnock Over a year ago

This is what I know: Insert does insert a NEW node/position into the list, and this is the reason for my delete. Each time I insert into the list, I am increasing the # of elements in the list and so each insert must of a corresponding delete. Only the LIST ADT has a replace method, not the array list or doubly linked. What the algorithm does is see what POSITION holds the highest element, then it swaps the ELEMENTS in the position, so first the selection sort compares positions, and then it swaps the elements in the position BTW, I have tried using the replace, same results

Jon B · Accepted Answer · 2014-04-15 19:17:04Z

0

You should only need to do one insert and one delete. You are supposed to search the unsorted part of the list for the smallest (or biggest) element, then move it to the end of the sorted part of the list. That's one insert and one delete.

Also be careful that you are deleting the correct element. If you insert before you delete, then the correct index to delete may be shifted by one if the insert went before that position.

answered Apr 15, 2014 at 19:17

Jon B

4815 silver badges9 bronze badges

1 Comment

Braithe Warnock Over a year ago

I will try this, each time I insert max position I am inserting 879, which means that my search for highest is picking up the highest elements again when it should drop it off at the end of the list and then not search that end of the list for highest

Braithe Warnock · Accepted Answer · 2014-04-16 04:39:02Z

This is the correct answer, it took me a clear mind, probably caused by a good cup of tea, to finally sort things out in the end... My insert and delete methods were just not right, one little change and wallah. cheers. Thanks for all the replies.

public static void SelectionSort(LIST A) { 
    POSITION i, j, maxp, temp;
    for(i = A.Previous(A.End()); !i.isEqual(A.First()); i = A.Previous(i)) { 
        maxp = i;
        for(j = A.First(); !j.isEqual(i); j = A.Next(j))  {                  
            if((Integer)A.Select(j) > (Integer)A.Select(maxp)) {             
                maxp = j;
            }     
        }   
        temp = i;
        A.Insert(A.End(), A.Select(maxp));
        A.Delete(A.Previous(A.End()));
        A.Insert(maxp, A.Select(temp));
        A.Delete(temp);
    }
}

Collectives™ on Stack Overflow

Implementing a SelectionSort capable of handling array list, linked list, and doubly linked list in java

4 Answers 4

2 Comments

1 Comment

1 Comment

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

4 Answers 4

2 Comments

1 Comment

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Related