cpp_reference/Sorts.h at master · stratx21/cpp_reference · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
/*
 * To change this license header, choose License Headers in Project Properties.
 * To change this template file, choose Tools | Templates
 * and open the template in the editor.
 */

/*
 * File:   Sorts.h
 * Author: Josh
 *
 * Created on January 16, 2018, 5:06 PM
 */


#ifndef SORTS_H
#define SORTS_H

#include <iostream>//needed for testing only
using namespace std;//needed for testing only

/**
 * To test the sorting algorithms.
 */
void testSort();

//MERGE::                                       O(n*lg(n))   <- lg = log base 2
//=============================================================================

/**
 * This function sets up the merge sort with the array and size of the array;
 *      this function assumes that the entire array of the size size should
 *      be sorted.
 *
 * precondition: size is no larger than the size of the array array.
 *
 * @param array the array to be sorted
 * @param size the size of the array to be sorted
 */
void mergeSort(int array[], int size);

/**
 * This function is the recursive function that splits the array array and
 *      merge sorts the two split parts, then merges them together.
 *
 * precondition: end is not out of range; end must be at max the length of the
 *      array minus one.
 *               start is no less than zero.
 *
 * @param array the array to be sorted
 * @param start the starting index to sort
 * @param end the end index to sort
 */
void mergeSort(int array[], int start, int end);

/**
 * This function merges two parts of the array, starting at start and ending
 *      at end, but split in the middle at middle.
 *
 * precondition: end is not out of range; end must be at max the length of the
 *      array minus one.
 *               start is no less than zero.
 *
 * @param array the array to have its parts between start and end arranged
 * @param start the start point of the part to merge
 * @param middle the middle that separates the two parts to merge
 * @param end the end point of the part to merge
 */
void merge    (int array[], int start, int middle, int end);


//BUBBLE::                                      O(n^2)
//=============================================================================

/**
 * This function sorts the array array in the form of a bubble sort.
 *
 * precondition: size is no larger than the size of the array array.
 *
 * @param array the array to be sorted
 * @param size the size of the array to be sorted
 */
void bubbleSort(int array[], int size);


//SELECTION::                                   O(n*log(n))
//=============================================================================
/**
 * This function sorts the array array in the form of a selection sort.
 *
 * precondition: size is no larger than the size of the array array.
 *
 * @param array the array to be sorted
 * @param size the size of the array to be sorted
 */
void selectionSort(int array[], int size);


//INSERTION::                                   O(n^2)
//=============================================================================

/**
 * This function sorts the array array in the form of an insertion sort.
 *
 * precondition: size is no larger than the size of the array array.
 *
 * @param array the array to be sorted
 * @param size the size of the array to be sorted
 */
void insertionSort(int array[], int size);

#endif /* SORTS_H */