포드 존슨 알고리즘

현재 모든 코드는 수도 코드로 작성되어 있고, 올바르게 동작하지 않을 수 있음을 명시한다.

 

포드존슨 알고리즘은 머지 인설션 소트의 종류중 하나이다.

 

사실 로직적인 부분이 이해가 가지 않는 듯한 부분 또한 매우 많이 존재한다.

art of computer programming the volumes 이책에서 서술하고 있는 내용을 바탕으로 

코드를 작성해보았다.

 

로직의 순서는 단순하다.

처음 vector나 특정 자료구조를 사용하고 있는 배열을 받고

이를 두개로 분할한다. 만약 총 개수가 홀수개라면 마지막 인덱스만 따로 정리해두는 로직이 필요하다.

 

짝수개라면, 반으로 나눠 두개씩 짝을 짓고, 그중 큰수로 정렬을 해둔다. 그렇게 되면 

{2, 1}, {4, 3}, {6, 5} 와 같이 분할되게 되고 여기서 큰 값들만 가지고 있는 벡터를 선언해 다시 재귀를 호출한다.

그렇게 되면 머지인설션의 머지부분이 완료가 된다.

 

template <T>
void swap(T first, T second);

tempalte<T, V>
pair<T<V>> T<V>> tupleDividedByNumber(T<V>& org) {
	pair<T<V>, T<V>> retTupleTemplate;//
    for (int i = 0; i < sizeof(); ++i) {
		//
	}
    return retTupleTemplate;
}


template <T, V>
T mergeInsertion(T<V>& orgTemplateArray) {
	pair<T<V>, T<V>> divideTemplateArray;
    V oddValue;
   	divideTemplateArray = tupleDividedByNumber(orgTemplateArray);
    // 만약 사이즈가 오드면 체크하는 부분은 작성하지 않았음.
    if (orgTemplateArray.size() == 1) {
		return largeArray;
	}
}

이런식의 코드 흐름을 가지고 진행되게 된다.

여기서 이제 1개가 남았을때,  추가하고, 이제 인설트 로직을 구현하기만 하면 된다.

 

이때 인서트 되는 순서는 

1 -> 3 -> 2 -> 7 -> 5 -> 4 와 같은 순서의 형태를 띄게 되는데 이는 야곱수라고 불리는 특별한 순서를 띄게 된다. 이순서에 맞게 

로직을 작성하면 끝나게 된다.

 

int jacob[] = {
	// 특별한 야곱수 
}

Template<T, V>
T<V> insertWithJacobNumber(T<V> returnArray, T<V>& orginArray, int idx) {

    if (jacob[idx - 1] > originArray.size()) {
		return returnArray;
    }
	if (idx == 1) {
		returnArray.push_back(originArray[0]);
        return insertWithJacobNumber(returnArray, originArray, idx + 1);
    }
    for (int idx = jacob[idx]; idx > jacob[idx - 1]; idx--) {
		returnArray.push_back(originArray[jacob[idx]]);
    }
    return returnArray;
}

현재 로직에서는 사실 push_back을 하고있으나 글을 읽으면, push_back이 아니라 특정 위치값이 들어가면 된다는것을 확인 할 수 있다. 이부분을 변경하고 인덱스를 변경한다면 올바른 결과를 얻을 수 있다 .