Python Pool: Understanding Strand Sort in Python With Example

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:

1. Take two lists: input[], output[]
2. Take another list sub[] and move the first element of input[] to it
3. Now, traverse through the list input[]
4. We will check every element of input[] and will compare whether or not 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[]
5. Now we will merge sub[] into the output[]
6. The above two steps will continue until and unless all the elements of input[] are in ouput[]

Source ode 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[0] < b[0]:
      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)

Explanation:

strand_sort() function:

• This function takes a list inp as parameter
• In the output list, it calls the strand() function by passing inp as 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

strand() function:

• 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 element of the inp list 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

merge() function:

• 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 list becomes empty
• Inside the loop the elements of both a and b is compared, and the smaller one is added to the output list
• After exiting the while loop, any remaining element in list a or b is added to the output list
• The output list is then returned

Output:

Strand Sort in Python

Time complexity:

• Best case: O(n)
• Average case: O(n2)
• Worst case: O(n²)

Advantages of using strand sort:

• It is more efficient than 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.

Must Read

• Insertion Sort in Python [Program, Algorithm, Example]
• Understanding Python Bubble Sort with examples
• Shell Sort Algorithm and Program in Python

Conclusion:

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(n²) 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.

Happy Pythoning!

The post Understanding Strand Sort in Python With Example appeared first on Python Pool.

from Planet Python
via read more