Algorithms_in_C++ 1.0.0
Set of algorithms implemented in C++.
Loading...
Searching...
No Matches
strand_sort.cpp File Reference

Implementation of Strand Sort algorithm. More...

#include <iostream>
#include <list>
Include dependency graph for strand_sort.cpp:

Namespaces

namespace  sorting
 for working with vectors
 
namespace  strand
 Functions for Strand Sort algorithm.
 

Functions

template<typename T >
std::list< T > sorting::strand::strand_sort (std::list< T > lst)
 Apply sorting.
 
static void test ()
 Function for testing.
 
int main ()
 Main function.
 

Detailed Description

Implementation of Strand Sort algorithm.

Strand Sort is a sorting algorithm that works in \(O(n)\) time if list is already sorted and works in \(O(n^2)\) in worst case.

It is passed over the array to be sorted once and the ascending (sequential) numbers are taken. After the first iteration, the sequential sub-array is put on the empty sorted array. The main sequence is passed over again and a new sub-sequence is created in order. Now that the sorted array is not empty, the newly extracted substring is merged with the sorted array. Repeat types 3 and 4 until the sub-sequence and main sequence are empty.

Author
Mertcan Davulcu

Function Documentation

◆ main()

int main ( void )

Main function.

Returns
0 on exit
84 {
85 test();
86 return 0;
87}
static void test()
Function for testing.
Definition strand_sort.cpp:64
Here is the call graph for this function:

◆ strand_sort()

template<typename T >
std::list< T > sorting::strand::strand_sort ( std::list< T > lst)

Apply sorting.

Template Parameters
elementtype of list
Parameters
lstList to be sorted
Returns
Sorted list<T> instance
36 {
37 if (lst.size() < 2) { // Returns list if empty or contains only one element
38 return lst; // Returns list
39 }
40 std::list<T> result; // Define new "result" named list instance.
41 std::list<T> sorted; // Define new "sorted" named list instance.
42 while(!lst.empty()) /* if lst is not empty */ {
43 sorted.push_back(lst.front()); // Adds the first element of "lst" list to the bottom of the "sorted" list.
44 lst.pop_front(); // Remove first element of "lst" list.
45 for (auto it = lst.begin(); it != lst.end(); ) { // Return the loop as long as the current iterator is not equal to the last literator of the "lst" list.
46 if (sorted.back() <= *it) { // If the last reference of the "sorted" list is less than or equal to the current iterator reference.
47 sorted.push_back(*it); // Adds the iterator retrieved in the loop under the "sorted" list.
48 it = lst.erase(it); // Deletes the element with the current iterator and assigns the deleted element to the iterator.
49 } else {
50 it++; // Next iterator.
51 }
52 }
53 result.merge(sorted); // Merge "result" list with "sorted" list.
54 }
55 return result; // Returns sorted list
56 }
T back(T... args)
T begin(T... args)
T empty(T... args)
T end(T... args)
T erase(T... args)
uint64_t result(uint64_t n)
Definition fibonacci_sum.cpp:76
T front(T... args)
T pop_front(T... args)
T push_back(T... args)
T size(T... args)
Here is the call graph for this function:

◆ test()

static void test ( )
static

Function for testing.

Returns
N/A
64 {
65 std::list<int> lst = { -333, 525, 1, 0, 94, 52, 33 };
66
67 std::cout << "Before: ";
68 for(auto item: lst) {
69 std::cout << item << " ";
70 }
71
72 lst = sorting::strand::strand_sort(lst); // Sort list.
73
74 std::cout << "\nAfter: ";
75 for(auto item: lst) {
76 std::cout << item << " ";
77 }
78}
std::list< T > strand_sort(std::list< T > lst)
Apply sorting.
Definition strand_sort.cpp:36