Sorting Algorithm

Files
file	merge_sort.cpp
	Merege Sort Algorithm (MEREGE 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 >

static 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.

                                                     {
    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;
}

Here is the call graph for this function:

heapify()

template<typename T >

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

                                   {
    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

                             {
    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);
    }
}

Here is the call graph for this function:

main()

int main

(

void

)

Main function

Driver Code

           {
    int size;
    std::cout << "Enter the number of elements : ";
    std::cin >> size;
    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;
}

Here is the call graph for this function:

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

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

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

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

Here is the call graph for this function:

show()

void show	(	int *	arr,
		int	size )

Utility function used to print the array after sorting

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

test()

static void test ( )

static

Test function

Returns

void

                   {
    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";
}

Here is the call graph for this function: