stooge_sort.cpp File Reference

Stooge sort implementation in C++ More...

#include <vector>
#include <cassert>
#include <algorithm>
#include <iostream>

Include dependency graph for stooge_sort.cpp:

Go to the source code of this file.

Functions
void	stoogeSort (std::vector< int > *L, size_t i, size_t j)
	for IO operations
void	test1 ()
	Function to test sorting algorithm.
void	test2 ()
	Function to test sorting algorithm, one element.
void	test3 ()
	Function to test sorting algorithm, repeating elements.
int	main ()
	Main function.

Detailed Description

Stooge sort implementation in C++

Stooge sort is a recursive sorting algorithm. It divides the array into 3 parts and proceeds to:

• sort first two thirds of the array
• sort last two thirds of the array
• sort first two thirds of the array It's time complexity is O(n^(log3/log1.5)), which is about O(n^2.7), which makes it to be not the most efficient sorting algorithm on the street on average. Space complexity is O(1).

Definition in file stooge_sort.cpp.

Function Documentation

main()

int main

(

void

)

Main function.

Parameters

argc	commandline argument count (ignored)
argv	commandline array of arguments (ignored)

Returns

0 on exit

Definition at line 79 of file stooge_sort.cpp.

           {
    test1();
    test2();
    test3();
    
    std::cout << "All tests have successfully passed!\n";
    return 0;
}

stoogeSort()

void stoogeSort	(	std::vector< int > *	L,
		size_t	i,
		size_t	j )

for IO operations

for vector for assert for std::is_sorted

The stoogeSort() function is used for sorting the array.

Parameters

L	- vector of values (int) to be sorted in in place (ascending order)
i	- the first index of the array (0)
j	- the last index of the array (L.size() - 1)

Returns

void

Definition at line 28 of file stooge_sort.cpp.

                                                       {
    if (i >= j) {
        return;
    }
    if ((*L)[i] > (*L)[j]) {
        std::swap((*L)[i], (*L)[j]);
    }
    if (j - i > 1) {
        size_t third = (j - i + 1) / 3;
        stoogeSort(L, i, j - third);
        stoogeSort(L, i + third, j);
        stoogeSort(L, i, j - third);
    }
}

test1()

void test1

(

)

Function to test sorting algorithm.

Returns

void

Definition at line 47 of file stooge_sort.cpp.

             {
    std::vector<int> L = { 8, 9, 10, 4, 3, 5, 1 };
    stoogeSort(&L, 0, L.size() - 1);
    assert(std::is_sorted(std::begin(L), std::end(L)));
}

test2()

void test2

(

)

Function to test sorting algorithm, one element.

Returns

void

Definition at line 57 of file stooge_sort.cpp.

             {
    std::vector<int> L = { -1 };
    stoogeSort(&L, 0, L.size() - 1);
    assert(std::is_sorted(std::begin(L), std::end(L)));
}

test3()

void test3

(

)

Function to test sorting algorithm, repeating elements.

Returns

void

Definition at line 67 of file stooge_sort.cpp.

             {
    std::vector<int> L = { 1, 2, 5, 4, 1, 5 };
    stoogeSort(&L, 0, L.size() - 1);
    assert(std::is_sorted(std::begin(L), std::end(L)));
}