---
# System prepended metadata

title: DSAmidterm

---

## BinarySearch

```
bool binarysearch(int a[], int l, int r, int k){
	while(l <= r){
		int m = r - (r-l)/2;

		if(a[m] == k) return true;
		else if(a[m] < k) l = m + 1;
		else r = m - 1;
	}
	return false;
	// Do phuc tap logn

}
```
## Nội suy
```
bool interpolation(int a[], int l, int r, int k){
	while(l <= r){
		int x = int((k-a[l])*(r-l)/(a[r] - a[l])) + l;

		if(a[x] == k) return true;
		else if(a[x] < k) l = x + 1;
		else r = x - 1;
	}
	return false;
}
```
## Bubble Sort
```
void bubbleSort(int a[], int n)
{
	for(int i = 0; i < n; ++i){
		bool swapped = false;
		for(int j = 0 ; j < n-i -1 ; ++j){
			if(a[j] > a[j+1]){
				swapped = true;
				int temp = a[j];
				a[j] = a[j+1];
				a[j+1] = temp;
			}
		}
		if(!swapped) break;
	}
}
```
## ShakeSort
```
void shakesort(int a[], int n) // Cac so lon trong truong hop bubble sort => shake sort
{
	int start = 0;
	int end = n - 1;
	while(end > start)
	{
		int tmp = start;
		for(int i = start ; i < end ; ++i){
			if(a[i] > a[i+1])
			{
				tmp = i + 1;
				int temp = a[i];
				a[i] = a[i+1];
				a[i+1] = temp;
			}
		}
		end = tmp;
		for(int i = end ; i > start ; --i){
			if(a[i] < a[i-1]){
				tmp = i - 1;
				int temp = a[i-1];
				a[i-1] = a[i];
				a[i] = temp;
			}
		}
		start = tmp;
	}
}
```
## Intersection
```
void intersectionsort(int a[], int n){
	for(int i = 0; i < n ; ++i){
		int value = a[i];
		int j = i - 1;
		while(j >= 0 && a[j] > value){
			int temp = a[j];
			a[j] = a[j+1];
			a[j+1] = temp;
			j--;
		}
	}
}
```

## HeapSort
```
void sift(int a[],int l,int r) //Create heap nlogn
{

	int i = l;
	int j = 2*i;
	while(j <= r){
		if(j < r){
			if(a[j+1] > a[j]) ++j; //Max heap

		}

		if(a[i] < a[j]){ // Max heap 
			int temp = a[i];
			a[i] = a[j];
			a[j] = temp; 
			i = j;
			j = 2*i;
		}
		else{
			++i;
			j = 2*i;
		}


	}
}

void heapify(int arr[], int N, int i) // On
{
    int largest = i; // Initialize largest as root
    int l = 2 * i ; // left = 2*i + 1
    int r = 2 * i +1; // right = 2*i + 2
 
    // If left child is larger than root
    if (l < N && arr[l] > arr[largest])
        largest = l;
 
    // If right child is larger than largest so far
    if (r < N && arr[r] > arr[largest])
        largest = r;
 
    // If largest is not root
    if (largest != i) {
        swap(arr[i], arr[largest]);
 
        // Recursively heapify the affected sub-tree
        heapify(arr, N, largest);
    }
}
 
// Function to build a Max-Heap from the given array
void buildHeap(int arr[], int N)
{
    // Index of last non-leaf node
    int startIdx = (N / 2);
 
    // Perform reverse level order traversal
    // from last non-leaf node and heapify
    // each node
    for (int i = startIdx; i >= 1; i--) {
        heapify(arr, N, i);
    }
}
 


void heapSort2(int a[], int l, int r){
	for(int i = 1 ; i <= r; ++i){
		cout << a[i] << " ";
	}
	cout << endl;
	int i = l; 
	while(i <= r){
		int temp = a[i];
		a[i] = a[r];
		a[r] = temp;
		--r;
		heapify(a,r,1);
	}
}


void heapSort(int a[], int l, int r){
	int i = l; 
	while(i <= r){
		int temp = a[i];
		a[i] = a[r];
		a[r] = temp;
		--r;
		sift(a,1,r);
	}
}
```
## QuickSort
```
int partition(int a[], int l, int r)
{
	int pivot = a[l];
	int i = l;
	int j = r+1;

	while(i < j)
	{
		++i;
		while(a[i] < pivot) ++i;
		--j;
		while(a[j] > pivot) --j;

		if(i < j)
		{
			int temp = a[i];
			a[i] = a[j];
			a[j] = temp;
		}
	}


	int temp = a[l];
	a[l] = a[j];
	a[j] = temp;

	return j;
}

void qsort(int a[], int l ,int r)
{
	if(l < r)
	{
		int p = partition(a,l,r);
		qsort(a,l,p-1);
		// for(int i = 1 ; i <= r ; ++i)
		// {
		// 	cout << a[i] << " ";
		// }
		// cout << endl;
		qsort(a,p+1,r);

	}
}
```
## MergeSort

