Homework 3 submission

sorting.cpp

/*

    sorting.cpp

    William Farmer

 */

#include "sorting.h"
#include <cstdio>
#include <vector>
#include <cmath>

using namespace std;

vector<int> quick_sort(vector<int> data)
{
    if (data.size() <= 1)
    {
        return data;
    }
    int pivot_index = floor(data.size() / 2);
    int pivot       = data.at(pivot_index);
    vector<int> less;
    vector<int> greater;
    data.erase(data.begin() + pivot_index);
    vector<int>::iterator it;
    for (it = data.begin(); it != data.end(); it++)
    {
        if (*it <= pivot)
        {
            less.push_back(*it);
        }
        else
        {
            greater.push_back(*it);
        }
    }
    vector<int> final;
    vector<int> less_list = quick_sort(less);
    vector<int> greater_list = quick_sort(greater);
    for (it = less_list.begin(); it != less_list.end(); it++)
    {
        final.push_back(*it);
    }
    final.push_back(pivot);
    for (it = greater_list.begin(); it != greater_list.end(); it++)
    {
        final.push_back(*it);
    }
    return final;
}

void bubblesort(vector<int> &data) {
    for (int target_pos = 0; target_pos < data.size(); target_pos++)
    {
        for (int swap_pos = 0; swap_pos < data.size(); swap_pos++)
        {
            if (swap_pos != target_pos)
            {
                if (data.at(target_pos) < data.at(swap_pos))
                {
                    int value = data.at(target_pos);
                    data.erase(data.begin() + target_pos);
                    vector<int>::iterator it = data.begin() + swap_pos;
                    it = data.insert(it, value);
                }
            }
        }
    }
}

void mergesort(vector<int> &data) {
    if (data.size() > 1)
    {
        vector<int> left;
        vector<int> right;
        for (int it = 0; it != floor(data.size() / 2); it++)
        {
            left.push_back(data.at(it));
        }
        for (int it = floor(data.size() / 2); it != data.size(); it++)
        {
            right.push_back(data.at(it));
        }
        mergesort(left);
        mergesort(right);
        data = merge(left, right);
    }
}

vector<int> merge(vector<int> &left, vector<int> &right) {
    vector<int> result;
    while ((left.size() > 0) || (right.size() > 0))
    {
        if ((left.size() > 0) && (right.size() > 0))
        {
            if (left.at(0) <= right.at(0))
            {
                result.push_back(left.at(0));
                left.erase(left.begin());
            } else
            {
                result.push_back(right.at(0));
                right.erase(right.begin());
            }
        } else if (left.size() > 0)
        {
            result.push_back(left.at(0));
            left.erase(left.begin());
        } else if (right.size() > 0)
        {
            result.push_back(right.at(0));
            right.erase(right.begin());
        }
    }
    return result;
}

void mystery_sort(vector<int> &data) {
    /*
     * Insertion Sort
     */
    for (int it = 1; it <= (data.size() - 1); it++)
    {
        int insert_value = data.at(it);
        int hole = it;
        while ((hole > 0) && (insert_value < data.at(hole - 1)))
        {
            data.at(hole) = data.at(hole - 1);
            hole -= 1;
        }
        data.at(hole) = insert_value;
    }
}

sorting.py

#!/usr/bin/env python
'''
Sorting Implementations

William Farmer
CSCI2270
Sorting Algorithms
'''

import sys
import heapq

def quick_sort(data):
    '''
    Slow but clean Quicksort
    '''
    if len(data) <= 1:
        return data
    pivot_index = int(len(data) / 2) # Declares pivot as middle of list
    pivot       = data[pivot_index]  # Finds value of pivot
    less        = []                 # List of less than
    greater     = []                 # List of greater
    del data[pivot_index]            # Remove pivot
    for item in data:                # For each Item, if it's less, append
        if item <= pivot:            # to the less, otherwise to greater
            less.append(item)
        else:
            greater.append(item)
    final_list = []
    final_list += quick_sort(less)      # concatenate the sorted less
    final_list += [pivot]
    final_list += quick_sort(greater)   # And the sorted greater
    return final_list                   # Return the result

def bubble_sort(data):
    '''
    Bubble sort for a list
    '''
    for target_pos in range(len(data)):
        for swap_pos in range(len(data)):
            if target_pos == swap_pos:
                pass
            else:
                if data[target_pos] < data[swap_pos]:
                    value = data.pop(target_pos)
                    data.insert(swap_pos, value)
    return data

def merge_sort(data):
    '''
    Merge sort implementation
    '''
    if len(data) <= 1:
        return data
    left  = []
    right = []
    for item in range(0, int(len(data) / 2)):
        left.append(data[item])
    for item in range(int(len(data) / 2), int(len(data))):
        right.append(data[item])
    left = merge_sort(left)
    right = merge_sort(right)
    return merge(left, right)

