This is the same problem as in this blog, Data Structure and Algorithm - Order Array into Positive and Negative Numbers Consecutively.
As I responded the thread, some started questioning about the algorithm complexity on memcpy. Argue that memcpy takes algorithm complexity of O(N) and therefore the solution on Data Structure and Algorithm - Order Array into Positive and Negative Numbers Consecutively does not have linear algorithm complexity. My answer to this question is that memcpy has much faster performance than for-loop and usually it is target-dependent because most of CPU architecture support chunk memory relocation. More or less continuous memory shifting is optimized by hardware like SIMD and Intel Vectorisation.
Motivated by this questioning, I started to think about what other data structure will eliminate this chunk memory movement target-dependent performance issue. The linked list comes out as no surprise. As well I intended to expand my collections of linked list problems.
2. C++ Implementation
// Implementation
// ********************************************************************************
// Use some common functions in LinkedListAlgo.h
// See more about this on Linked List: Common API
/*
* This function is only for signed arithmetic type
* double, float, long, int, short, char
*/
template<typename T>
void OrderElementsIntoNegativePositiveSeries(LinkedListElement<T>* head)
{
if (head == nullptr ||
head->next == nullptr ||
head->next->next == nullptr){
return;
}
// if first value is negative, then find a positive value next
bool positiveValToFind = head->data < 0;
LinkedListElement<T>* outOfOrderNode = head;
LinkedListElement<T>* curNode = head;
LinkedListElement<T>* tempNode;
/* Slightly implementation difference:
* curNode->next : CurrentPlaceTracker
* outOfOrderNode->next : OutOfPlaceTracker
* Simply this is simple and does not need two extra pointers
* to track the two previous nodes of two trackers, as they are
* needed to swap the position of elements.
*/
while (curNode->next != nullptr) {
if ((curNode->next->data > 0 && positiveValToFind) ||
(curNode->next->data < 0 && !positiveValToFind)) {
if (outOfOrderNode->next == curNode->next) {
// Scenario 1
positiveValToFind = !positiveValToFind;
outOfOrderNode = outOfOrderNode->next;
curNode = curNode->next;
}
else {
// Scenario 2
// No memory shifting. only need to re-arrange
// the pointers
tempNode = curNode->next;
curNode->next = tempNode->next;
tempNode->next = outOfOrderNode->next;
outOfOrderNode->next = tempNode;
outOfOrderNode = tempNode->next;
}
}
else {
curNode = curNode->next;
}
}
}
// A few other functions implemented in LinkedListAlogCpp.h
// Simply to make the tests easier
// LinkedListAlogCpp.h
#ifndef LINKED_LIST_ALGO_CPP_H
#define LINKED_LIST_ALGO_CPPH
#pragma once
#include "LinkedListAlgo.h"
#include <vector>
template<typename T>
void LL_PushFrontFromStdVector(LinkedListElement<T>** head, const std::vector<T>& dataVec)
{
if (dataVec.empty()) {
return;
}
for (std::vector<T>::const_reverse_iterator cRIter = dataVec.rbegin();
cRIter != dataVec.rend(); ++cRIter) {
LL_PushFront(head, *cRIter);
}
}
template<typename T>
void LL_PushBackFromStdVector(LinkedListElement<T>** head, const std::vector<T>& dataVec)
{
if (dataVec.empty()) {
return;
}
for (std::vector<T>::const_iterator cIter = dataVec.begin();
cIter != dataVec.end(); ++cIter) {
LL_Pushback(head, *cIter);
}
}
template<typename T>
void LL_CopyDataToStdVector(LinkedListElement<T>* head, std::vector<T>& dataVec)
{
if (head != nullptr) {
dataVec.clear();
dataVec.reserve(LL_GetSize(head));
}
LinkedListElement<T>* curNode = head;
while (curNode != nullptr) {
dataVec.push_back(curNode->data);
curNode = curNode->next;
}
}
#endif
// ********************************************************************************
// Test
// The same test cases as in
// ********************************************************************************
void TestOrderElementsCornerCase()
{
{
std::vector<int> testArr;
LinkedListElement<int>* head = nullptr;
LL_PushFrontFromStdVector(&head, testArr);
OrderElementsIntoNegativePositiveSeries(head);
std::vector<int> result;
LL_CopyDataToStdVector(head, result);
assert(result.empty());
}
{
std::vector<int> testArr = { 1 };
LinkedListElement<int>* head = nullptr;
LL_PushFrontFromStdVector(&head, testArr);
OrderElementsIntoNegativePositiveSeries(head);
std::vector<int> result;
LL_CopyDataToStdVector(head, result);
assert(testArr == result);
}
{
std::vector<int> testArr = { 1, -1 };
LinkedListElement<int>* head = nullptr;
LL_PushFrontFromStdVector(&head, testArr);
OrderElementsIntoNegativePositiveSeries(head);
std::vector<int> result;
LL_CopyDataToStdVector(head, result);
assert(testArr == result);
}
}
void TestOrderElementsCase1()
{
std::vector<int> testArr = { 2, -1, -3, -7, -8, 9, 5, -5, -7 };
const std::vector<int> result = { 2, -1, 9, -3, 5, -7, -8, -5, -7 };
LinkedListElement<int>* head = nullptr;
LL_PushFrontFromStdVector(&head, testArr);
OrderElementsIntoNegativePositiveSeries(head);
std::vector<int> result1;
LL_CopyDataToStdVector(head, result1);
assert(result1 == result);
}
void TestOrderElementsCase2()
{
std::vector<int> testArr = { 2, 9, 5, 3, 2, 1, -1, -3, -7, -8, -5, -7 };
const std::vector<int> result = { 2, -1, 9, -3, 5, -7, 3, -8, 2, -5, 1, -7 };
LinkedListElement<int>* head = nullptr;
LL_PushFrontFromStdVector(&head, testArr);
OrderElementsIntoNegativePositiveSeries(head);
std::vector<int> result1;
LL_CopyDataToStdVector(head, result1);
assert(result1 == result);
}
void TestOrderElementsCase3()
{
std::vector<int> testArr = { 2, -1, -3, -7, -8, -5, -7, 9, 5, 3, 2, 1 };
const std::vector<int> result = { 2, -1, 9, -3, 5, -7, 3, -8, 2, -5, 1, -7 };
LinkedListElement<int>* head = nullptr;
LL_PushFrontFromStdVector(&head, testArr);
OrderElementsIntoNegativePositiveSeries(head);
std::vector<int> result1;
LL_CopyDataToStdVector(head, result1);
assert(result1 == result);
}
void TestOrderElementsCase4()
{
std::vector<int> testArr = { 2, -1, -3, -7, 9, 5, 3, 2, 1, -8, -5, -7 };
const std::vector<int> result = { 2, -1, 9, -3, 5, -7, 3, -8, 2, -5, 1, -7 };
LinkedListElement<int>* head = nullptr;
LL_PushFrontFromStdVector(&head, testArr);
OrderElementsIntoNegativePositiveSeries(head);
std::vector<int> result1;
LL_CopyDataToStdVector(head, result1);
assert(result1 == result);
}
void TestOrderElementsCase5()
{
std::vector<int> testArr = { -1, -3, -7, 2, 9, 5, 3, 2, 1, -8, -5, -7 };
const std::vector<int> result = { -1, 2, -3, 9, -7, 5, -8, 3, -5, 2, -7, 1 };
LinkedListElement<int>* head = nullptr;
LL_PushFrontFromStdVector(&head, testArr);
OrderElementsIntoNegativePositiveSeries(head);
std::vector<int> result1;
LL_CopyDataToStdVector(head, result1);
assert(result1 == result);
}
void TestOrderElementsCase6()
{
std::vector<int> testArr = { -1, -3, -7, -8, -5, -7, 2, 9, 5, 3, 2, 1 };
const std::vector<int> result = { -1, 2, -3, 9, -7, 5, -8, 3, -5, 2, -7, 1 };
LinkedListElement<int>* head = nullptr;
LL_PushFrontFromStdVector(&head, testArr);
OrderElementsIntoNegativePositiveSeries(head);
std::vector<int> result1;
LL_CopyDataToStdVector(head, result1);
assert(result1 == result);
}
// ********************************************************************************
No comments:
Post a Comment