02-Algorithm-master formula, median value, logarithmizer (C++ implementation)

2. Understand O(N*logN) sorting

Section 1, master formula

? In programming, recursion is a very common algorithm. It is widely used because of the simplicity of the code. However, compared with sequential execution or loop programs, the time complexity of recursion is difficult to calculate, and the master formula is used to calculate the time complexity of recursive programs. .

T(N) = a*T(N/b) + O(N^d);

? The parameters are explained below:

b: sample size of sub-process
a: The number of calculations of the sub-process
O(N^d): time complexity of merging sub-results

Any program that satisfies the above formula can calculate the time complexity according to the master formula:

log(b,a) > d: time complexity is O(N^log(b,a))
log(b,a) = d: time complexity is O(N^d * logN)
log(b,a) < d: time complexity is O(N^d)

Section 2, finding the median

? Before learning merge sort, we first learn a simple algorithm: when we find the median of a value, we can use:

int mid = L + ((R - L) >> 1);

? This can avoid memory leaks.

Section 3, Merge Sort

? Merge sort: Merge sort is also a process of ordering the speeds respectively. Let’s explain the merging part first. Let’s assume we have two sorted arrays. We merge these two arrays. Use a temporary array. When neither array reaches the bounds. Compare corresponding elements. Put the small number into a temporary array. If they are equal, the array on the left is put in first. After putting one in, the corresponding one will only increase by 1.

? We divide an array into two parts. Then call this margin function recursively to perform merge sorting.

? Calculated according to the master formula, the master formula of merge sort is:

T(N) = 2*T(N/2) + O(N^1);
log(2,2) = 2;

? The time complexity is O(N^d * logN).

? Because merge sort does not waste comparison operations, each comparison behavior becomes an ordered part.

The code is given below:

#include <iostream>
#include <vector>
using namespace std;

#pragma once
class MargeSort
{<!-- -->
public:
static void sort(vector<int> & amp; arr);
static void progress(vector<int> & amp;, int left, int right);
static void marge(vector<int> & amp;, int left, int right, int mid);
private:
};

#include "MargeSort.h"

void MargeSort::sort(vector<int> & amp; arr)
{<!-- -->
int length = arr.size();

if (length < 2) return;

progress(arr, 0, length - 1);
}

void MargeSort::progress(vector<int> & amp; arr, int left, int right)
{<!-- -->
if (left == right)
{<!-- -->
return;
}
int mid = left + ((right - left) >> 1);
progress(arr, left, mid);
progress(arr, mid + 1, right);
marge(arr, left, right, mid);
}

void MargeSort::marge(vector<int> & amp; arr, int left, int right, int mid)
{<!-- -->
vector<int> help;

int p1 = left;
int p2 = mid + 1;

while (p1 <= mid & amp; & amp; p2 <= right)
{<!-- -->
help.push_back(arr[p1] <= arr[p2] ? arr[p1 + + ] : arr[p2 + + ]);
}

while (p1 <= mid)
{<!-- -->
help.push_back(arr[p1 + + ]);
}

while (p2 <= right)
{<!-- -->
help.push_back(arr[p2 + + ]);
}

for (int i = 0; i < right - left + 1; i + + )
{<!-- -->
arr[i + left] = help[i];
}

help.clear();
}

Attachment: C++ Logarithmizer

#pragma once
#include <iostream>
#include <random>
#include <stdio.h>
#include <stdlib.h>
#include <windows.h>
using namespace std;

void print_arr(vector<int> & amp; arr, int length);
int random(int min, int max);
void swap(int* a, int* b);
void copy_arr(int* source, int* destination, int length);
void random_arr(vector<int> & amp; arr, int length, int min, int max);
void set_font_color(WORD color);

#include "Helper.h"

void print_arr(vector<int> & amp; arr, int length)
{<!-- -->
cout << " ";
for (int i = 0; i < length; i + + )
{<!-- -->
cout << arr[i];
if (i != length - 1)
cout << ", ";
}
cout << endl;
}

int random(int min = 0, int max = 100) {<!-- -->
random_device seed;//Hardware generates random number seed
ranlux48 engine(seed());//Use seeds to generate random number engines
uniform_int_distribution<> distrib(min, max);//Set the random number range and make it uniformly distributed
return distrib(engine);//random number
}

void random_arr(vector<int> & amp; arr, int length, int min, int max) {<!-- -->
for (int i = 0; i < length; i + + )
{<!-- -->
arr.push_back(random(min, max));
}
}

void set_font_color(WORD color)
{<!-- -->
HANDLE handle;//Create handle
handle = GetStdHandle(STD_OUTPUT_HANDLE);//Get the standard input and output handle
SetConsoleTextAttribute(handle, color);//The characters are the same as color
}

void swap(int* a, int* b) {<!-- -->
*a = *a ^ *b;
*b = *a ^ *b;
*a = *a ^ *b;
}

void copy_arr(int* source, int* destination, int length) {<!-- -->
for (int i = 0; i < length; i + + )
{<!-- -->
destination[i] = source[i];
}
}

#pragma once
#include <vector>
#include<algorithm>
using namespace std;

classCompare
{<!-- -->
public:
static void do_(int number, void(*custom_sort)(vector<int> & amp;), int length, int min, int max);
private:
static bool do_(void (*custom_sort)(vector<int> & amp;), int length, int min, int max);
static bool do_(vector<int> & amp; arr1, vector<int> & amp; arr2, int length);
};

#include "Compare.h"
#include "Helper.h"

void Compare::do_(int number, void(*custom_sort)(vector<int> & amp;), int length, int min, int max)
{<!-- -->
if (number == 0) return;

for (int i = 0; i < number; i + + )
{<!-- -->
do_(custom_sort, length, min, max);
}
}

bool Compare::do_(void(*custom_sort)(vector<int> & amp;), int length, int min, int max)
{<!-- -->
vector<int> arr;
random_arr(arr, length, min, max);

vector<int> arr1;
arr1.assign(arr.begin(), arr.end());

vector<int> arr2;
arr2.assign(arr.begin(), arr.end());

sort(arr1.begin(), arr1.end());
custom_sort(arr2);

if (!do_(arr1, arr2, length))
{<!-- -->
set_font_color(FOREGROUND_RED);
cout << "Wrong Sample: ";
print_arr(arr, length);
cout << "Wrong Sample Sort:";
print_arr(arr2, length);
cout << endl;
return false;
}
else
{<!-- -->
set_font_color(FOREGROUND_GREEN);
cout << "Right Sample: ";
print_arr(arr, length);
cout << "Right Sample Sort: ";
print_arr(arr2, length);
cout << endl;
};

set_font_color(0x07);
return true;
}

bool Compare::do_(vector<int> & amp; arr1, vector<int> & amp; arr2, int length)
{<!-- -->
bool right = true;
for (int i = 0; i < length; i + + )
{<!-- -->
if (arr1[i] == arr2[i])
{<!-- -->

}
else
{<!-- -->
right = false;
};
}
return right;
}