Posted on by Kalkicode
Code Sorting

# Strand Sort

Strand Sort is a sorting algorithm that was developed by Craig McQueen in 2005. It is a comparison-based sorting algorithm that works by repeatedly scanning the input list, removing sorted elements from it, and appending them to a new list in sorted order until no unsorted elements remain.

The basic idea behind Strand Sort is to find "strands" of increasing elements in the input list and merge them into the output list. A strand is defined as a subsequence of the input list where each element is greater than or equal to the previous element. The algorithm repeatedly scans the input list, selecting the longest strand of increasing elements it can find and appending it to the output list. The selected strand is then removed from the input list, and the process is repeated until no unsorted elements remain.

One of the key advantages of Strand Sort is that it has a worst-case time complexity of O(n log n), which is the same as many other popular sorting algorithms like Merge Sort and Quicksort. However, it has a number of additional optimizations that can make it more efficient than these algorithms in certain cases.

One of the main drawbacks of Strand Sort is that it requires a lot of memory to perform the sort, since it needs to maintain both the input and output lists in memory at the same time. This can make it less practical for sorting very large datasets that do not fit in memory.

Here given code implementation process.

``````// C program
// Strand Sort
#include <stdio.h>

#include <stdlib.h>

struct Node
{
int element;
struct Node *next;
};
//Create a node
struct Node *create_node(int data)
{
struct Node *node = (struct Node *) malloc(sizeof(struct Node *));
if (node != NULL)
{
node->element = data;
node->next = NULL;
}
return node;
}
//Merge two sorted list and return its result
struct Node *merge_list(struct Node *list1, struct Node *list2)
{
if (list1 == NULL)
{
//When list1 is empty
return list2;
}
else if (list2 == NULL)
{
return list1;
}
else
{
//Some auxiliary variables
struct Node *tail = NULL;
struct Node *node = NULL;
// Combine list elements in sorted order
// This process takes(m+n) time
// Here m is size of list1
// And n is size of list2
while (list1 != NULL || list2 != NULL)
{
if (list1 != NULL && list2 != NULL)
{
if (list1->element < list2->element)
{
node = list1;
list1 = list1->next;
}
else
{
node = list2;
list2 = list2->next;
}
}
else if (list1 != NULL)
{
node = list1;
list1 = list1->next;
}
else
{
node = list2;
list2 = list2->next;
}
{
//When get first node of resultant list
}
else
{
//Add node at end of resultant list
tail->next = node;
}
node->next = NULL;
tail = node;
}
}
}
//Perform the standard sort of given list elements
struct Node *stander_sort(struct Node *input_list, struct Node *output_list)
{
if (input_list == NULL)
{
return output_list;
}
//create new list and set first element of input list
struct Node *sub_list = input_list;
struct Node *tail = sub_list;
struct Node *back = NULL;
//visit to next element
//like remove first node initial input list
input_list = sub_list->next;
struct Node *auxiliary_list = input_list;
int item = sub_list->element;
while (auxiliary_list != NULL)
{
if (auxiliary_list->element > item)
{
//Add node at end of sublist
tail->next = auxiliary_list;
item = auxiliary_list->element;
if (back == NULL)
{
//remove front node in actual list
input_list = auxiliary_list->next;
auxiliary_list = auxiliary_list->next;
}
else
{
auxiliary_list = auxiliary_list->next;
//remove intermediate element
back->next = auxiliary_list;
}
tail = tail->next;
}
else
{
back = auxiliary_list;
auxiliary_list = auxiliary_list->next;
}
}
// Separate the new sublist
tail->next = NULL;
output_list = merge_list(output_list, sub_list);
return stander_sort(input_list, output_list);
}
//This are providing the environment setup to perform standard sort
void sort_element(int collection[], int size)
{
if (size <= 1)
{
return;
}
//Loop controlling variable
int i = 0;
//Create editable list
struct Node *input_list = NULL;
struct Node *output_list = NULL;
//Some auxiliary variables
struct Node *tail = NULL;
struct Node *node = NULL;
//Find add array element into custom list
for (i = 0; i < size; ++i)
{
node = create_node(collection[i]);
if (input_list == NULL)
{
input_list = node;
}
else
{
tail->next = node;
}
tail = node;
}
output_list = stander_sort(input_list, output_list);
input_list = NULL;
i = 0;
// Insert element into actual collection
while (output_list != NULL)
{
//Get current node
node = output_list;
//set element into collection
collection[i] = node->element;
//visit to next node
output_list = node->next;
//free node
free(node);
node = NULL;
i++;
}
}
//Display element of given collection
void display_element(int collection[], int size)
{
for (int i = 0; i < size; ++i)
{
printf("  %d", collection[i]);
}
printf("\n");
}
int main()
{
// Define the unsorted array elements
int collection[] = {
7 , 3 , 0 , 8 , 23 , 2 , 9 , 35 , 13 , 12 , 1 , 3
};
//Get the size of given collection
int size = sizeof(collection) / sizeof(collection[0]);
printf("\n Before sort : ");
display_element(collection, size);
sort_element(collection, size);
printf("\n After sort  : ");
display_element(collection, size);
return 0;
}``````

