Content deleted Content added
Bolded the steps to make it more readable |
Added the implementation of the algorithm, along with the animation |
||
Line 1:
[[File:StrandSort.gif|thumb|220x220px|Strand Sort Animation]]
Strand sort is a very simple [[Recursion (computer science)|recursive]] [[sorting algorithm]] that sorts items of a list into increasing order. It works by moving the first element of a list into a sub-list. Then comparing each subsequent element in the sub-list to the original list and moving each element in the original list that is greater than the element in the sub-list to the sub-list. Then the sub-list is merged into a new list. Repeat this process and merge all sub-lists until all elements are sorted.<ref name=":0">{{Cite book|url=https://www.worldcat.org/oclc/641462443|title=IT enabled practices and emerging management paradigms|date=2008|publisher=Prestige Institute of Management and Research|others=Gupta, I. C. (Ishwar Chandra), 1946-, Jaroliya, Deepak., Prestige Institute of Management and Research.|isbn=9788174466761|edition=1st ed|___location=Indore|oclc=641462443}}</ref> This algorithm is called strand sort because there are strands of sorted elements within the unsorted elements that are removed one at a time.<ref name=":1">{{Cite web|url=https://xlinux.nist.gov/dads/HTML/strandSort.html|title=strand sort|website=xlinux.nist.gov|language=en-US|access-date=2018-11-06}}</ref> This algorithm is also comparison [[sorting algorithm]] because elements of the sub-list are compared to elements of the original list. This algorithm is also used in [[J Sort]] for fewer than 40 elements.<ref>{{Cite book|url=https://www.worldcat.org/oclc/311311576|title=Data structures using C : 1000 problems and solutions|last=Sudipta.|first=Mukherjee,|date=2008|publisher=Tata McGraw-Hill|isbn=9780070667655|___location=New Delhi|oclc=311311576}}</ref>
Line 5 ⟶ 6:
== Example ==
Based off of the description of the algorithm provided in the book, ''IT
'''Step 1:''' Start with a list of numbers: {13, 7, 19, 6, 25, 29, 1, 4 }
Line 60 ⟶ 61:
The solution list now contains: {1,4, 6, 7, 13, 19, 25, 19}. There are now more elements in the original list, and all of the elements in the solution list have successfully been sorted into increasing numerical order.
== Implementation ==
Since Strand Sort requires many insertions and deletions, it is best to use a linked list when implementing strand sort. <ref name=":1" /> Linked lists require constant time for both insertions and removals of elements using iterators. Linked lists can only access sequential elements, which is what strand sort does. The time to traverse through the linked list is directly related to the input size of the list.<ref>{{Cite web|url=https://www.cs.cmu.edu/~adamchik/15-121/lectures/Linked%20Lists/linked%20lists.html|title=LinkedLists|website=www.cs.cmu.edu|access-date=2018-11-06}}</ref> The following implementation is done in Java 8 and is based off of the description of the algorithm from the book, ''IT Enabled Practices and Emerging Management Paradigms''.<ref name=":0" /><syntaxhighlight lang="java" line="1">
package strandSort;
import java.util.*;
public class strandSort {
static LinkedList<Integer> solList = new LinkedList<Integer>();
static int k = 0;
/**
* This is a recursive Strand Sort method. It takes in a linked list of
* integers as parameters. It first check the base case to see if the linked
* list is empty. Then proceeds to the Strand sort algorithm until the
* linked list is empty.
*
* @param origList:
* a linked list of integers
*/
public static void strandSortIterative(LinkedList<Integer> origList) {
// Base Case
if (origList.isEmpty()) {
return;
}
else {
// Create the subList and add the first element of
// The original linked list to the sublist.
// Then remove the first element from the original list.
LinkedList<Integer> subList = new LinkedList<Integer>();
subList.add(origList.getFirst());
origList.removeFirst();
// Iterate through the original list, checking if any elements are
// Greater than the element in the sub list.
int index = 0;
for (int j = 0; j < origList.size(); j++) {
if (origList.get(j) > subList.get(index)) {
subList.add(origList.get(j));
origList.remove(j);
j = j - 1;
index = index + 1;
}
}
// Merge sub-list into solution list. There are three cases for this
// step
// Case 1: The first recursive call, add all of the elements to the
// solution
// list in sequential order
if (k == 0) {
for (int i = 0; i < subList.size(); i++) {
solList.add(subList.get(i));
k = k + 1;
}
}
// Case 2: After the first recursive call if there subList contains
// more than one element,
// the elements need to be added to
// The front of the solution list, adding the largest element first.
else if (subList.size() > 1) {
for (int w = subList.size() - 1; w >= 0; w--) {
solList.addFirst(subList.get(w));
// w = w+1;
}
} else {
// If there is only one element in the subList, then
// It just gets added to the front of the solution list.
for (int w = 0; w < subList.size(); w++) {
solList.addFirst(subList.get(w));
}
}
strandSortIterative(origList);
}
}
public static void main(String[] args) {
// Create a new linked list of Integers
LinkedList<Integer> origList = new LinkedList<Integer>();
// Add the following integers to the linked list: {13, 7, 19, 6, 25, 29,
// 1, 4}
origList.add(13);
origList.add(7);
origList.add(19);
origList.add(6);
origList.add(25);
origList.add(29);
origList.add(1);
origList.add(4);
strandSortIterative(origList);
// Print out the solution list
for (int i = 0; i < solList.size(); i++) {
System.out.println(solList.get(i));
}
}
}
</syntaxhighlight>
{{AFC submission|t||ts=20181106150605|u=Heldw|ns=118|demo=}}<!-- Important, do not remove this line before article has been created. -->
| |||