```
struct Node {
    int data;
    struct Node* next;
};

void splitList(Node* head, Node** a, Node** b) {
    Node* slow = head;
    Node* fast = head->next;
    while (fast != NULL) {
        fast = fast->next;
        if (fast != NULL) {
            slow = slow->next;
            fast = fast->next;
        }
    }
    *a = head;
    *b = slow->next;
    slow->next = NULL;
}

Node* mergeLists(Node* a, Node* b) {
    Node* result = NULL;
    if (a == NULL)
        return b;
    else if (b == NULL)
        return a;
    if (a->data <= b->data) {
        result = a;
        result->next = mergeLists(a->next, b);
    }
    else {
        result = b;
        result->next = mergeLists(a, b->next);
    }
    return result;
}

void mergeSort(Node** headRef) {
    Node* head = *headRef;
    Node* a;
    Node* b;
    if ((head == NULL) || (head->next == NULL)) {
        return;
    }
    splitList(head, &a, &b);
    mergeSort(&a);
    mergeSort(&b);
    *headRef = mergeLists(a, b);
}

void push(Node** headRef, int newData) {
    Node* newNode = new Node();
    newNode->data = newData;
    newNode->next = (*headRef);
    (*headRef) = newNode;
}

void printList(Node *node) {
    while (node!=NULL) {
        cout<<node->data<<" ";
        node = node->next;
    }
}
void merge(int a[], int l, int m, int r) // merge start 1
{
	int b[r];
	int c[r];
	int len_b = m - l + 1;
	int len_c = r-m;
	//cout << len_b << "-" << len_c << "|" << l<< endl;
	for(int i = 1 ; i <=len_b; ++i)
	{
		b[i] = a[l+i-1];
	}
	for(int i = 1; i <= len_c; ++i)
	{
		c[i] = a[i + m];
	}
	int i = 1, j = 1;
	int index = l;
	while(i < len_b + 1 && j < len_c + 1)
	{
		if(b[i] >= c[j])
		{
			a[index++] = c[j++];
		}
		else
		{
			a[index++] = b[i++];

		}
	}
	while(i < len_b + 1)
	{
		a[index++] = b[i++];
	}

	while(j < len_c + 1)
	{
		a[index++] = c[j++];
	}

}

void mergeSort(int a[], int l, int r)
{
	if(l < r)
	{
		int m = (r+l)/2;
		mergeSort(a,l,m);
		mergeSort(a,m+1,r);
		merge(a,l,m,r);

	}
}
```

## Counting Sort
```
void countingsort(int a[], int l, int r,int f[]){
	for(int i = l ; i <= r; ++i)
	{
		f[a[i]]++;
	}

	for(int i = 1 ; i <= 100; ++i)
	{
		f[i] += f[i-1];
	}
	for(int i = 1 ; i <= 100; ++i)
	{
		if(f[i] != 0)
		{
			cout << i << "-" << f[i] << endl;
		}
	}

	int b[r];
	for(int i = r; i >= l ; --i)
	{
		b[f[a[i]]] = a[i];
		f[a[i]]--;
	}

	for(int i = l ; i <= r; ++i){
		a[i] = b[i];
	}
}
```