#### Output

`````` Before sort :   7  3  0  8  23  2  9  35  13  12  1  3

After sort  :   0  1  2  3  3  7  8  9  12  13  23  35``````
``````/*
Java Program
Strand Sort
*/
//Node of list element
class Node
{
public int element;
public Node next;
public Node(int data)
{
this.element = data;
this.next = null;
}
}
class StrandSort
{
//Merge two sorted list and return its result
public Node merge_list(Node list1, Node list2)
{
if (list1 == null)
{
//When list1 is empty
return list2;
}
else if (list2 == null)
{
return list1;
}
else
{
//Some auxiliary variables
Node tail = null;
Node node = null;
// Combine list elements in sorted order
// This process takes(m+n) time
// Here m is size of list1
// And n is size of list2
while (list1 != null || list2 != null)
{
if (list1 != null && list2 != null)
{
if (list1.element < list2.element)
{
node = list1;
list1 = list1.next;
}
else
{
node = list2;
list2 = list2.next;
}
}
else if (list1 != null)
{
node = list1;
list1 = list1.next;
}
else
{
node = list2;
list2 = list2.next;
}
{
//When get first node of resultant list
}
else
{
//Add node at end of resultant list
tail.next = node;
}
node.next = null;
tail = node;
}
}
}
//Perform the standard sort of given list elements
public Node stander_sort(Node input_list, Node output_list)
{
if (input_list == null)
{
return output_list;
}
//create new list and set first element of input list
Node sub_list = input_list;
Node tail = sub_list;
Node back = null;
//visit to next element
//like remove first node initial input list
input_list = sub_list.next;
Node auxiliary_list = input_list;
int item = sub_list.element;
while (auxiliary_list != null)
{
if (auxiliary_list.element > item)
{
//Add node at end of sublist
tail.next = auxiliary_list;
item = auxiliary_list.element;
if (back == null)
{
//remove front node in actual list
input_list = auxiliary_list.next;
auxiliary_list = auxiliary_list.next;
}
else
{
auxiliary_list = auxiliary_list.next;
//remove intermediate element
back.next = auxiliary_list;
}
tail = tail.next;
}
else
{
back = auxiliary_list;
auxiliary_list = auxiliary_list.next;
}
}
// Separate the new sublist
tail.next = null;
output_list = merge_list(output_list, sub_list);
return stander_sort(input_list, output_list);
}
//This are providing the environment setup to perform standard sort
public void sort_element(int[] collection, int size)
{
if (size <= 1)
{
return;
}
//Loop controlling variable
int i = 0;
//Create editable list
Node input_list = null;
Node output_list = null;
//Some auxiliary variables
Node tail = null;
Node node = null;
//Find add array element into custom list
for (i = 0; i < size; ++i)
{
node = new Node(collection[i]);
if (input_list == null)
{
input_list = node;
}
else
{
tail.next = node;
}
tail = node;
}
output_list = stander_sort(input_list, output_list);
input_list = null;
i = 0;
// Insert element into actual collection
while (output_list != null)
{
//Get current node
node = output_list;
//set element into collection
collection[i] = node.element;
//visit to next node
output_list = node.next;
node = null;
i++;
}
}
//Display element of given collection
public void display_element(int[] collection, int size)
{
for (int i = 0; i < size; ++i)
{
System.out.print("  " + collection[i]);
}
System.out.print("\n");
}
public static void main(String[] args)
{
StrandSort obj = new StrandSort();
// Define the unsorted array elements
int[] collection = {
7,
3,
0,
8,
23,
2,
9,
35,
13,
12,
1,
3
};
//Get the size of given collection
int size = collection.length;
System.out.print("\n Before sort : ");
obj.display_element(collection, size);
//sort collection element
obj.sort_element(collection, size);
System.out.print("\n After sort  : ");
obj.display_element(collection, size);
}
}``````

#### Output

`````` Before sort :   7  3  0  8  23  2  9  35  13  12  1  3

After sort  :   0  1  2  3  3  7  8  9  12  13  23  35``````
``````//Include header file
#include <iostream>

