Home » Data Structure » Array Data Structure

Segregate odd and even numbers using Lomuto's Partition scheme

C++ implementation to Segregate odd and even numbers using Lomuto's Partition scheme.
Submitted by Vikneshwar GK, on April 09, 2022

Consider an integer array, of size n. The task at hand is to arrange the array in such a way that the even elements are placed first followed by the odd elements.

Example:

Input:
array[]= {2, 1, 5, 3, 4, 6}

Output:
array[] = {2, 4, 6, 3, 1, 5} 

Input:
array[] = {3, 1, 5, 7, 8, 2, 4, 6}

Output:
array[] = {8, 2, 4, 6, 3, 1, 5, 7}

Solution: Lomuto's Partition

This method involves using a pointer to swap the elements accordingly to form the required format. It involves the following steps:

Initialize the pointer to the element before the first odd element in the array.
Iterate through the array.
If the element is odd, then swap it with the pointer element.
Repeat the above steps.
Print the array.

C++ Implementation:

#include <bits/stdc++.h>
#include <stdlib.h>
#include <time.h>

using namespace std;

// Function to print the array
void printArray(int array[], int length)
{
    for (int i = 0; i < length; i++) {
        cout << array[i] << " ";
    }
}

// Function to arrange even and odd numbers
void arrayRearrange(int array[], int length)
{

    int i = -1, j = 0;
    int t;
    while (j != length) {
        if (array[j] % 2 == 0) {
            i++;

            // swap the elements
            swap(array[i], array[j]);
        }
        j++;
    }

    printArray(array, length);
}

// Main Function
int main()
{
    int array[100];
    int N;
    
    cout << "Enter Number of elements: ";
    cin >> N;

    for (int i = 0; i < N; i++) {
        cout << "Enter element " << i + 1 << ": ";
        cin >> array[i];
    }

    arrayRearrange(array, N);

    return 0;
}

Output:

Enter Number of elements: 6
Enter element 1: 2
Enter element 2: 1
Enter element 3: 5
Enter element 4: 3
Enter element 5: 4
Enter element 6: 6
2 4 6 3 1 5