Sorting Algorithm

Files
file	merge_sort.cpp
	Merge Sort Algorithm (MERGE SORT) implementation
file	wiggle_sort.cpp
	[Wiggle Sort Algorithm] (https://leetcode.com/problems/wiggle-sort-ii/) Implementation

Namespaces
namespace	sorting
	for working with vectors

Functions
template<typename T>
void	heapify (T *arr, int n, int i)
template<typename T>
void	heapSort (T *arr, int n)
void	merge (int *arr, int l, int m, int r)
void	mergeSort (int *arr, int l, int r)
void	show (int *arr, int size)
int	main ()
template<typename T>
static void	displayElements (const std::vector< T > &arr)
	Utility function used for printing the elements. Prints elements of the array after they're sorted using wiggle sort algorithm.
static void	test ()

Detailed Description

The heapify procedure can be thought of as building a heap from the bottom up by successively sifting downward to establish the heap property.

Parameters

arr	array to be sorted
n	size of array
i	node position in Binary Tress or element position in Array to be compared with it's childern

Function Documentation

displayElements()

template<typename T>

void displayElements ( const std::vector< T > & arr )

static

Utility function used for printing the elements. Prints elements of the array after they're sorted using wiggle sort algorithm.

Parameters

arr	array containing the sorted elements

Examples

/Users/runner/work/C-Plus-Plus/C-Plus-Plus/sorting/wiggle_sort.cpp.

Definition at line 86 of file wiggle_sort.cpp.

                                                     {
    uint32_t size = arr.size();
 
    std::cout << "Sorted elements are as follows: ";
 
    std::cout << "[";
 
    for (int i = 0; i < size; i++) {
        std::cout << arr[i];
        if (i != size - 1) {
            std::cout << ", ";
        }
    }
 
    std::cout << "]" << std::endl;
}

heapify()

template<typename T>

void heapify	(	T *	arr,
		int	n,
		int	i )

Definition at line 58 of file heap_sort.cpp.

                                   {
    int largest = i;
    int l = 2 * i + 1;
    int r = 2 * i + 2;
 
    if (l < n && arr[l] > arr[largest])
        largest = l;
 
    if (r < n && arr[r] > arr[largest])
        largest = r;
 
    if (largest != i) {
        std::swap(arr[i], arr[largest]);
        heapify(arr, n, largest);
    }
}

heapSort()

template<typename T>

void heapSort	(	T *	arr,
		int	n )

Utilizes heapify procedure to sort the array

Parameters

arr	array to be sorted
n	size of array

Definition at line 84 of file heap_sort.cpp.

                             {
    for (int i = n - 1; i >= 0; i--) heapify(arr, n, i);
 
    for (int i = n - 1; i >= 0; i--) {
        std::swap(arr[0], arr[i]);
        heapify(arr, i, 0);
    }
}

main()

int main

(

void

)

Main function

Driver Code

Definition at line 101 of file merge_sort.cpp.

           {
    int size;
    std::cout << "Enter the number of elements: ";
    std::cin >> size;
 
    if (size <= 0) {
        std::cout << "Invalid size.\n";
        return 1;
    }
 
    int *arr = new int[size];
    std::cout << "Enter the unsorted elements: ";
    for (int i = 0; i < size; ++i) {
        std::cin >> arr[i];
    }
 
    mergeSort(arr, 0, size - 1);
    std::cout << "Sorted array: ";
    show(arr, size);
    delete[] arr;
    return 0;
}

merge()

void merge	(	int *	arr,
		int	l,
		int	m,
		int	r )

The merge() function is used for merging two halves. The merge(arr, l, m, r) is key process that assumes that arr[l..m] and arr[m+1..r] are sorted and merges the two sorted sub-arrays into one.

Parameters

arr	- array with two halves arr[l...m] and arr[m+1...r]
l	- left index or start index of first half array
m	- right index or end index of first half array

(The second array starts form m+1 and goes till r)

Parameters

r	- end index or right index of second half array

Definition at line 37 of file merge_sort.cpp.

                                          {
    int n1 = m - l + 1;
    int n2 = r - m;
 
    std::vector<int> L(n1), R(n2);
 
    for (int i = 0; i < n1; i++) L[i] = arr[l + i];
    for (int j = 0; j < n2; j++) R[j] = arr[m + 1 + j];
 
    int i = 0, j = 0, k = l;
 
    while (i < n1 && j < n2) {
        if (L[i] <= R[j]) {
            arr[k] = L[i];
            i++;
        } else {
            arr[k] = R[j];
            j++;
        }
        k++;
    }
 
    while (i < n1) {
        arr[k] = L[i];
        i++;
        k++;
    }
 
    while (j < n2) {
        arr[k] = R[j];
        j++;
        k++;
    }
}

mergeSort()

void mergeSort	(	int *	arr,
		int	l,
		int	r )

Merge sort is a divide and conquer algorithm, it divides the input array into two halves and calls itself for the two halves and then calls merge() to merge the two halves

Parameters

arr	- array to be sorted
l	- left index or start index of array
r	- right index or end index of array

Definition at line 82 of file merge_sort.cpp.

                                       {
    if (l < r) {
        int m = l + (r - l) / 2;
        mergeSort(arr, l, m);
        mergeSort(arr, m + 1, r);
        merge(arr, l, m, r);
    }
}

show()

void show	(	int *	arr,
		int	size )

Utility function used to print the array after sorting

Definition at line 95 of file merge_sort.cpp.

                              {
    for (int i = 0; i < size; i++) std::cout << arr[i] << " ";
    std::cout << "\n";
}

test()

void test ( )

static

Test function

Returns

void

Definition at line 107 of file wiggle_sort.cpp.

                   {
    std::srand(std::time(nullptr));  // initialize random number generator
 
    std::vector<float> data1(100);
    for (auto &d : data1) {  // generate random numbers between -5.0 and 4.99
        d = float(std::rand() % 1000 - 500) / 100.f;
    }
 
    std::vector<float> sorted = sorting::wiggle_sort::wiggleSort<float>(data1);
 
    displayElements(sorted);
 
    for (uint32_t j = 0; j < data1.size(); j += 2) {
        assert(data1[j] <= data1[j + 1] &&
               data1[j + 1] >= data1[j + 2]);  // check the validation condition
    }
 
    std::cout << "Test 1 passed\n";
}