using namespace std;
/*
C++ Program
Strand Sort
*/
//Node of list element
class Node
{
public:
int element;
Node *next;
Node(int data)
{
this->element = data;
this->next = NULL;
}
};
class StrandSort
{
public:
//Merge two sorted list and return its result
Node *merge_list(Node *list1, Node *list2)
{
if (list1 == NULL)
{
//When list1 is empty
return list2;
}
else if (list2 == NULL)
{
return list1;
}
else
{
//Some auxiliary variables
Node *tail = NULL;
Node *node = NULL;
// Combine list elements in sorted order
// This process takes(m+n) time
// Here m is size of list1
// And n is size of list2
while (list1 != NULL || list2 != NULL)
{
if (list1 != NULL && list2 != NULL)
{
if (list1->element < list2->element)
{
node = list1;
list1 = list1->next;
}
else
{
node = list2;
list2 = list2->next;
}
}
else if (list1 != NULL)
{
node = list1;
list1 = list1->next;
}
else
{
node = list2;
list2 = list2->next;
}
{
//When get first node of resultant list
}
else
{
//Add node at end of resultant list
tail->next = node;
}
node->next = NULL;
tail = node;
}
}
}
//Perform the standard sort of given list elements
Node *stander_sort(Node *input_list, Node *output_list)
{
if (input_list == NULL)
{
return output_list;
}
//create new list and set first element of input list
Node *sub_list = input_list;
Node *tail = sub_list;
Node *back = NULL;
//visit to next element
//like remove first node initial input list
input_list = sub_list->next;
Node *auxiliary_list = input_list;
int item = sub_list->element;
while (auxiliary_list != NULL)
{
if (auxiliary_list->element > item)
{
//Add node at end of sublist
tail->next = auxiliary_list;
item = auxiliary_list->element;
if (back == NULL)
{
//remove front node in actual list
input_list = auxiliary_list->next;
auxiliary_list = auxiliary_list->next;
}
else
{
auxiliary_list = auxiliary_list->next;
//remove intermediate element
back->next = auxiliary_list;
}
tail = tail->next;
}
else
{
back = auxiliary_list;
auxiliary_list = auxiliary_list->next;
}
}
// Separate the new sublist
tail->next = NULL;
output_list = this->merge_list(output_list, sub_list);
return this->stander_sort(input_list, output_list);
}
//This are providing the environment setup to perform standard sort
void sort_element(int collection[], int size)
{
if (size <= 1)
{
return;
}
//Loop controlling variable
int i = 0;
//Create editable list
Node *input_list = NULL;
Node *output_list = NULL;
//Some auxiliary variables
Node *tail = NULL;
Node *node = NULL;
//Find add array element into custom list
for (i = 0; i < size; ++i)
{
node = new Node(collection[i]);
if (input_list == NULL)
{
input_list = node;
}
else
{
tail->next = node;
}
tail = node;
}
output_list = this->stander_sort(input_list, output_list);
input_list = NULL;
i = 0;
// Insert element into actual collection
while (output_list != NULL)
{
//Get current node
node = output_list;
//set element into collection
collection[i] = node->element;
//visit to next node
output_list = node->next;
node = NULL;
i++;
}
}
//Display element of given collection
void display_element(int collection[], int size)
{
for (int i = 0; i < size; ++i)
{
cout << "  " << collection[i];
}
cout << "\n";
}
};
int main()
{
StrandSort obj = StrandSort();
// Define the unsorted array elements
int collection[] = {
7 , 3 , 0 , 8 , 23 , 2 , 9 , 35 , 13 , 12 , 1 , 3
};
//Get the size of given collection
int size = sizeof(collection) / sizeof(collection[0]);
cout << "\n Before sort : ";
obj.display_element(collection, size);
//sort collection element
obj.sort_element(collection, size);
cout << "\n After sort  : ";
obj.display_element(collection, size);
return 0;
}``````

#### Output

`````` Before sort :   7  3  0  8  23  2  9  35  13  12  1  3

After sort  :   0  1  2  3  3  7  8  9  12  13  23  35``````
``````//Include namespace system
using System;

/*
C# Program
Strand Sort
*/

