text: # 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
explanation: The document describes a problem involving the separation of odd and even numbers in an integer array. It provides a detailed explanation of the problem, different methods to solve it, and includes test code in C++ to demonstrate the implementation and performance comparison of these methods. The document does not contain a specific math question or a question and answer.
distilabel_metadata.content: Evaluate the user given text extract and determine if it contains a math question and optionally and answer to this question.
  
  Output rules:
  
  1. Briefly describe the document and mention if it contains a question or a question and answer.
  2. Finalize the output with: Label: no-question,question,question-and-answer,multiple-question,multiple-question-and-answer
distilabel_metadata.role: system
distilabel_metadata.content: # 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
distilabel_metadata.role: user
distilabel_metadata.raw_output_q_a_detector_0: The document describes a problem involving the separation of odd and even numbers in an integer array. It provides a detailed explanation of the problem, different methods to solve it, and includes test code in C++ to demonstrate the implementation and performance comparison of these methods. The document does not contain a specific math question or a question and answer.
  
  Label: no-question