Let's sort the Linked List
Step 1: 6 4 → 2 5 → 1 2 → 2 2 → 1 1 Step 2: 1 1 → 6 4 → 2 5 → 1 2 → 2 2 Step 3: 1 1 → 1 2 → 6 4 → 2 5 → 2 2 Step 4: 1 1 → 1 2 → 2 2 → 6 4 → 2 5 Step 5: 1 1 → 1 2 → 2 2 → 2 5 → 6 4
Which sorting technique is being used above to sort the linked list ?
Note: The sorting algorithm being used in this case is most likely to be implemented in something like a linked list , where it is simple to add and remove elements.
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
1 solution
Why on Earth would selection sort shift the remaining indicies?
Log in to reply
I absolutely second this. It would increase the number of swaps drastically. A more realistic selection sort would swap elements. Example below:
[64 , 25 , 12 , 22 , 11] [11 , 25 , 12 , 22 , 64] [11 , 12 , 25 , 22 , 64] [11 , 12 , 22 , 25 , 64]
It's a less complicated algorithm, has fewer steps, and fewer swaps.
Edit: line breaks are being difficult
It depends on how Selection Sort is being implemented. While the traditional notion of Selection Sort would do an in-place swap (e.g., what @Matt Tough has displayed), a more common implementation in lists where add/remove is simple (e.g., in a linked list ) is to simply remove the minimum un-sorted element and then insert it at the end of the sorted values.
For example, in step 2, the sorted sublist is {11}. Between steps 2 and 3, the algorithm checks out the unsorted sublist, finds 12 as the smallest element, removes it, and adds it to the end of the sorted sublist.
The key in Selection Sort is that the algorithm is looking through the unsorted data.
Log in to reply
...but it says it's an array.
Log in to reply
@Justin Barnard – Yeah - I updated the question to make it more clear. Thanks for pointing this out!
Isn't Selection Sort supposed to swap 64 with 11, then 25 with 12, and so on? This part of moving the whole array looks more like Insertion Sort
It can't be Bubble Sort , since Bubble Sort works through the list (multiple times if needed) swapping adjacent elements, yet between Step 1 and Step 2, all five elements moved.
It can't be Insertion Sort . Similar to Bubble Sort, this sort makes a sorted sublist to the left and right of some element (often the first element in the list). There is no sorted-sublist to the right of any element here.
It's pretty obviously not Merge Sort , since it doesn't look as if a divide-and-conquer approach is being used. Also, the move of the 11 to the front of the list between Step 1 and 2 wouldn't happen in Merge Sort.
That leaves Selection Sort as the only possibility. It looks for the smallest element in the right, unsorted part of the list and moves it into the sorted part. For example, it brings 11 to the front of the list between Step 1 and Step 2, then brings 12 into the sorted list (of 3 elements) between Step 2 and 3, and so on.