//Node of list element
class Node
{
public int element;
public Node next;
public Node(int data)
{
this.element = data;
this.next = null;
}
}
class StrandSort
{
//Merge two sorted list and return its result
public Node merge_list(Node list1, Node list2)
{
if (list1 == null)
{
//When list1 is empty
return list2;
}
else if (list2 == null)
{
return list1;
}
else
{
//Some auxiliary variables
Node tail = null;
Node node = null;
// Combine list elements in sorted order
// This process takes(m+n) time
// Here m is size of list1
// And n is size of list2
while (list1 != null || list2 != null)
{
if (list1 != null && list2 != null)
{
if (list1.element < list2.element)
{
node = list1;
list1 = list1.next;
}
else
{
node = list2;
list2 = list2.next;
}
}
else if (list1 != null)
{
node = list1;
list1 = list1.next;
}
else
{
node = list2;
list2 = list2.next;
}
{
//When get first node of resultant list
}
else
{
//Add node at end of resultant list
tail.next = node;
}
node.next = null;
tail = node;
}
}
}
//Perform the standard sort of given list elements
public Node stander_sort(Node input_list, Node output_list)
{
if (input_list == null)
{
return output_list;
}
//create new list and set first element of input list
Node sub_list = input_list;
Node tail = sub_list;
Node back = null;
//visit to next element
//like remove first node initial input list
input_list = sub_list.next;
Node auxiliary_list = input_list;
int item = sub_list.element;
while (auxiliary_list != null)
{
if (auxiliary_list.element > item)
{
//Add node at end of sublist
tail.next = auxiliary_list;
item = auxiliary_list.element;
if (back == null)
{
//remove front node in actual list
input_list = auxiliary_list.next;
auxiliary_list = auxiliary_list.next;
}
else
{
auxiliary_list = auxiliary_list.next;
//remove intermediate element
back.next = auxiliary_list;
}
tail = tail.next;
}
else
{
back = auxiliary_list;
auxiliary_list = auxiliary_list.next;
}
}
// Separate the new sublist
tail.next = null;
output_list = merge_list(output_list, sub_list);
return stander_sort(input_list, output_list);
}
//This are providing the environment setup to perform standard sort
public void sort_element(int[] collection, int size)
{
if (size <= 1)
{
return;
}
//Loop controlling variable
int i = 0;
//Create editable list
Node input_list = null;
Node output_list = null;
//Some auxiliary variables
Node tail = null;
Node node = null;
//Find add array element into custom list
for (i = 0; i < size; ++i)
{
node = new Node(collection[i]);
if (input_list == null)
{
input_list = node;
}
else
{
tail.next = node;
}
tail = node;
}
output_list = stander_sort(input_list, output_list);
input_list = null;
i = 0;
// Insert element into actual collection
while (output_list != null)
{
//Get current node
node = output_list;
//set element into collection
collection[i] = node.element;
//visit to next node
output_list = node.next;
node = null;
i++;
}
}
//Display element of given collection
public void display_element(int[] collection, int size)
{
for (int i = 0; i < size; ++i)
{
Console.Write("  " + collection[i]);
}
Console.Write("\n");
}
public static void Main(String[] args)
{
StrandSort obj = new StrandSort();
// Define the unsorted array elements
int[] collection = {
7 , 3 , 0 , 8 , 23 , 2 , 9 , 35 , 13 , 12 , 1 , 3
};
//Get the size of given collection
int size = collection.Length;
Console.Write("\n Before sort : ");
obj.display_element(collection, size);
//sort collection element
obj.sort_element(collection, size);
Console.Write("\n After sort  : ");
obj.display_element(collection, size);
}
}``````

#### Output

`````` Before sort :   7  3  0  8  23  2  9  35  13  12  1  3

After sort  :   0  1  2  3  3  7  8  9  12  13  23  35``````
``````<?php
/*
Php Program
Strand Sort
*/
//Node of list element
class Node
{
public \$element;
public \$next;

function __construct(\$data)
{
\$this->element = \$data;
\$this->next = null;
}
}
class StrandSort
{
//Merge two sorted list and return its result
public	function merge_list(\$list1, \$list2)
{
if (\$list1 == null)
{
//When list1 is empty
return \$list2;
}
else if (\$list2 == null)
{
return \$list1;
}
else
{
//Some auxiliary variables
\$tail = null;
\$node = null;
// Combine list elements in sorted order
// This process takes(m+n) time
// Here m is size of list1
// And n is size of list2
while (\$list1 != null || \$list2 != null)
{
if (\$list1 != null && \$list2 != null)
{
if (\$list1->element < \$list2->element)
{
\$node = \$list1;
\$list1 = \$list1->next;
}
else
{
\$node = \$list2;
\$list2 = \$list2->next;
}
}
else if (\$list1 != null)
{
\$node = \$list1;
\$list1 = \$list1->next;
}
else
{
\$node = \$list2;
\$list2 = \$list2->next;
}
{
//When get first node of resultant list
}
else
{
//Add node at end of resultant list
\$tail->next = \$node;
}
\$node->next = null;
\$tail = \$node;
}
}
}
//Perform the standard sort of given list elements
public	function stander_sort(\$input_list, \$output_list)
{
if (\$input_list == null)
{
return \$output_list;
}
//create new list and set first element of input list
\$sub_list = \$input_list;
\$tail = \$sub_list;
\$back = null;
//visit to next element
//like remove first node initial input list
\$input_list = \$sub_list->next;
\$auxiliary_list = \$input_list;
\$item = \$sub_list->element;
while (\$auxiliary_list != null)
{
if (\$auxiliary_list->element > \$item)
{
//Add node at end of sublist
\$tail->next = \$auxiliary_list;
\$item = \$auxiliary_list->element;
if (\$back == null)
{
//remove front node in actual list
\$input_list = \$auxiliary_list->next;
\$auxiliary_list = \$auxiliary_list->next;
}
else
{
\$auxiliary_list = \$auxiliary_list->next;
//remove intermediate element
\$back->next = \$auxiliary_list;
}
\$tail = \$tail->next;
}
else
{
\$back = \$auxiliary_list;
\$auxiliary_list = \$auxiliary_list->next;
}
}
// Separate the new sublist
\$tail->next = null;
\$output_list = \$this->merge_list(\$output_list, \$sub_list);
return \$this->stander_sort(\$input_list, \$output_list);
}
//This are providing the environment setup to perform standard sort
public	function sort_element( & \$collection, \$size)
{
if (\$size <= 1)
{
return;
}
//Loop controlling variable
\$i = 0;
//Create editable list
\$input_list = null;
\$output_list = null;
//Some auxiliary variables
\$tail = null;
\$node = null;
//Find add array element into custom list
for (\$i = 0; \$i < \$size; ++\$i)
{
\$node = new Node(\$collection[\$i]);
if (\$input_list == null)
{
\$input_list = \$node;
}
else
{
\$tail->next = \$node;
}
\$tail = \$node;
}
\$output_list = \$this->stander_sort(\$input_list, \$output_list);
\$input_list = null;
\$i = 0;
// Insert element into actual collection
while (\$output_list != null)
{
//Get current node
\$node = \$output_list;
//set element into collection
\$collection[\$i] = \$node->element;
//visit to next node
\$output_list = \$node->next;
\$node = null;
\$i++;
}
}
//Display element of given collection
public	function display_element( & \$collection, \$size)
{
for (\$i = 0; \$i < \$size; ++\$i)
{
echo "  ". \$collection[\$i];
}
echo "\n";
}
}

