Sorting array

[abcd12345678910]

You have an array with N positive integers, the number of odd values and even values are equals, your work is to arrange them in non-decreasing order. You can only use a constant extra amount of memory for extra variables. See the example below:

Input: 20,4,3,9,10,23
Output: 3,4,9,10,23,20

Input: 19,24,2,40,21,9,10,9
Output: 2,9,10,9,24,19,40,21

Algorithm
1. Create a new array with size = N and assign it with all 0.

2. Compare the smallest even value with the smallest odd value in the original array, if the even value is smaller then it will be at the first position else odd value will be at the first position of the new array.

3. Run a loop to transfer value from the original to the new array. The even value will be at position n, and the odd value will be at position n + 1 (if smallest even < smallest odd) else reverse.

My algorithm seems hard to implement, does anyone have a better algorithm?

[Repeater]

Input: 20,4,3,9,10,23
Output: 3,4,9,10,23,20

Why is that the output? 20 is less than 23. That appears to be a decrease, but the instructions say "arrange them in non-decreasing order"

[abcd12345678910]

I think it is like 3 < 9 < 23, same for 4 < 10 < 20, compare odd values with odd values, even values with even values.

[Repeater]

Make two new arrays, put evens in one, odds in the other, sort them independently, copy them back over the original array, taking one from even, one from odd, until all copied.

[dhayden]

I don't see what even and odd values have to do with the problem, which just says to sort the array.

1. Create a new array with size = N

That conflicts with the requirement that

You can only use a constant extra amount of memory

Maybe I'm missing something, or there's more to the problem than you've stated, but it sounds like a simple "sort the data" problem with some additional info thrown in to distract you.

[Repeater]

The provided examples do suggest that the real task is

"sort these arrays such that the elements alternate even and odd numbers (beginning with even), and also such that the even numbers are themselves sorted low to high, and the odd numbers are also sorted low to high".

But only OP can confirm.

[abcd12345678910]

That's right, but it can begin with odd.

[Repeater]

At risk of just doing your homework for you, here's a solution.
I left three functions for you to fill in, at the top.
sortArray is the function that does the work. It doesn't make any more arrays. The sort is done in place.


If you add code to output the array at various places, you'll be able to figure out what the algorithm is doing.

Bad input will cause problems. Think about adding protection against bad input.

#include <iostream>

using namespace std;