## Radix Sort(Okn)
```
int digit(int num, int k)
{
	for(int i = 1 ; i < k ; ++i)
	{
		num /= 10;
	}
	return num%10;
}


void radix_sort(int a[], int k,int L[100][100],int size[],int n)
{
	for(int i = 0 ; i <= 9 ; ++i)
	{
		size[i] = 0;
	}
	

	for(int i = 1 ; i <= n; ++i)
	{
		int dig = digit(a[i], k);
		L[size[dig]][dig] = a[i];
		size[dig]++;
	}

	int index = 1;
	for(int i = 0 ; i <= 9 ; ++i)
	{
		for(int j = 0 ; j < size[i] ; ++j)
		{
			a[index++] = L[j][i];
		}
	}
}


void radix_sort2(int a[], int n, int k)
{
	int f[10]; // f[2] binary
	for(int i = 0 ; i <= 9 ; ++i) f[i] = 0;

	for(int i = 1 ; i <= n; ++i)
	{
		int dig = digit(a[i], k); // dig = (a[i] >> k) & 1
		f[dig]++;
	}

	for(int i = 1 ; i <= 9 ; ++i)
	{
		f[i] += f[i-1];
	}

	int b[n];

	for(int i = n; i >= 1; --i)
	{
		int dig = digit(a[i], k); // dig = (a[i] >> k) & 1
		b[f[dig]] = a[i];
		f[dig]--;
	}

	for(int i = 1 ; i <= n ; ++i)
	{
		a[i] = b[i];
	}
}
void radix_sort(vector<int>& nums,bool ascending = true, bool neg = false)
{

    if(neg)
    {
        for(int i = 0 ; i < nums.size() ; ++i) nums[i] = -nums[i];
        ascending = !ascending;

    }

    int max_nums = nums[0];
    for(int i = 1 ; i < nums.size() ; ++i)
    {
        if(max_nums < nums[i]) max_nums = nums[i];
    }
    if(max_nums == 0) return;
    int d = (int)log10(max_nums) + 1;
    for(int k = 1 ; k <= d ; ++k)
    {
        int* f = new int[10];
        for(int i = 0 ; i <= 9 ; ++i) f[i] = 0;

        for(int i = 0 ; i < nums.size(); ++i)
        {
            int dig = digit(nums[i],k);
            f[dig]++;
        }
        for(int i = 1 ; i <= 9 ; ++i) f[i] += f[i-1];

        int* b = new int[nums.size()];
        for(int i = nums.size()-1 ; i >= 0; --i)
        {
            int dig = digit(nums[i],k);
            b[f[dig]-1] = nums[i];
            f[dig]--;
        }
        for(int i = 0 ; i < nums.size(); ++i) nums[i] = b[i];       
        delete[] b;
        delete[] f;
    }

    if(ascending == false)
    {
        for(int i = 0 ; i < nums.size()/2 ; ++i)
        {
            int temp = nums[i];
            nums[i] = nums[nums.size() - i - 1];
            nums[nums.size() - i - 1] = temp;
        }
    }
    if(neg)
    {
        for(int i = 0 ; i < nums.size() ; ++i) nums[i] = -nums[i];
    }
}

void radix_sort_neg(vector<int>& nums)
{
    vector<int> nega;
    vector<int> pos;


    int n = nums.size();
    for(int i = 0 ; i < n; ++i)
    {
        if(nums[i] < 0 ) nega.push_back(nums[i]);
        else pos.push_back(nums[i]);
    }

    radix_sort(pos);
    radix_sort(nega, true, true);
    for(int i = 0 ; i < nega.size(); ++i) nums[i] = nega[i];
    for(int i = 0 ; i < pos.size(); ++i) nums[i + nega.size()] = pos[i];

}


int getbit(int val, int pos) {
	return (val >> pos) & 1;
}

void swap(int& x, int& y) {
	int tmp = x;
	x = y;
	y = tmp;
	return;
}

void msdradixsort(int a[], int l,int r, int k){
	// if (l >= r || k < 0) return;
	// int t = l, p = r;
	// while (t < p) {
	// 	while(t <= r && getbit(a[t], k) == 0) ++t;
	// 	while(p >= l && getbit(a[p], k) == 1) --p;
	// 	cout << t << ' ' << p << '\n';
	// 	if(t > p) break;
	// 	swap(a[t], a[p]);
	// 	++t;
	// 	--p;
	// 	cout << "! " << t << ' ' << p << '\n';
	// }

	// cout << l << ' ' << r << ' ' << k << ' ' << t << ' ' << p << '\n';
	// msdradixsort(a, l, t - 1 , k - 1);
	// msdradixsort(a, t, r, k - 1);
	// return;

	//
	if(l < r && k >= 0)
	{
		int left = l;
		int right = r;
		while (left <= right) {
			while((left <= r && !((a[left] >> k) & 1))) ++left;
			while((right >= l) && (((a[right] >> k) & 1))) --right;
			if(left >= right) break;
			int temp = a[left];
			a[left] = a[right];
			a[right] = temp;			
		}

		msdradixsort(a, l, left -1,k-1);
		msdradixsort(a, left,r,k-1);
	}
}


struct SNode{
	int val;
	SNode* next;
};

struct DNode{
	int val;
	DNode* next;
	DNode* prev;
};

SNode* createSNode(int value)
{
	SNode* a = new SNode;
	a->val = value;
	a->next = nullptr;
	return a;
}

DNode* createDNode(int value)
{
	DNode* a = new DNode;
	a->val = value;
	a->next = nullptr;
	a->prev = nullptr;
	return a;
}


struct Ref_single{
	SNode* head;
	SNode* tail;
	void addTail(int val)
		{
			SNode* p = createSNode(val);

			if(head == nullptr)
			{
				head= tail = p;
				return;

			}
			tail->next = p;
			tail = p;
		}

	void init()
	{
		head = nullptr;
		tail = nullptr;
	}
};


struct Ref_dual{
	DNode* head;
	DNode* tail;
	void addTail(int val)
		{
			DNode* p = createDNode(val);

			if(head == nullptr)
			{
				head= tail = p;
				return;

			}
			DNode* tmp = tail;
			tail->next = p;
			tail = p;
			tail->prev = tmp;
		}

	void init()
	{
		head = nullptr;
		tail = nullptr;
	}
};
Ref_single L[10];
Ref_dual D[10];


void radix_sort_linkedlist(int a[], int l, int r, int d)
{
	for(int i = 0 ; i <= 9 ; ++i) L[i].init();

	for(int k = 1 ; k  <= d; ++k)
	{
		for(int i = l ; i <= r; ++i)
		{
			int dig = digit(a[i], k);
			L[dig].addTail(a[i]);
		}
		int index = 1;
		for(int i = 0 ; i <= 9 ; ++i)
		{
			SNode* p = L[i].head;
			while(p != nullptr)
			{
				a[index++] = p->val;

				SNode* tmp = p->next;
				delete p;
				p = tmp;
			}

			p = nullptr;
			L[i].head = L[i].tail = nullptr;

		}
	}
}

void radix_sort_duallinkedlist(int a[], int l, int r, int d)
{
	for(int i = 0 ; i <= 9 ; ++i) L[i].init();

	for(int k = 1 ; k  <= d; ++k)
	{
		for(int i = l ; i <= r; ++i)
		{
			int dig = digit(a[i], k);
			L[dig].addTail(a[i]);
		}
		int index = 1;
		for(int i = 0 ; i <= 9 ; ++i)
		{
			SNode* p = L[i].head;
			while(p != nullptr)
			{
				a[index++] = p->val;

				SNode* tmp = p->next;
				delete p;
				p = tmp;
			}

			p = nullptr;
			L[i].head = L[i].tail = nullptr;

		}
	}
}
```
## FlashSort O(n)
```

void flashsort(int a[], int l, int r)
{

	//Giai doan 1 : Xac dinh phan lop
	int m = (int)(0.45*(r-l+1)); // so phan lop
	int L[m]; // L[i] luu vi tri bien phai cua phan lop thu i

	for(int i = 1 ; i <= m ; ++i) L[i] = 0;
	int min_a = a[l],max_a = a[l];
	
	for(int i = l ; i <= r; ++i)
	{
		if(min_a > a[i]) min_a = a[i];
		if(max_a < a[i]) max_a = a[i];
	}
	for(int i = l ; i <= r; ++i)
	{
		int k = (int)((m-1)*(a[i] - min_a)/(max_a - min_a)) + 1;
		L[k]++; // So phan tu cua phan lop thu k tang len 1
	}

	for(int k = 2 ; k <= m ; ++k) L[k] += L[k-1]; // L[i] la bien ben phai cua phan lop thu i

	//Giai doan 2 : Phan hoach phan lop

	//i <= L[kai] thi chua phan hoach
	int i = l, k = m, count = l;
	while(count <= r)
	{

		while(i > L[k])
		{
			++i;
			k = (int)((m-1)*(a[i] - min_a)/(max_a - min_a)) + 1;

		}
		int x = a[i];
		while(i <= L[k])
		{
			k = (int)((m-1)*(a[i] - min_a)/(max_a - min_a)) + 1;
			int y = a[L[k]];
			a[L[k]] = x;
			x = y;
			L[k]--;
			++count;
		}
	}
	//Giai doan 3 : Insertion sort sort cac phan tu trong bucket
	// L[i+1] bieu dieu vi tri bien ben phai cua phan lop thu i
	for(int k = 2 ; k <= m; ++k)
	{
		for(int i = L[k] - 1 ; i > L[k-1] ; --i)
		{
			if(a[i] > a[i+1])
			{
				int t = a[i];
				int j = i;
				while(j > L[k-1] && t > a[j+1])
				{
					a[j] = a[j+1];
					++j;
				}
				a[j] = t;
			}
		}
	}

}

```
```
int main(){

	int n; cin >> n;
	int a[n + 1];

	for(int i = 1 ; i <= n; ++i) cin >> a[i];
	int k,l,r;
	cin >> k >> l >> r;
	// cout << binarysearch(a,l,r,k) << endl;
	// cout << interpolation(a,l,r,k) << endl;

	//bubbleSort(a,n);
	//shakesort(a,n);
	//intersectionsort(a,n);

	// for(int i = 1 ; i <= n ; ++i)
	// {
	// 	sift(a,1,n);
	// }
	// heapSort(a,1,n);


	// buildHeap(a,n);
	// heapSort2(a,1,n);

	//qsort(a,1,n);


	// mergeSort(a,1,n);

	// int f[100];
	// for(int i = 0 ; i <= 100; ++i)
	// {
	// 	f[i] = 0;
	// }
	// countingsort(a,1,n,f);

	// int size[10];
	// int L[100][100];

	int max_a = a[1];
	for(int i = 2; i <= n; ++i)
	{
		if(max_a < a[i])
		{
			max_a = a[i];
		}
	}

	int d = (int)log10(max_a) + 1;

	// for(int k = 1 ; k <= d ; ++k)
	// {
	// 	radix_sort(a, k, L,size,n);
	// }


	// for(int k = 1 ; k <= d ; ++k)
	// {
	// 	radix_sort2(a, n,k);
	// }

	// int d = (int)log2(max_a) + 1;

	// msdradixsort(a, 1, n, d);

	radix_sort_duallinkedlist(a, 1 , n, d);

	for(int i = 1 ; i <= n; ++i){
		cout << a[i] << " ";
	}
}
```

## Other

```
struct st{
    string num;
    int index;
    
    bool operator < (const st & other) const {
        return ((num < other.num) || (num == other.num && index < other.index));
    }
};
```

```

int findkth(int a[] ,int l, int r, int k)
{
	if(l >= r) return a[l];
	int ans = a[l];

	int L[r-l+1];
	int R[r-l+1];
	int p[r-l+1];

	int len_l = 0, len_r = 0, len_p = 0;
	int pivot = a[l];
	for(int i = l ; i < r ; ++i)
	{
		if(a[i] < pivot)
		{
			L[len_l++] = a[i];
		}
		else if(a[i] == pivot)
		{
			p[len_p++] = a[i];
		}
		else
		{
			R[len_r++] = a[i];
		}
	}

	if(k <= len_l) ans =findkth(L,0,len_l,k);
	else if(k <= len_l + len_p) ans =  pivot;
	else ans = findkth(R,0,len_r, r - k );
	return ans;
}
```