function main()
{
\$obj = new StrandSort();
// Define the unsorted array elements
\$collection = array(7, 3, 0, 8, 23, 2, 9, 35, 13, 12, 1, 3);
//Get the size of given collection
\$size = count(\$collection);
echo "\n Before sort : ";
\$obj->display_element(\$collection, \$size);
//sort collection element
\$obj->sort_element(\$collection, \$size);
echo "\n After sort  : ";
\$obj->display_element(\$collection, \$size);
}
main();``````

#### Output

`````` Before sort :   7  3  0  8  23  2  9  35  13  12  1  3

After sort  :   0  1  2  3  3  7  8  9  12  13  23  35``````
``````/*
Node Js Program
Strand Sort
*/
//Node of list element
class Node
{
constructor(data)
{
this.element = data;
this.next = null;
}
}
class StrandSort
{
//Merge two sorted list and return its result
merge_list(list1, list2)
{
if (list1 == null)
{
//When list1 is empty
return list2;
}
else if (list2 == null)
{
return list1;
}
else
{
//Some auxiliary variables
var tail = null;
var node = null;
// Combine list elements in sorted order
// This process takes(m+n) time
// Here m is size of list1
// And n is size of list2
while (list1 != null || list2 != null)
{
if (list1 != null && list2 != null)
{
if (list1.element < list2.element)
{
node = list1;
list1 = list1.next;
}
else
{
node = list2;
list2 = list2.next;
}
}
else if (list1 != null)
{
node = list1;
list1 = list1.next;
}
else
{
node = list2;
list2 = list2.next;
}
{
//When get first node of resultant list
}
else
{
//Add node at end of resultant list
tail.next = node;
}
node.next = null;
tail = node;
}
}
}
//Perform the standard sort of given list elements
stander_sort(input_list, output_list)
{
if (input_list == null)
{
return output_list;
}
//create new list and set first element of input list
var sub_list = input_list;
var tail = sub_list;
var back = null;
//visit to next element
//like remove first node initial input list
input_list = sub_list.next;
var auxiliary_list = input_list;
var item = sub_list.element;
while (auxiliary_list != null)
{
if (auxiliary_list.element > item)
{
//Add node at end of sublist
tail.next = auxiliary_list;
item = auxiliary_list.element;
if (back == null)
{
//remove front node in actual list
input_list = auxiliary_list.next;
auxiliary_list = auxiliary_list.next;
}
else
{
auxiliary_list = auxiliary_list.next;
//remove intermediate element
back.next = auxiliary_list;
}
tail = tail.next;
}
else
{
back = auxiliary_list;
auxiliary_list = auxiliary_list.next;
}
}
// Separate the new sublist
tail.next = null;
output_list = this.merge_list(output_list, sub_list);
return this.stander_sort(input_list, output_list);
}
//This are providing the environment setup to perform standard sort
sort_element(collection, size)
{
if (size <= 1)
{
return;
}
//Loop controlling variable
var i = 0;
//Create editable list
var input_list = null;
var output_list = null;
//Some auxiliary variables
var tail = null;
var node = null;
//Find add array element into custom list
for (i = 0; i < size; ++i)
{
node = new Node(collection[i]);
if (input_list == null)
{
input_list = node;
}
else
{
tail.next = node;
}
tail = node;
}
output_list = this.stander_sort(input_list, output_list);
input_list = null;
i = 0;
// Insert element into actual collection
while (output_list != null)
{
//Get current node
node = output_list;
//set element into collection
collection[i] = node.element;
//visit to next node
output_list = node.next;
node = null;
i++;
}
}
//Display element of given collection
display_element(collection, size)
{
for (var i = 0; i < size; ++i)
{
process.stdout.write("  " + collection[i]);
}
process.stdout.write("\n");
}
}

function main()
{
var obj = new StrandSort();
// Define the unsorted array elements
var collection = [7, 3, 0, 8, 23, 2, 9, 35, 13, 12, 1, 3];
//Get the size of given collection
var size = collection.length;
process.stdout.write("\n Before sort : ");
obj.display_element(collection, size);
//sort collection element
obj.sort_element(collection, size);
process.stdout.write("\n After sort  : ");
obj.display_element(collection, size);
}
main();``````

#### Output

`````` Before sort :   7  3  0  8  23  2  9  35  13  12  1  3

