Sorting means arranging items in a specified manner. Strand sort is a sorting algorithm that is recursive in nature. It is mainly used to sort a list in increasing order. In this article, we will learn how to implement strand sort in python.
Strand Sort Algorithm in Python:
- Take two lists: input, output
- Take another list sub and move the first element of input to it
- Now, traverse through the list input
- We will check every element of input and compare whether it is greater than the last inserted element in sub. If it is true, then we will add that element to sub; otherwise, keep it in input
- Now we will merge sub into the output
- The above two steps will continue until and unless all the elements of input are in ouput
Source Code for Strand Sort:
def strand_sort(inp): output = strand(inp) while len(inp): output = merge(output, strand(inp)) return output def strand(inp): element, sub = 0, [inp.pop(0)] while element < len(inp): if inp[element] > sub[-1]: sub.append(inp.pop(element)) else: element += 1 return sub def merge(a, b): output =  while len(a) and len(b): if a < b: output.append(a.pop(0)) else: output.append(b.pop(0)) output += a output += b return output inputs = [9,2,0,4,1,8,2,3,7] print("Input List:") print(inputs) output = strand_sort(inputs) print("Output List:") print(output)
- This function takes a list inp as a parameter
- In the output list, it calls the strand() function by passing inp as a parameter
- Then a while loop is implemented, which is used to merge the stranded list to the output list
- The while loop is continued till the input list is empty
- Finally, the output list is returned as the final result
- This function also takes a list inp as the parameter.
- Two variables, one integer called element is initialized to 0. Another list variable sub is initialized with the first element of the input list
- A while loop is used to iterate through the inp list.
- At each iteration, the inp list element is compared with the last added element of the sub list
- if the element of the inp list is greater, it is transferred to the sub list. Otherwise, it is ignored
- Lastly, the sub list is returned
- This function takes to list a and b (that needs to be merged) as parameters
- A while loop is used, which iterates till either of the lists becomes empty
- Inside the loop, the elements of both a and b are compared, and the smaller one is added to the output list
- After exiting the while loop, any remaining element in the list a or b is added to the output list
- The output list is then returned
- Best case: O(n)
- Average case: O(n2)
- Worst case: O(n2)
Advantages of using strand sort:
- It is more efficient than the selection sort algorithm
- The cache miss ratio for strand sort is less than that of shell sort
Disadvantages of using strand sort:
- It is not as efficient in performance as quick sort or merge sort
- It has a complex algorithm
Strand Sort In-depth Tutorial Video
Video Tutorial link Click Here.
- Insertion Sort in Python [Program, Algorithm, Example]
- Understanding Python Bubble Sort with examples
- Shell Sort Algorithm and Program in Python
This is how one can easily do a strand sort on a list in python. The worst-case time complexity of strand sort is O(n2), and the best case time complexity is O(n). Implementation of strand sort must be done as per the needs and constraints and obviously as per a person’s personal preference.
However, if you have any doubts or questions, do let me know in the comment section below. I will try to help you as soon as possible.