bool isOdd(int input){ // RETURN TRUE IF INPUT IS ODD}
bool isEven(int input){ // RETURN TRUE IF INPUT IS EVEN}
void swap(int& a, int& b){// MAKE A EQUAL B, AND B EQUAL A}
void sortArray(int* array, int size);

int main()
{
  int v1[] = {20,4,3,9,10,23};
  int size = sizeof(v1) / sizeof(int);

  sortArray(v1, size);
  for (int i = 0; i < size; ++i)
    { cout << v1[i] << ' ';}
  cout << '\n';

  int another[]= { 19,24,2,40,21,9,10,9};
  size = sizeof(another) / sizeof(int);

  sortArray(another, size);
  for (int i = 0; i < size; ++i)
    { cout << another[i] << ' ';}
  cout << '\n';
  
  int another2[]= { 3,5,7,8,10,12};
  size = sizeof(another2) / sizeof(int);
  sortArray(another2, size);
  
  for (int i = 0; i < size; ++i)
    { cout << another2[i] << ' ';}
  cout << '\n';

}
  
void sortArray(int* array, int size)
{
  int index = 0;
  bool repeat = true;
  while (repeat)
    {
      repeat = false;
      index = 0;
      while (index < size - 1)
	{
	  if (isEven(index))
	    {
	      if (isOdd(array[index]))
		{
		  for (int index2 = index+1; ; index2++)
		    {
		      if (isEven(array[index2]))
			{
			  swap(array[index], array[index2]);
			  repeat = true;
			  break;
			}
		    }
		}
	    }
	  else // index is odd
	    {
	      if (isEven(array[index]))
		{
		  for (int index2 = index+1; ; index2++)
		    {
		      if (isOdd(array[index2]))
			{
			  swap(array[index], array[index2]);
			  repeat = true;
			  break;
			}
		    }
		}
	    }
	  index++;
	}
    }
		  
  repeat = true;
  while (repeat)
    {
      repeat = false;
      index = 0;
      while (index < size - 2)
	{
	  if (array[index] > array[index+2])
	    {
	      swap(array[index], array[index+2]);
	      repeat = true;	   
	    }
	  index++;
	}
    }

  if (array[0] > array[1])
    {
      for (index = 0; index < size-1; index+=2)
	{
	  swap(array[index], array[index+1]);
	}
    }
}

[dhayden]

Here's another algorithm, similar to what I think the OP was trying to do. The idea is based on a simple insertion sort. The wrinkle is that you first must figure out of the sequence starts with an even number or an odd one.

1. Find the smallest item. Swap it with the first item. Now you know if the sequence starts with an even item or an odd. Let's assume it starts with odd.

2. Starting at position 2, find the smallest even item. Swap it with the item at position 2.
3. Move to position 3. Find the smallest remaining odd item. Swap it.

Keep going. At each iteration, you move to the next position and change a variable that says whether you're looking for even numbers or odd. Find the smallest remaining even or odd number and swap it.

Example of the original input: 20,4,3,9,10,23. Note that I'll use "human friendly" indexes of 1-6 instead of C++ indexes 0-5.
1. Smallest value is 3. Swap it with the first item:

3,4,20,9,10,23

Move to position 2. Find the smallest remaining even number. It's 4, which coincidentally is already in position 2

3,4,20,9,10,23

Move to position 3. Smallest remaining odd number is 9. Swap it with the value in position 3:

3,4,9,20,10,23

Move to position 4. Smallest remaining even number is 10. Swap them:

3,4,9,10,20,23

Move to position 5. Smallest remaining odd item is 23. Swap them:

3,4,9,10,23,20

No need to check position 6 because there's nothing beyond it to swap it with.

[abcd12345678910]

Thank you, everyone.

[markyrocks]

heres my solution. It works for both test cases.

vector<int> in{ 19, 24, 2, 40, 21, 9, 10, 9 };

bool isEven(int a) { return a % 2 == 0; }

int main() {

	int t{};
	for (int x = 0; x < in.size(); x++) {
		if (in[0] > in[x]) { swap(in[0],in[x]); }
	}

	for (size_t x = 0; x < in.size() - 1; x++) {

		for (size_t i = x + 1; i < in.size(); i++) {
			if (isEven(in[x]) && isEven(in[x + 1]) && !isEven(in[i])) {
				swap(in[x+1],in[i]);
			}
			else if (isEven(in[x]) && !isEven(in[x + 1]) && !isEven(in[i]) && in[x + 1] > in[i]) {
				swap(in[x + 1],in[i]);
			}
			else if (!isEven(in[x]) && !isEven(in[x + 1]) && isEven(in[i])) {
				swap(in[x + 1], in[i]);
			}
			else if (!isEven(in[x]) && isEven(in[x + 1]) && isEven(in[i]) && in[x + 1] > in[i]) {
				swap(in[x + 1], in[i]);
			}
		}

	}
	for (int x = 0; x < in.size(); x++) {
		cout << in[x] << " ";
	}

}

[seeplus]

For your info, there's a C++ stl function called swap(), which swaps the specified arguments. See http://www.cplusplus.com/reference/utility/swap/ You need to have #include <utility> at the top.

so for eg

if (in[0] > in[x]) { t = in[0]; in[0] = in[x]; in[x] = t; }

becomes:

if (in[0] > in[x])
    std::swap(in[0], in[x]);

[markyrocks]

that will be handy bc I find myself doing this all the time. I've been doing swaps like that for so long that i hardly even think about it.

edit : i fixed it up for you seeplus.

[Repeater]

On that continuing topic, <algorithm> and various others are heaving with really useful functions and classes.

There are lots of ways to get familiar with them, but this is a good start: https://www.youtube.com/watch?v=bFSnXNIsK4A

[dhayden]

#include <iostream>
#include <algorithm>
#include <vector>
#include <limits>

using std::cin;
using std::cout;
using std::swap;
using std::min_element;
using std::vector;
using std::numeric_limits;

int main()
{
    vector<int> data;
    int val;
    // Read the vector from cin
    while (cin >> val) {
	data.push_back(val);
    }

    // get the smallest value and swap it with the first one
    // http://www.cplusplus.com/reference/algorithm/min_element/
    auto minIter = min_element(data.begin(), data.end());
    swap(*data.begin(), *minIter);


    // Get the modulus of the first value divided by 2.
    int modulus = data[0] % 2;

    for (unsigned i=1; i < data.size()-1; ++i) {
	unsigned minIdx = i;
	// http://www.cplusplus.com/reference/limits/numeric_limits/
	val = numeric_limits<int>::max();

	// Change the modulus that we're looking for.
	modulus = !modulus;    // Converts 0->1 and 1->0

	// Find the smallest remaining item with the matching modulus
	for (unsigned j=i+1; j < data.size(); ++j) {
	    if (data[j] < val && data[j]%2 == modulus) {
		minIdx = j;
		val = data[j];
	    }
	}

	// Now swap the current item with the one you found.
	swap(data[i], data[minIdx]);
    }

    // Print them out
    for (auto val : data) {
	cout << val << ' ';
    }
    cout << '\n';
}