C++ program to sort even nums in descending order then odd nums in same order using one array and without built in functions

[Paul5]

#include<iostream>
using namepsace std;
 int main()
{
    int a[10000],i,n,j,k,temp,c=0;
   
    cout<<"Enter size of the  array :";
    cin>>n;
    cout<<"Enter elements in array : ";
    for(i=0; i<n; i++)
    {
       
        if(a[i]%2==1)
         c++;
    }
    for(i=0; i<n-1; i++)
    {
           
        for(j=0; j<n-i-1; j++)
        {
           if(a[j]<a[j+1])
           {
           	temp=a[j];
           	a[j]=a[j+1];
           	a[j+1]=temp;
	   }
 
        }
       
    }   
	
    k=0;
    j=n-c;
    
     for(i=0; i<n; i++)
    {
        if(a[i]%2==0)
        {
           if(k<n-c)
               a[k++];
	}  
	else
	{
            if(j<n)
               a[j++];
	}
    }
    
 cout<<"\narray after sorting even and odd elements separately:\n ";
 
    for(i=0; i<n; i++)
    {
       cout<<a[i];
    }  
 

}
So I had this logic in my mind which I have written above The array is sorted But problem comes when to separate even and odd numbers Kindly guide me

[salem c]

https://en.wikipedia.org/wiki/Indentation_style
Your code is visually all over the place and impossible to follow.

> array after sorting even and odd elements separately
What does this mean.

Show an example input and expected output.

[jonnin]

an easy way is to use pointers.
if you sort the array by even odd first (really a type of partial sort), you can then split it with pointers into 2 'arrays' with a starting address and a # of items value, and send both of those to any standard sort function (meaning one you wrote, in this context, eg a function shellsort(startaddr, num)).

everything is done in place, you are just slicing it up.

slightly more complicated is to use a normal sort on the input array, and arrange the comparisons to take its least bit into account, such that it does a 'then by' sort ... first by parity, then by magnitude.

[rodwynnejones]

Sorting even numbers, while leaving a odd numbers in their original position in array.
Have I understood correctly?
If yes..

if(a[j] > a[j + 1] && !(a[j] % 2) && !(a[j + 1] % 2)){
//your swap routine here.
}

[Paul5]

@rodwynnejones By same order I mean also odd numbers in descending order

[Paul5]

@salem c Expected output should be like this

6 4 2 9 7 5

What so complex in my question that you did not understand?

[lastchance]

@Paul5,
I didn't fully understand your question either - and still don't. You have largely missed the point of the questions asked.

What is the expected output for the array
2 4 5 7 6 9

Is it
6 4 2 9 7 5
or
6 4 9 7 2 5
(i.e. do the even numbers retain their slots, or do they all go to the front?)

You will notice that @salem c asked you for both output and INPUT.

[salem c]

> Expected output should be like this
I asked for INPUT and OUTPUT

And no, random words and broken code are no substitute for understanding the problem you're trying to solve.

bool isSorted(int a, int b) {
  bool aEven = (a % 2) == 0;
  bool bEven = (b % 2) == 0;
  if ( aEven && !bEven ) return true;   // a is even, b is odd - that's OK
  if ( !aEven && bEven ) return false;  // a is odd, b is even, must be swapped
  // numbers have the same parity, so compare by magnitude
  return a < b;  // already sorted by magnitude
}

So this
if(a[j]<a[j+1])
becomes
if( !isSorted(a[j],a[j+1]) )

[seeplus]

It's exercises like this which teach 'C' rather than C++ for a C++ course that makes me despair for C++ teaching.

For a C++ course, teach C++. OK, once the C++ way has been taught then there's some merit in explaining about other ways of doing it - but the emphasis should always be on the C++ way.

So for this exercise, a C++ way would be:

#include <vector>
#include <algorithm>
#include <iostream>
#include <functional>

int main() {
	size_t nonums {};

	std::cout << "Enter how many numbers: ";
	std::cin >> nonums;

	std::vector<int> nums(nonums);

	std::cout << "Enter the value for each element: ";

	for (auto& n : nums)
		std::cin >> n;

	const auto odd {std::partition(nums.begin(), nums.end(), [](auto n) {return n % 2 == 0; })};

	std::sort(nums.begin(), odd, std::greater<int>());
	std::sort(odd, nums.end(), std::greater<int>());

	for (const auto& n : nums)
		std::cout << n << ' ';

	std::cout << '\n';
}

Enter how many numbers: 6
Enter the value for each element: 2 4 5 7 6 9
6 4 2 9 7 5

and IMO this (or similar) approach should be being required - not how to code in C!

[Paul5]

@salem c

Input: 5 7 9 2 4 6

Output: 6 4 2 9 7 5

Now look at the input and output you can clearly see even nums are sorted first in descending order then odd numbers are sorted in same(descending) order
My program is sorting the nums but how do I separate even and odd nums and make that output above mentioned happen
Well the code is broken that's why I am posting here If it was working fine then why would I post here?