After sort  :   0  1  2  3  3  7  8  9  12  13  23  35``````
``````#  Python 3 Program
#  Strand Sort

# Node of list element
class Node :

def __init__(self, data) :
self.element = data
self.next = None

class StrandSort :
# Merge two sorted list and return its result
def merge_list(self, list1, list2) :
if (list1 == None) :
# When list1 is empty
return list2

elif(list2 == None) :
return list1
else :
# Some auxiliary variables
tail = None
node = None
#  Combine list elements in sorted order
#  This process takes(m+n) time
#  Here m is size of list1
#  And n is size of list2
while (list1 != None or list2 != None) :
if (list1 != None and list2 != None) :
if (list1.element < list2.element) :
node = list1
list1 = list1.next
else :
node = list2
list2 = list2.next

elif(list1 != None) :
node = list1
list1 = list1.next
else :
node = list2
list2 = list2.next

# When get first node of resultant list
else :
# Add node at end of resultant list
tail.next = node

node.next = None
tail = node

# Perform the standard sort of given list elements
def stander_sort(self, input_list, output_list) :
if (input_list == None) :
return output_list

# create new list and set first element of input list
sub_list = input_list
tail = sub_list
back = None
# visit to next element
# like remove first node initial input list
input_list = sub_list.next
auxiliary_list = input_list
item = sub_list.element
while (auxiliary_list != None) :
if (auxiliary_list.element > item) :
# Add node at end of sublist
tail.next = auxiliary_list
item = auxiliary_list.element
if (back == None) :
# remove front node in actual list
input_list = auxiliary_list.next
auxiliary_list = auxiliary_list.next
else :
auxiliary_list = auxiliary_list.next
# remove intermediate element
back.next = auxiliary_list

tail = tail.next
else :
back = auxiliary_list
auxiliary_list = auxiliary_list.next

#  Separate the new sublist
tail.next = None
output_list = self.merge_list(output_list, sub_list)
return self.stander_sort(input_list, output_list)

# This are providing the environment setup to perform standard sort
def sort_element(self, collection, size) :
if (size <= 1) :
return

# Loop controlling variable
i = 0
# Create editable list
input_list = None
output_list = None
# Some auxiliary variables
tail = None
node = None
# Find add array element into custom list
while (i < size) :
node = Node(collection[i])
if (input_list == None) :
input_list = node
else :
tail.next = node

tail = node
i += 1

output_list = self.stander_sort(input_list, output_list)
input_list = None
i = 0
#  Insert element into actual collection
while (output_list != None) :
# Get current node
node = output_list
# set element into collection
collection[i] = node.element
# visit to next node
output_list = node.next
node = None
i += 1

# Display element of given collection
def display_element(self, collection, size) :
i = 0
while (i < size) :
print("  ", collection[i], end = "")
i += 1

print("\n", end = "")

def main() :
obj = StrandSort()
#  Define the unsorted array elements
collection = [7, 3, 0, 8, 23, 2, 9, 35, 13, 12, 1, 3]
# Get the size of given collection
size = len(collection)
print("\n Before sort : ", end = "")
obj.display_element(collection, size)
# sort collection element
obj.sort_element(collection, size)
print("\n After sort  : ", end = "")
obj.display_element(collection, size)

if __name__ == "__main__": main()``````

#### Output

`````` Before sort :    7   3   0   8   23   2   9   35   13   12   1   3

After sort  :    0   1   2   3   3   7   8   9   12   13   23   35``````
``````#     Ruby Program
#     Strand Sort

# Node of list element
class Node

# Define the accessor and reader of class Node
attr_accessor :element, :next

def initialize(data)

self.element = data
self.next = nil
end
end
class StrandSort

# Merge two sorted list and return its result
def merge_list(list1, list2)

if (list1 == nil)

# When list1 is empty
return list2
elsif(list2 == nil)

return list1
else

# Some auxiliary variables
tail = nil
node = nil
#  Combine list elements in sorted order
#  This process takes(m+n) time
#  Here m is size of list1
#  And n is size of list2
while (list1 != nil || list2 != nil)

if (list1 != nil && list2 != nil)

if (list1.element < list2.element)

node = list1
list1 = list1.next
else

node = list2
list2 = list2.next
end
elsif(list1 != nil)

node = list1
list1 = list1.next
else

node = list2
list2 = list2.next
end

# When get first node of resultant list
else

# Add node at end of resultant list
tail.next = node
end
node.next = nil
tail = node
end
end
end
# Perform the standard sort of given list elements
def stander_sort(input_list, output_list)

if (input_list == nil)

return output_list
end
# create new list and set first element of input list
sub_list = input_list
tail = sub_list
back = nil
# visit to next element
# like remove first node initial input list
input_list = sub_list.next
auxiliary_list = input_list
item = sub_list.element
while (auxiliary_list != nil)

if (auxiliary_list.element > item)

# Add node at end of sublist
tail.next = auxiliary_list
item = auxiliary_list.element
if (back == nil)

# remove front node in actual list
input_list = auxiliary_list.next
auxiliary_list = auxiliary_list.next
else

