# Selected algorithm problem -- odd and even data separation

Posted by Nulletz on Mon, 14 Feb 2022 10:03:52 +0100

Author: Zhai Tianbao Steven

### Title Description:

Input an integer array and implement a function to adjust the order of numbers in the array, so that all odd numbers are in the first half of the array and all even numbers are in the second half of the array, and ensure that the relative position between odd numbers and odd numbers, even numbers and even numbers remains unchanged.

### Problem solving ideas:

The topic is simple, but you can expand your ideas. I used three methods: vector storage, list storage and user-defined linked list storage to verify the calculation efficiency. The three methods adopt the idea of traversal. In the traversal process, the odd number is stored in one container, the even number is stored in another container, and then the two containers can be combined. Among them, I have customized a linked list to connect the tail of odd linked list and the head of even linked list, which saves the process of merging containers and has high insertion efficiency. There is a complete speed comparison scheme in the follow-up of the article.

### Test code:

```#include <iostream>
#include <string>
#include <vector>
#include <deque>
#include <time.h>
#include <list>

using namespace std;

struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) :
val(x), next(NULL) {
}
};

// Judge whether it is an odd number
bool isOdd(int number)
{
return (bool)(number % 2);
}

// Odd even separation
vector<int> OddEvenSeparate1(vector<int> input)
{
vector<int> output;
vector<int> evens;
for (int i = 0; i < input.size(); ++i)
{
if (isOdd(input[i]))
{
output.emplace_back(input[i]);
}
else
{
evens.emplace_back(input[i]);
}
}
output.insert(output.end(), evens.begin(), evens.end());
return output;
}

// Odd even separation
list<int> OddEvenSeparate2(vector<int> input)
{
list<int> output;
list<int> evens;
for (int i = 0; i < input.size(); ++i)
{
if (isOdd(input[i]))
{
output.emplace_back(input[i]);
}
else
{
evens.emplace_back(input[i]);
}
}
output.splice(output.end(), evens);
return output;
}

// Odd even separation
ListNode* OddEvenSeparate3(vector<int> input)
{
ListNode* output = new ListNode(-1);
ListNode* evens = new ListNode(-1);
for (int i = 0; i < input.size(); ++i)
{
if (isOdd(input[i]))
{
ListNode* temp = new ListNode(input[i]);
output->next = temp;
output = output->next;
}
else
{
ListNode* temp = new ListNode(input[i]);
evens->next = temp;
evens = evens->next;
}
}
}

int main()
{
// Given array
vector<int> a(10000);
for (int i = 0; i < a.size(); ++i)
{
a[i] = rand();
}
clock_t s, e;
// Odd even separation
// The first method
s = clock();
vector<int> b1 = OddEvenSeparate1(a);
e = clock();
cout << "time1:" << e - s << endl;
cout << "first:" << endl;
for (auto i : b1)
{
cout << i << " ";
}
cout << endl;
// The second method
s = clock();
list<int> b2 = OddEvenSeparate2(a);
e = clock();
cout << "time2:" << e - s << endl;
cout << "second:" << endl;
for (auto i : b2)
{
cout << i << " ";
}
cout << endl;
// The third method
s = clock();
ListNode* b3 = OddEvenSeparate3(a);
e = clock();
cout << "time3:" << e - s << endl;
cout << "third:" << endl;
while (b3 != nullptr)
{
cout << b3->val << " ";
b3 = b3->next;
}
cout << endl;

system("pause");
return 0;
}
```

# Test results:

When the input array is 10 numbers, verify the accuracy of the next three methods, as shown in Figure 1.

Figure 1. Verification accuracy

When the input array is 10 million, the speed under debug is shown in Figure 2.

Fig. 2 speed comparison under release

When the input array is 10 million, the speed under release is shown in Figure 3.

Figure 3 speed comparison under debug

As can be seen from the above figure, the user-defined linked list is the fastest in debug mode, but the vector is the fastest in release mode, and the user-defined linked list is slightly faster than the list in STL.

If the code needs to be improved or has any bug s, please comment and leave a message. I will correct it in time to avoid misleading others~

If the article helps you, you can point a praise to let me know, I will be very happy ~ come on!

Topics: C++ Algorithm Container
The text passage describes a programming problem where the task is to separate odd and even numbers in an array while maintaining their relative order. It includes a detailed explanation of the problem, the solution approaches, and the test code with performance comparisons.
no_question

the passage does not contain any explicit mathematical questions or word problems that require a numerical answer. it is primarily a description of a programming task and its implementation.
Given a text passage, determine:
    1. If it contains a mathematical question (including word problems or calculations)
    2. If an answer to that mathematical question is provided in the text

First, describe the content structure you found in 1-2 sentences.