def merge(left, right):
    '''
    Merges two lists and sorts
    '''
    result = []
    while len(left) > 0 or len(right) > 0:
        if len(left) > 0 and len(right) > 0:
            if left[0] <= right[0]:
                result.append(left[0])
                left = left[1:len(left)]
            else:
                result.append(right[0])
                right = right[1:len(right)]
        elif len(left) > 0:
            result.append(left[0])
            left = left[1:len(left)]
        elif len(right) > 0:
            result.append(right[0])
            right = right[1:len(right)]
    return result

def heap_sort(data):
    '''
    Uses a heap for a heapsort
    '''
    heap        = []
    sorted_list = []
    for item in data:
        heapq.heappush(heap, item)
    for number in range(len(heap)):
        sorted_list.append(heapq.heappop(heap))
    return sorted_list

test_sorting.py

#!/usr/bin/env python

import unittest
import sorting
import random
import sys
import logging

open('log.txt', mode='w').close()
logging.basicConfig(filename='log.txt',
                    level=logging.DEBUG,
                    format='%(asctime)s\t-\t%(message)s')
logging.info('Start Test Sequence\n')

class TestSortingAlgorithms(unittest.TestCase):

    def __init__(self, *args, **kwargs):
        unittest.TestCase.__init__(self, *args, **kwargs)

    def setUp(self):
        self.listOne   = [2, 5, 3, 6, 1, 6, 7, 1, 7, 8, 0, 2]
        self.listTwo   = [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2]
        self.listThree = [9, 8, 7, 6, 5, 4, 3, 2, 1, 0]
        self.listFour  = [23, 1, 12, 4, 1, 4, 3, 23, 32, 2, 3, 234, 2]
        self.big_list  = []
        for item in range(1000):
            self.big_list.append(random.randint(0,100))


    def test_bubble_sort(self):
        '''
        Test the bubble sort implementation
        '''
        logging.debug('Starting Bubble Sort')
        assert(sorting.bubble_sort(self.listOne) ==
                sorted(self.listOne))
        assert(sorting.bubble_sort(self.listTwo) ==
                sorted(self.listTwo))
        assert(sorting.bubble_sort(self.listThree) ==
                sorted(self.listThree))
        assert(sorting.bubble_sort(self.listFour) ==
                sorted(self.listFour))
        try:
            assert(sorting.bubble_sort(self.big_list) ==
                    sorted(self.big_list))
        except AssertionError:
            logging.error('Big List failed... Unknown reason...')
            logging.error(self.big_list)
            logging.error(sorting.bubble_sort(self.big_list))
            logging.error(sorted(self.big_list))
            sys.exit(1)

    def test_merge_sort(self):
        '''
        Test merge sort implementation
        '''
        logging.debug('Starting Merge Sort')
        assert(sorting.merge_sort(self.listOne) ==
                sorted(self.listOne))
        assert(sorting.merge_sort(self.listTwo) ==
                sorted(self.listTwo))
        assert(sorting.merge_sort(self.listThree) ==
                sorted(self.listThree))
        assert(sorting.merge_sort(self.listFour) ==
                sorted(self.listFour))
        try:
            assert(sorting.merge_sort(self.big_list) ==
                    sorted(self.big_list))
        except AssertionError:
            logging.error('Big List failed... Unknown reason...')
            logging.error(self.big_list)
            logging.error(sorting.merge_sort(self.big_list))
            logging.error(sorted(self.big_list))
            sys.exit(1)

    def test_quick_sort(self):
        '''
        Test quick_sort implementation
        '''
        logging.debug('Starting Quicksort')
        assert(sorted(self.listOne) ==
                sorting.quick_sort(self.listOne))
        assert(sorted(self.listTwo) ==
                sorting.quick_sort(self.listTwo))
        assert(sorted(self.listThree) ==
                sorting.quick_sort(self.listThree))
        assert(sorted(self.listFour) ==
                sorting.quick_sort(self.listFour))
        try:
            assert(sorted(self.big_list) ==
                    sorting.quick_sort(self.big_list))
        except AssertionError:
            logging.error('Big List failed... Unknown reason...')
            logging.error(self.big_list)
            logging.error(sorting.quick_sort(self.big_list))
            logging.error(sorted(self.big_list))
            sys.exit(1)

    def test_heap_sort(self):
        '''
        Tests heap sort
        '''
        logging.debug('Starting Heapsort')
        assert(sorted(self.listOne) ==
                sorting.heap_sort(self.listOne))
        assert(sorted(self.listTwo) ==
                sorting.heap_sort(self.listTwo))
        assert(sorted(self.listThree) ==
                sorting.heap_sort(self.listThree))
        assert(sorted(self.listFour) ==
                sorting.heap_sort(self.listFour))
        try:
            assert(sorted(self.big_list) ==
                    sorting.heap_sort(self.big_list))
        except AssertionError:
            logging.error('Big List failed... Unknown reason...')
            logging.error(self.big_list)
            logging.error(sorting.heap_sort(self.big_list))
            logging.error(sorted(self.big_list))
            sys.exit(1)

if __name__ == "__main__":
    unittest.main()