auxiliary_list = auxiliary_list.next
# remove intermediate element
back.next = auxiliary_list
end
tail = tail.next
else

back = auxiliary_list
auxiliary_list = auxiliary_list.next
end
end
#  Separate the new sublist
tail.next = nil
output_list = self.merge_list(output_list, sub_list)
return self.stander_sort(input_list, output_list)
end
# This are providing the environment setup to perform standard sort
def sort_element(collection, size)

if (size <= 1)

return
end
# Loop controlling variable
i = 0
# Create editable list
input_list = nil
output_list = nil
# Some auxiliary variables
tail = nil
node = nil
# Find add array element into custom list
while (i < size)

node = Node.new(collection[i])
if (input_list == nil)

input_list = node
else

tail.next = node
end
tail = node
i += 1
end
output_list = self.stander_sort(input_list, output_list)
input_list = nil
i = 0
#  Insert element into actual collection
while (output_list != nil)

# Get current node
node = output_list
# set element into collection
collection[i] = node.element
# visit to next node
output_list = node.next
node = nil
i += 1
end
end
# Display element of given collection
def display_element(collection, size)

i = 0
while (i < size)

print("  ", collection[i])
i += 1
end
print("\n")
end
end
def main()

obj = StrandSort.new()
#  Define the unsorted array elements
collection = [7, 3, 0, 8, 23, 2, 9, 35, 13, 12, 1, 3]
# Get the size of given collection
size = collection.length
print("\n Before sort : ")
obj.display_element(collection, size)
# sort collection element
obj.sort_element(collection, size)
print("\n After sort  : ")
obj.display_element(collection, size)
end
main()``````

#### Output

`````` Before sort :   7  3  0  8  23  2  9  35  13  12  1  3

After sort  :   0  1  2  3  3  7  8  9  12  13  23  35
``````
``````/*
Scala Program
Strand Sort
*/
//Node of list element
class Node(var element: Int,
var next: Node)
{
def this(data: Int)
{
this(data, null);
}
}
class StrandSort(var input_list : Node)
{
def this()
{
this(null);
}
//Merge two sorted list and return its result
def merge_list(l1: Node, l2: Node): Node = {
var list1 = l1;
var list2 = l2;
if (list1 == null)
{
//When list1 is empty
return list2;
}
else if (list2 == null)
{
return list1;
}
else
{
//Some auxiliary variables
var tail: Node = null;
var node: Node = null;
// Combine list elements in sorted order
// This process takes(m+n) time
// Here m is size of list1
// And n is size of list2
while (list1 != null || list2 != null)
{
if (list1 != null && list2 != null)
{
if (list1.element < list2.element)
{
node = list1;
list1 = list1.next;
}
else
{
node = list2;
list2 = list2.next;
}
}
else if (list1 != null)
{
node = list1;
list1 = list1.next;
}
else
{
node = list2;
list2 = list2.next;
}
{
//When get first node of resultant list
}
else
{
//Add node at end of resultant list
tail.next = node;
}
node.next = null;
tail = node;
}
}
}
//Perform the standard sort of given list elements
def stander_sort(output_list: Node): Node = {
if (this.input_list == null)
{
return output_list;
}
//create new list and set first element of input list
var sub_list: Node = this.input_list;
var tail: Node = sub_list;
var back: Node = null;
//visit to next element
//like remove first node initial input list
this.input_list = sub_list.next;
var auxiliary_list: Node = this.input_list;
var item: Int = sub_list.element;
while (auxiliary_list != null)
{
if (auxiliary_list.element > item)
{
//Add node at end of sublist
tail.next = auxiliary_list;
item = auxiliary_list.element;
if (back == null)
{
//remove front node in actual list
this.input_list = auxiliary_list.next;
auxiliary_list = auxiliary_list.next;
}
else
{
auxiliary_list = auxiliary_list.next;
//remove intermediate element
back.next = auxiliary_list;
}
tail = tail.next;
}
else
{
back = auxiliary_list;
auxiliary_list = auxiliary_list.next;
}
}
// Separate the new sublist
tail.next = null;

return stander_sort(merge_list(output_list, sub_list));
}
//This are providing the environment setup to perform standard sort
def sort_element(collection: Array[Int], size: Int): Unit = {
if (size <= 1)
{
return;
}
//Loop controlling variable
var i: Int = 0;
//Create editable list
var output_list: Node = null;
//Some auxiliary variables
var tail: Node = null;
var node: Node = null;
//Find add array element into custom list
while (i < size)
{
node = new Node(collection(i));
if (this.input_list == null)
{
this.input_list = node;
}
else
{
tail.next = node;
}
tail = node;
i += 1;
}
output_list = stander_sort(output_list);

i = 0;
// Insert element into actual collection
while (output_list != null)
{
//Get current node
node = output_list;
//set element into collection
collection(i) = node.element;
//visit to next node
output_list = node.next;
node = null;
i += 1;
}
}
//Display element of given collection
def display_element(collection: Array[Int], size: Int): Unit = {
var i: Int = 0;
while (i < size)
{
print("  " + collection(i));
i += 1;
}
print("\n");
}
}
object Main
{
def main(args: Array[String]): Unit = {
var obj: StrandSort = new StrandSort();
// Define the unsorted array elements
var collection: Array[Int] = Array(7, 3, 0, 8, 23, 2, 9, 35, 13, 12, 1, 3);
//Get the size of given collection
var size: Int = collection.length;
print("\n Before sort : ");
obj.display_element(collection, size);
//sort collection element
obj.sort_element(collection, size);
print("\n After sort  : ");
obj.display_element(collection, size);
}
}``````