Then provide your analysis in the following format:
TYPE: <one of the following values>
- NO_QUESTION
- SINGLE_QUESTION
- SINGLE_QUESTION_WITH_ANSWER
- MULTIPLE_QUESTIONS
- MULTIPLE_QUESTIONS_WITH_ANSWERS
system
# Selected algorithm problem -- odd and even data separation

Posted by Nulletz on Mon, 14 Feb 2022 10:03:52 +0100

Author: Zhai Tianbao Steven

### Title Description:

Input an integer array and implement a function to adjust the order of numbers in the array, so that all odd numbers are in the first half of the array and all even numbers are in the second half of the array, and ensure that the relative position between odd numbers and odd numbers, even numbers and even numbers remains unchanged.

### Problem solving ideas:

The topic is simple, but you can expand your ideas. I used three methods: vector storage, list storage and user-defined linked list storage to verify the calculation efficiency. The three methods adopt the idea of traversal. In the traversal process, the odd number is stored in one container, the even number is stored in another container, and then the two containers can be combined. Among them, I have customized a linked list to connect the tail of odd linked list and the head of even linked list, which saves the process of merging containers and has high insertion efficiency. There is a complete speed comparison scheme in the follow-up of the article.

### Test code:

```#include <iostream>
#include <string>
#include <vector>
#include <deque>
#include <time.h>
#include <list>

using namespace std;

struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) :
val(x), next(NULL) {
}
};

// Judge whether it is an odd number
bool isOdd(int number)
{
return (bool)(number % 2);
}

// Odd even separation
vector<int> OddEvenSeparate1(vector<int> input)
{
vector<int> output;
vector<int> evens;
for (int i = 0; i < input.size(); ++i)
{
if (isOdd(input[i]))
{
output.emplace_back(input[i]);
}
else
{
evens.emplace_back(input[i]);
}
}
output.insert(output.end(), evens.begin(), evens.end());
return output;
}

// Odd even separation
list<int> OddEvenSeparate2(vector<int> input)
{
list<int> output;
list<int> evens;
for (int i = 0; i < input.size(); ++i)
{
if (isOdd(input[i]))
{
output.emplace_back(input[i]);
}
else
{
evens.emplace_back(input[i]);
}
}
output.splice(output.end(), evens);
return output;
}

// Odd even separation
ListNode* OddEvenSeparate3(vector<int> input)
{
ListNode* output = new ListNode(-1);
ListNode* evens = new ListNode(-1);
for (int i = 0; i < input.size(); ++i)
{
if (isOdd(input[i]))
{
ListNode* temp = new ListNode(input[i]);
output->next = temp;
output = output->next;
}
else
{
ListNode* temp = new ListNode(input[i]);
evens->next = temp;
evens = evens->next;
}
}
}

int main()
{
// Given array
vector<int> a(10000);
for (int i = 0; i < a.size(); ++i)
{
a[i] = rand();
}
clock_t s, e;
// Odd even separation
// The first method
s = clock();
vector<int> b1 = OddEvenSeparate1(a);
e = clock();
cout << "time1:" << e - s << endl;
cout << "first:" << endl;
for (auto i : b1)
{
cout << i << " ";
}
cout << endl;
// The second method
s = clock();
list<int> b2 = OddEvenSeparate2(a);
e = clock();
cout << "time2:" << e - s << endl;
cout << "second:" << endl;
for (auto i : b2)
{
cout << i << " ";
}
cout << endl;
// The third method
s = clock();
ListNode* b3 = OddEvenSeparate3(a);
e = clock();
cout << "time3:" << e - s << endl;
cout << "third:" << endl;
while (b3 != nullptr)
{
cout << b3->val << " ";
b3 = b3->next;
}
cout << endl;

system("pause");
return 0;
}
```

# Test results:

When the input array is 10 numbers, verify the accuracy of the next three methods, as shown in Figure 1.

Figure 1. Verification accuracy

When the input array is 10 million, the speed under debug is shown in Figure 2.

Fig. 2 speed comparison under release

When the input array is 10 million, the speed under release is shown in Figure 3.

Figure 3 speed comparison under debug

As can be seen from the above figure, the user-defined linked list is the fastest in debug mode, but the vector is the fastest in release mode, and the user-defined linked list is slightly faster than the list in STL.

If the code needs to be improved or has any bug s, please comment and leave a message. I will correct it in time to avoid misleading others~

If the article helps you, you can point a praise to let me know, I will be very happy ~ come on!

Topics: C++ Algorithm Container
user
The text passage describes a programming problem where the task is to separate odd and even numbers in an array while maintaining their relative order. It includes a detailed explanation of the problem, the solution approaches, and the test code with performance comparisons.

TYPE: NO_QUESTION

The passage does not contain any explicit mathematical questions or word problems that require a numerical answer. It is primarily a description of a programming task and its implementation.