cycle_sort.cpp File Reference

Implementation of Cycle sort algorithm. More...

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

Include dependency graph for cycle_sort.cpp:

Go to the source code of this file.

Namespaces
namespace	sorting
	for working with vectors
namespace	cycle_sort
	Functions for Cycle sort algorithm.

Functions
template<typename T >
std::vector< T >	sorting::cycle_sort::cycleSort (const std::vector< T > &in_arr)
	The main function implements cycleSort.
static void	test ()
	Test implementations.
int	main ()
	Main function.

Detailed Description

Implementation of Cycle sort algorithm.

Cycle Sort is a sorting algorithm that works in \(O(n^2)\) time in the best case and works in \(O(n^2)\) in worst case. If a element is already at its correct position, do nothing. If a element is not at its correct position, we then need to move it to its correct position by computing the correct positions.Therefore, we should make sure the duplicate elements.

Author

TsungHan Ho

Definition in file cycle_sort.cpp.

Function Documentation

cycleSort()

template<typename T >

std::vector< T > sorting::cycle_sort::cycleSort

(

const std::vector< T > &

in_arr

)

The main function implements cycleSort.

Template Parameters

T	type of array

Parameters

in_arr

array to be sorted

Returns

void

Definition at line 38 of file cycle_sort.cpp.

                                                   {
    std::vector<T> arr(in_arr);
    for (int cycle_start = 0; cycle_start <= arr.size() - 1; cycle_start++) {
        // initialize item
        T item = arr[cycle_start];
 
        // Count the number of elements smaller than item, this  number is the
        // correct index of item.
        int pos = cycle_start;
        for (int i = cycle_start + 1; i < arr.size(); i++) {
            if (arr[i] < item) {
                pos++;
            }
        }
 
        // item is already in correct position
        if (pos == cycle_start) {
            continue;
        }
 
        // duplicate  elements
        while (item == arr[pos]) pos += 1;
        if (pos == cycle_start) {
            continue;
        } else {
            std::swap(item, arr[pos]);
        }
        // Rest of the  elements
        while (pos != cycle_start) {
            pos = cycle_start;
            // Find position where we put the element
            for (size_t i = cycle_start + 1; i < arr.size(); i++) {
                if (arr[i] < item) {
                    pos += 1;
                }
            }
            // duplicate  elements
            while (item == arr[pos]) pos += 1;
            if (item == arr[pos]) {
                continue;
            } else {
                std::swap(item, arr[pos]);
            }
        }
    }
    return arr;
}

main()

int main

(

void

)

Main function.

Returns

0 on exit

Definition at line 128 of file cycle_sort.cpp.

           {
    test();  // execute the test
    return 0;
}

test()

static void test ( )

static

Test implementations.

Returns

void

Definition at line 92 of file cycle_sort.cpp.

                   {
    // Test 1
    // [4, 3, 2, 1] return [1, 2, 3, 4]
    std::vector<uint32_t> array1 = {4, 3, 2, 1};
    std::cout << "Test 1... ";
    std::vector<uint32_t> arr1 = sorting::cycle_sort::cycleSort(array1);
    assert(std::is_sorted(std::begin(arr1), std::end(arr1)));
    std::cout << "passed" << std::endl;
 
    // [4.3, -6.5, -7.4, 0, 2.7, 1.8] return [-7.4, -6.5, 0, 1.8, 2.7, 4.3]
    std::vector<double> array2 = {4.3, -6.5, -7.4, 0, 2.7, 1.8};
    std::cout << "Test 2... ";
    std::vector<double> arr2 = sorting::cycle_sort::cycleSort(array2);
    assert(std::is_sorted(std::begin(arr2), std::end(arr2)));
    std::cout << "passed" << std::endl;
 
    // Test 3
    // [3, 3, 3, 3] return [3, 3, 3, 3]
    std::vector<uint32_t> array3 = {3, 3, 3, 3};
    std::cout << "Test 3... ";
    std::vector<uint32_t> arr3 = sorting::cycle_sort::cycleSort(array3);
    assert(std::is_sorted(std::begin(arr3), std::end(arr3)));
    std::cout << "passed" << std::endl;
 
    // [9, 4, 6, 8, 14, 3] return [9, 4, 6, 8, 14, 3]
    std::vector<uint32_t> array4 = {3, 4, 6, 8, 9, 14};
    std::cout << "Test 4... ";
    std::vector<uint32_t> arr4 = sorting::cycle_sort::cycleSort(array4);
    assert(std::is_sorted(std::begin(arr4), std::end(arr4)));
    std::cout << "passed" << std::endl;
}