#### Output

`````` Before sort :   7  3  0  8  23  2  9  35  13  12  1  3

After sort  :   0  1  2  3  3  7  8  9  12  13  23  35``````
``````/*
Swift Program
Strand Sort
*/
//Node of list element
class Node
{
var element: Int;
var next: Node? ;
init(_ data: Int)
{
self.element = data;
self.next = nil;
}
}
class StrandSort
{
//Merge two sorted list and return its result
func merge_list(_ list1: inout Node? , _ list2 : inout Node? ) -> Node?
{
if (list1 == nil)
{
//When list1 is empty
return list2;
}
else if (list2 == nil)
{
return list1;
}
else
{
//Some auxiliary variables
var tail: Node? = nil;
var node: Node? = nil;
// Combine list elements in sorted order
// This process takes(m+n) time
// Here m is size of list1
// And n is size of list2
while (list1 != nil || list2 != nil)
{
if (list1 != nil && list2 != nil)
{
if (list1!.element < list2!.element)
{
node = list1;
list1 = list1!.next;
}
else
{
node = list2;
list2 = list2!.next;
}
}
else if (list1 != nil)
{
node = list1;
list1 = list1!.next;
}
else
{
node = list2;
list2 = list2!.next;
}
{
//When get first node of resultant list
}
else
{
//Add node at end of resultant list
tail!.next = node;
}
node!.next = nil;
tail = node;
}
}
}
//Perform the standard sort of given list elements
func stander_sort(_ input_list: inout Node? , _ output_list : inout Node? ) -> Node?
{
if (input_list == nil)
{
return output_list;
}
//create new list and set first element of input list
var sub_list: Node? = input_list;
var tail: Node? = sub_list;
var back: Node? = nil;
//visit to next element
//like remove first node initial input list
input_list = sub_list!.next;
var auxiliary_list: Node? = input_list;
var item: Int = sub_list!.element;
while (auxiliary_list != nil)
{
if (auxiliary_list!.element > item)
{
//Add node at end of sublist
tail!.next = auxiliary_list;
item = auxiliary_list!.element;
if (back == nil)
{
//remove front node in actual list
input_list = auxiliary_list!.next;
auxiliary_list = auxiliary_list!.next;
}
else
{
auxiliary_list = auxiliary_list!.next;
//remove intermediate element
back!.next = auxiliary_list;
}
tail = tail!.next;
}
else
{
back = auxiliary_list;
auxiliary_list = auxiliary_list!.next;
}
}
// Separate the new sublist
tail!.next = nil;
output_list = self.merge_list(&output_list, &sub_list);
return self.stander_sort(&input_list, &output_list);
}
//This are providing the environment setup to perform standard sort
func sort_element(_ collection: inout[Int], _ size: Int)
{
if (size <= 1)
{
return;
}
//Loop controlling variable
var i: Int = 0;
//Create editable list
var input_list: Node? = nil;
var output_list: Node? = nil;
//Some auxiliary variables
var tail: Node? = nil;
var node: Node? = nil;
//Find add array element into custom list
while (i < size)
{
node = Node(collection[i]);
if (input_list == nil)
{
input_list = node;
}
else
{
tail!.next = node;
}
tail = node;
i += 1;
}
output_list = self.stander_sort(&input_list, &output_list);
i = 0;
// Insert element into actual collection
while (output_list != nil)
{
//Get current node
node = output_list;
//set element into collection
collection[i] = node!.element;
//visit to next node
output_list = node!.next;
node = nil;
i += 1;
}
}
//Display element of given collection
func display_element(_ collection: [Int], _ size: Int)
{
var i: Int = 0;
while (i < size)
{
print("  ", collection[i], terminator: "");
i += 1;
}
print("\n", terminator: "");
}
}
func main()
{
let obj: StrandSort = StrandSort();
// Define the unsorted array elements
var collection: [Int] = [7, 3, 0, 8, 23, 2, 9, 35, 13, 12, 1, 3];
//Get the size of given collection
let size: Int = collection.count;
print("\n Before sort : ", terminator: "");
obj.display_element(collection, size);
//sort collection element
obj.sort_element(&collection, size);
print("\n After sort  : ", terminator: "");
obj.display_element(collection, size);
}
main();``````

#### Output

`````` Before sort :    7   3   0   8   23   2   9   35   13   12   1   3

After sort  :    0   1   2   3   3   7   8   9   12   13   23   35``````

## Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

Categories
Relative Post