[Paul5]

@seeplus sorry brother The requirement of my program is to use only one array not vectors

[seeplus]

Well if you have to do it the bad C way, then one way is follow the logic of the C++ way - first arrange the array so that the evens come first and then the odds. Then sort each part separately.

Perhaps:

#include <iostream>

void swap(int& a, int& b) {
    auto t {a};

    a = b;
    b = t;
}

void sort(int* array, size_t no) {
    for (size_t i {}; i < no - 1; ++i)
        for (size_t j {}; j < no - i - 1; ++j)
            if (array[j] < array[j + 1])
                swap(array[j], array[j + 1]);
}

int* partition(int* array, size_t used) {
    auto first {array}, last {first + used};

    for (; first != last; ++first) {
        while (*first % 2 == 0)
            if (++first == last)
                return first;

        do
            if (first == --last)
                return first;
        while (*last % 2);

        swap(*first, *last);
    }

    return first;
}

int main() {
    int a[100] {};
    size_t n {};

    std::cout << "Enter size of the array :";
    std::cin >> n;

    std::cout << "Enter elements in array : ";
    for (size_t i {}; i < n; ++i)
        std::cin >> a[i];

    const auto brk {partition(a, n)};

    sort(a, brk - a);
    sort(brk, n - (brk - a));

    std::cout << "\nArray after sorting even and odd elements separately:\n";
    for (size_t i {}; i < n; ++i)
        std::cout << a[i] << ' ';

    std::cout << '\n';
}

Enter size of the array :6
Enter elements in array : 5 7 9 2 4 6

Array after sorting even and odd elements separately:
6 4 2 9 7 5

[Paul5]

@seeplus my program is sorting nums in descending order but problem lies where I have to separate even and odd numbers and display the output that I have mentioned above in comment

[seeplus]

See above updated post.

[lastchance]

#include<iostream>
using namespace std;

bool isGreaterThan( int x, int y )
{
   if ( ( x + y ) % 2 ) return y % 2;    // if opposite parities, return whether y is odd
   else                 return x > y;    // otherwise just return the greater
}

int main()
{
   int a[] = { 5, 7, 9, 2, 4, 6 };
   int n = sizeof a / sizeof a[0];

   for ( int i = 0; i < n - 1; i++ )
   {
      for ( int j = 0; j < n - i - 1; j++ )
      {
         if ( isGreaterThan( a[j+1], a[j] ) )
         {
            int temp = a[j];
            a[j] = a[j+1];
            a[j+1]=temp;
         }
      }
   }
 
   for ( int i = 0; i < n; i++ ) cout << a[i] << ' ';
}

6 4 2 9 7 5 

[Paul5]

Thanks everyone for helping me

[Paul5]

@lastchance Did you used bubble sort in the program you mentioned in your comment from line 15 to 26?

[lastchance]

Did you used bubble sort in the program you mentioned in your comment from line 15 to 26?

Yes. It's just that with a specified comparator (similar, in principle, to what @salem c suggested earlier) you can move even numbers ahead and sort at the same time - you don't need separate operations.


You could do the same with std::sort (or any other sort method) if you want to:

#include <iostream>
#include <algorithm>
using namespace std;

bool isGreaterThan( int x, int y )
{
   if ( ( x + y ) % 2 ) return y % 2;    // if opposite parities, return whether y is odd
   else                 return x > y;    // otherwise just return the greater
}

int main()
{
   int a[] = { 5, 7, 9, 2, 4, 6 };
   int n = sizeof a / sizeof a[0];

   sort( a, a + n, isGreaterThan );
   for ( int e : a ) cout << e << ' ';
}

[Paul5]

@lastchance So the time complexity of the program you mentioned above with bubble sort will be same as time complexity of bubble sort or it will be different due to the bool isGreaterThan( int x, int y ) function

[lastchance]

Paul5 wrote:

So the time complexity of the program you mentioned above with bubble sort will be same as time complexity of bubble sort or it will be different due to the bool isGreaterThan( int x, int y ) function

The time complexity will be O(N²) with bubble sort irrespective of the comparator. You have nested loops, each performing O(N) operations - so N x N overall. (A minor improvement of bubble sort does offer the opportunity to finish early if the data is sorted; this is a rare event when N is large and doesn't change the time complexity of either worst or average case.) The time complexity of std::sort is O(N log(N)): again, independent of the comparator.

At the end of the day you are just replacing one greater-than (>) comparator with another slightly more complicated one. It doesn't change the time complexity of the looping arrangement.

Whoever (or whatever committee) wrote the Wikipedia article on sorting methods did quite a good job:
https://en.wikipedia.org/wiki/Sorting_algorithm

Note that bubble sort can potentially do an awful lot of swaps. That's fine if what you are exchanging are simple objects like ints, but poor if they are complex objects with a lot of components. In this case you can either revert to swapping pointers or use an alternative sort like selection sort.