게하! 개하! (게임도 하고 개발도 하고)

알고리즘 과제 PA1 본문

알고리즘/[2020] 알고리즘 과제

알고리즘 과제 PA1

Sorrel 2021. 1. 9. 16:03
#include <iostream>
#include "inv.h"

#define MODE 0

using namespace std;
inv::inv(){
	this->array = NULL;
	this->size = 0;
}
inv::~inv(){
	if(this->array)	delete this->array;
	return;
}
void inv::reset(int *a, int s){
	int i=0;
	if(this->array)	delete this->array;

	this->array = new int[s];
	this->size = s;
	for(i=0;i<s;i++)	*(this->array+i) = *(a+i);
	return;
}
void inv::printArray(void){
	int i = 0;
	for(i=0;i<size;i++)	cout<<*(this->array+i)<<" ";
	cout<<endl;
}
int inv::merge(int *data, int start, int mid, int end){
	int i = start;
	int j = mid+1;
	int k = start;
	int sorted[size+1];
	int cnt=0;
	while(i<=mid&&j<=end){
		if(data[i]<=data[j]){
			sorted[k++]=data[i++];
		}else{
			sorted[k++]=data[j++];
			cnt+=mid-i+1;
		}
	}
	if(i>mid){
		for(int t = j; t<=end; t++){
			sorted[k++] = data[t];
		}
	}
	else{
		for(int t = i; t<=mid; t++){
			sorted[k++]=data[t];
		}
	}
	for(int t = start ; t<=end; t++){
		data[t]=sorted[t];
	}
	return cnt;
}

int inv::mergeSort(int *data, int start, int end){
	if(start<end){
		int count=0;
		int mid=(start+end)/2;
		count+=mergeSort(data, start, mid);
		count+=mergeSort(data, mid+1, end);
	        count+=merge(data, start, mid, end);
	return count;
	}
	else
		return 0;
}	
int inv::numOfInv(void){
	return mergeSort(array, 0, size-1);
}

'알고리즘 > [2020] 알고리즘 과제' 카테고리의 다른 글

알고리즘 과제 PA4  (0) 2021.01.09
알고리즘 과제 PA3  (0) 2021.01.09
알고리즘 과제 PA2  (0) 2021.01.09
알고리즘 과제 PA1  (0) 2021.01.09
알고리즘 과제 PA5  (0) 2021.01.09
0 Comments
댓글쓰기 폼