strand_sort.cpp File Reference

Implementation of Strand Sort algorithm. More...

#include <iostream>
#include <list>

Include dependency graph for strand_sort.cpp:

Go to the source code of this file.

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

Definition in file strand_sort.cpp.

Function Documentation

main()

int main

(

void

)

Main function.

Returns

0 on exit

Definition at line 84 of file strand_sort.cpp.

           {
    test();
    return 0;
}

strand_sort()

template<typename T>

std::list< T > sorting::strand::strand_sort

(

std::list< T >

lst

)

Apply sorting.

Template Parameters

element

type of list

Parameters

lst	List to be sorted

Returns

Sorted list<T> instance

Definition at line 36 of file strand_sort.cpp.

                                               {
            if (lst.size() < 2) { // Returns list if empty or contains only one element
                return lst; // Returns list
            }
            std::list<T> result; // Define new "result" named list instance.
            std::list<T> sorted; // Define new "sorted" named list instance.
            while(!lst.empty()) /* if lst is not empty */ {
                sorted.push_back(lst.front()); // Adds the first element of "lst" list to the bottom of the "sorted" list.
                lst.pop_front(); // Remove first element of "lst" list.
                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.
                    if (sorted.back() <= *it) { // If the last reference of the "sorted" list is less than or equal to the current iterator reference.
                        sorted.push_back(*it); // Adds the iterator retrieved in the loop under the "sorted" list.
                        it = lst.erase(it); // Deletes the element with the current iterator and assigns the deleted element to the iterator.
                    } else {
                        it++; // Next iterator.
                    }
                }
                result.merge(sorted); // Merge "result" list with "sorted" list.
            }
            return result; // Returns sorted list
        }

test()

void test ( )

static

Function for testing.

Returns

N/A

Definition at line 64 of file strand_sort.cpp.

                   {
    std::list<int> lst = { -333, 525, 1, 0, 94, 52, 33 };
 
    std::cout << "Before: ";
    for(auto item: lst) {
        std::cout << item << " ";
    }
 
    lst = sorting::strand::strand_sort(lst); // Sort list.
 
    std::cout << "\nAfter: ";
    for(auto item: lst) {
        std::cout << item << " ";
    }
}