Fundamental Algorithms Analysis (006)-Insert Sort

Insert Sort

Hahah, we aim to do it as easy as we can. We also introduce merge algorithm. Merge method is always useful when we use devide & conquer technique.

Insert sort (C++)

int* insertSort(int length,int* arr) {
	int  j, current;
	for (int i = 1; i < length; ++i) {
		current = arr[i];//save current value for it may be modified later
		for (j = i - 1; j >= 0 && current < arr[j]; --j) arr[j + 1] = arr[j];//select proper position and shift data
		arr[j + 1] = current;//insert current to suitable position
	}
	return arr;
}

If you need do that descendingly, just change the compare operator opposite.

for (j = i - 1; j >= 0 && current > arr[j]; --j) arr[j + 1] = arr[j];

Merge(C++)

We adopt traditional interface to unify our previous programs. If we didn’t, code can be much less than now. We like using containers of C++ like vector or any other to realize some problem for their safety and convenience. However, we don’t know how to use traditional array with its length transferred together in function, which makes program look ugly. If anybody knows how to access the size or length of an array when it is transferred into function as a pointer, please let me know. Thanks very much.

int* merge(int* aa1,int* aa2,int l1,int l2) {
	deque<int> a1(aa1, aa1 + l1);
	deque<int> a2(aa2, aa2 + l2);
	deque<int> a;
	int t1, t2;
	bool flag = false;
	while (!a1.empty() || !a2.empty()) {
		if (a1.empty()) (a.insert(a.end(), a2.begin(), a2.end()),flag=true);
		if (a2.empty()) (a.insert(a.end(), a1.begin(), a1.end()), flag = true);
		if (flag) break;
		a.push_back(min(a1.front(),a2.front()));
		if (a1.front() > a2.front()) a2.pop_front();
		else a1.pop_front();
	}
	int* aa = new int[l1 + l2]();
	for (int i = 0; i < a.size(); ++i)aa[i] = a[i];
	return aa;
}

Main test (C++)

#include <iostream>
using namespace std;
int* insertSort(int length,int* arr) {
	int  j, current;
	for (int i = 1; i < length; ++i) {
		current = arr[i];//save current value for it may be modified later
		for (j = i - 1; j >= 0 && current < arr[j]; --j) arr[j + 1] = arr[j];//select proper position and shift data
		arr[j + 1] = current;//insert current to suitable position
	}
	return arr;
}
int main() {
	int a[] = {2,1,3,2,4,5,6,3,4 };
	int length = end(a) - begin(a);
	int* r = insertSort(length,a);
	for (int i = 0; i < length; i++)cout << r[i] << " ";
}

---

#include <iostream>
#include <deque>
#include <algorithm>
using namespace std;
int* merge(int* aa1,int* aa2,int l1,int l2) {
	deque<int> a1(aa1, aa1 + l1);
	deque<int> a2(aa2, aa2 + l2);
	deque<int> a;
	int t1, t2;
	bool flag = false;
	while (!a1.empty() || !a2.empty()) {
		if (a1.empty()) (a.insert(a.end(), a2.begin(), a2.end()),flag=true);
		if (a2.empty()) (a.insert(a.end(), a1.begin(), a1.end()), flag = true);
		if (flag) break;
		a.push_back(min(a1.front(),a2.front()));
		if (a1.front() > a2.front()) a2.pop_front();
		else a1.pop_front();
	}
	int* aa = new int[l1 + l2]();
	for (int i = 0; i < a.size(); ++i)aa[i] = a[i];
	return aa;
}
int main() {
	int a1[]={ 1,3,5,7,9 };
	int a2[]={ 2,4,6,8,10 };
	int l1 = end(a1) - begin(a1);
	int l2 = end(a2) - begin(a2);
	int* a = merge(a1, a2,l1,l2);
	for (int i = 0; i < l1+l2; ++i)cout << a[i] << " ";
}

Merge Sort(C++)

Finally, we can have a look at merge sort algorithm using divide&conquer method.