Given a list N, the task is to sort all the elements in odd and even positions in increasing order. After sorting, we need to put all the odd positioned elements together, then all the even positioned elements.
Examples:
Input : [3, 2, 7, 6, 8]
Output : 3 7 8 2 6
Explanation:
Odd position elements in sorted order are 3, 7, 8.
Even position elements in sorted order are 2, 6.
Input : [1, 0, 2, 7, 0, 0]
Output : 0 1 2 0 0 7
Odd {1, 2, 0}
Even {0, 7, 0}
Approach:
- Initialize two lists to store the odd and even indexed digits.
- Traverse through all the digits and store the odd indexed digits at odd_indexes list and the even indexed digits at even_indexes list.
- Print the elements in the odd_indexes list in sorted order.
- Print the elements in the even_indexes list in sorted order.
Below is the implementation of the above approach:
C++
// C++ implementation of above approach #include<bits/stdc++.h>using namespace std;// function to print the odd and even indexed digitsvoid odd_even(int arr[], int n){ // lists to store the odd and // even positioned digits vector<int> odd_indexes; vector<int>even_indexes; // traverse through all the indexes // in the integer for (int i = 0; i < n;i++) { // if the digit is in odd_index position // append it to odd_position list if (i % 2 == 0) odd_indexes.push_back(arr[i]); // else append it to the even_position list else even_indexes.push_back(arr[i]); } // print the elements in the list in sorted order sort(odd_indexes.begin(), odd_indexes.end()); sort(even_indexes.begin(), even_indexes.end()); for(int i = 0; i < odd_indexes.size();i++) cout << odd_indexes[i] << " "; for(int i = 0; i < even_indexes.size(); i++) cout << even_indexes[i] << " "; } // Driver codeint main(){ int arr[] = {3, 2, 7, 6, 8}; int n = sizeof(arr)/sizeof(arr[0]); odd_even(arr, n);}// This code is contributed by// Surendra_Gangwar |
Java
// Java implementation of the approachimport java.util.*;class GFG {// function to print the odd and even indexed digitsstatic void odd_even(int arr[], int n){ // lists to store the odd and // even positioned digits Vector<Integer> odd_indexes = new Vector<Integer>(); Vector<Integer> even_indexes = new Vector<Integer>(); // traverse through all the indexes // in the integer for (int i = 0; i < n;i++) { // if the digit is in odd_index position // append it to odd_position list if (i % 2 == 0) odd_indexes.add(arr[i]); // else append it to the even_position list else even_indexes.add(arr[i]); } // print the elements in the list in sorted order Collections.sort(odd_indexes); Collections.sort(even_indexes); for(int i = 0; i < odd_indexes.size(); i++) System.out.print(odd_indexes.get(i) + " "); for(int i = 0; i < even_indexes.size(); i++) System.out.print(even_indexes.get(i) + " "); } // Driver codepublic static void main(String[] args){ int arr[] = {3, 2, 7, 6, 8}; int n = arr.length; odd_even(arr, n);}}// This code is contributed by Rajput-Ji |
Python3
# function to print the odd and even indexed digitsdef odd_even(n): # lists to store the odd and # even positioned digits odd_indexes = [] even_indexes = [] # traverse through all the indexes # in the integer for i in range(len(n)): # if the digit is in odd_index position # append it to odd_position list if i % 2 == 0: odd_indexes.append(n[i]) # else append it to the even_position list else: even_indexes.append(n[i]) # print the elements in the list in sorted order for i in sorted(odd_indexes): print(i, end =" ") for i in sorted(even_indexes): print(i, end =" ")# Driver Coden = [3, 2, 7, 6, 8]odd_even(n) |
C#
// C# implementation of the approachusing System;using System.Collections.Generic;class GFG {// function to print the odd and even indexed digitsstatic void odd_even(int []arr, int n){ // lists to store the odd and // even positioned digits List<int> odd_indexes = new List<int>(); List<int> even_indexes = new List<int>(); // traverse through all the indexes // in the integer for (int i = 0; i < n;i++) { // if the digit is in odd_index position // append it to odd_position list if (i % 2 == 0) odd_indexes.Add(arr[i]); // else append it to the even_position list else even_indexes.Add(arr[i]); } // print the elements in the list in sorted order odd_indexes.Sort(); even_indexes.Sort(); for(int i = 0; i < odd_indexes.Count; i++) Console.Write(odd_indexes[i] + " "); for(int i = 0; i < even_indexes.Count; i++) Console.Write(even_indexes[i] + " "); } // Driver codepublic static void Main(String[] args){ int []arr = {3, 2, 7, 6, 8}; int n = arr.Length; odd_even(arr, n);}}// This code is contributed by PrinciRaj1992 |
PHP
<?php// PHP implementation of above approach // function to print the odd and even // indexed digits function odd_even($n){ // lists to store the odd and // even positioned digits $odd_indexes = array(); $even_indexes = array(); // traverse through all the indexes // in the integer for ($i = 0; $i < sizeof($n); $i++) { // if the digit is in odd_index position // append it to odd_position list if ($i % 2 == 0) array_push($odd_indexes, $n[$i]); // else append it to the even_position list else array_push($even_indexes, $n[$i]); } // print the elements in the list in sorted order sort($odd_indexes); for ($i = 0; $i < sizeof($odd_indexes); $i++) echo $odd_indexes[$i], " "; sort($even_indexes) ; for ($i = 0; $i < sizeof($even_indexes); $i++) echo $even_indexes[$i], " ";}// Driver Code $n = array(3, 2, 7, 6, 8);odd_even($n);// This code is contributed by Ryuga?> |
Javascript
<script>// Javascript implementation of above approach // function to print the odd and even indexed digitsfunction odd_even(arr, n){ // lists to store the odd and // even positioned digits var odd_indexes = []; var even_indexes = []; // traverse through all the indexes // in the integer for (var i = 0; i < n;i++) { // if the digit is in odd_index position // append it to odd_position list if (i % 2 == 0) odd_indexes.push(arr[i]); // else append it to the even_position list else even_indexes.push(arr[i]); } // print the elements in the list in sorted order odd_indexes.sort(); even_indexes.sort(); for(var i = 0; i < odd_indexes.length;i++) document.write( odd_indexes[i] + " "); for(var i = 0; i < even_indexes.length; i++) document.write( even_indexes[i] + " "); } // Driver codevar arr = [3, 2, 7, 6, 8];var n = arr.length;odd_even(arr, n);</script> |
Output
3 7 8 2 6
Time Complexity: O(n*log(n)) //the inbuilt sort function takes N log N time to complete all operations, hence the overall time taken by the algorithm is N log N
Auxiliary Space: O(n) // since two vectors are used so the space taken by the algorithm is worst case is linear
Another Approach: The above problem can also be solved without the use of Auxiliary space. The idea is to swap the first half even positions element with the second half odd positions element. In this way, all oddly positioned elements will come in the first half while all evenly positioned elements will come in the second half of the array. After doing this we will sort the first half and then the second half of the array in increasing order individually.
Below is the implementation of the above approach:
C++
// C++ implementation of above approach#include <bits/stdc++.h>using namespace std;// Function to print the odd and even indexed digitsvoid odd_even(int arr[], int n){ // First even position // as the index starts from 0 int i = 1; // Last index int j = n - 1; // If last position is even if (j % 2 != 0) // Decrement j to odd position j--; // Swapping till half of the array // so that all odd positioned element // will occur in first half and // even positioned element will // occur in second half. while (i < j) { swap(arr[i], arr[j]); i += 2; j -= 2; } // Sorting first half of the array // containing odd positioned elements // in increasing order sort(arr, arr + (n + 1) / 2); // Sorting second half of the array // containing even positioned elements // in increasing order sort(arr + (n + 1) / 2, arr + n); // Printing all elements for (int i = 0; i < n; i++) cout << arr[i] << " ";}// Driver Codeint main(){ int arr[] = { 3, 2, 7, 6, 8 }; int n = sizeof(arr) / sizeof(arr[0]); odd_even(arr, n); return 0;}// This code is contributed by Pushpesh Raj |
Java
// Java implementation of above approachimport java.util.Arrays;public class Main { // Function to print the odd and even indexed digits static void odd_even(int[] arr, int n) { // First even position // as the index starts from 0 int i = 1; // Last index int j = n - 1; // If last position is even if (j % 2 != 0) // Decrement j to odd position j--; // Swapping till half of the array // so that all odd positioned element // will occur in first half and // even positioned element will // occur in second half. while (i < j) { int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; i += 2; j -= 2; } // Sorting first half of the array // containing odd positioned elements // in increasing order Arrays.sort(arr, 0, (n + 1) / 2); // Sorting second half of the array // containing even positioned elements // in increasing order Arrays.sort(arr, (n + 1) / 2, n); // Printing all elements for (i = 0; i < n; i++) System.out.print(arr[i] + " "); } // Driver Code public static void main(String[] args) { int[] arr = { 3, 2, 7, 6, 8 }; int n = arr.length; odd_even(arr, n); }} |
Python3
# Python implementation of above approach# Function to print the odd and even indexed digitsdef odd_even(arr, n): # First even position # as the index starts from 0 i = 1 # Last index j = n - 1 # If last position is even if (j % 2 != 0): # Decrement j to odd position j -= 1 # Swapping till half of the array # so that all odd positioned element # will occur in first half and # even positioned element will # occur in second half. while (i < j): arr[i], arr[j] = arr[j], arr[i] i += 2 j -= 2 # Sorting first half of the array # containing odd positioned elements # in increasing order arr[: (n + 1) // 2] = sorted(arr[: (n + 1) // 2]) # Sorting second half of the array # containing even positioned elements # in increasing order arr[(n + 1) // 2:] = sorted(arr[(n + 1) // 2:]) # Printing all elements for i in range(n): print(arr[i], end=" ")# Driver Codearr = [3, 2, 7, 6, 8]n = len(arr)odd_even(arr, n)# This code is contributed by Prince Kumar |
C#
using System;class Program{ // Function to print the odd and even indexed digits static void odd_even(int[] arr, int n) { // First even position // as the index starts from 0 int i = 1; // Last index int j = n - 1; // If last position is even if (j % 2 != 0) // Decrement j to odd position j--; // Swapping till half of the array // so that all odd positioned element // will occur in first half and // even positioned element will // occur in second half. while (i < j) { int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; i += 2; j -= 2; } // Sorting first half of the array // containing odd positioned elements // in increasing order Array.Sort(arr, 0, (n + 1) / 2); // Sorting second half of the array // containing even positioned elements // in increasing order Array.Sort(arr, (n + 1) / 2, n - (n + 1) / 2); // Printing all elements for (i = 0; i < n; i++) Console.Write(arr[i] + " "); } // Driver Code static void Main(string[] args) { int[] arr = { 3, 2, 7, 6, 8 }; int n = arr.Length; odd_even(arr, n); }}// This code is contributed by Sundaram |
Javascript
// javascript implementation of above approach// Function to print the odd and even indexed digitsfunction odd_even(arr, n){ // First even position // as the index starts from 0 let i = 1; // Last index let j = n - 1; // If last position is even if (j % 2 != 0) // Decrement j to odd position j--; // Swapping till half of the array // so that all odd positioned element // will occur in first half and // even positioned element will // occur in second half. while (i < j) { let temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; i += 2; j -= 2; } // Sorting first half of the array // containing odd positioned elements // in increasing order let temp = arr; arr = arr.slice(0,Math.floor((n+1)/2)).sort(function(a,b){return a-b;}); for(let i = Math.floor(n + 1)/2; i < n; i++) arr.push(temp[i]); for (let i = 0; i < n/2; i++) console.log(arr[i]); // Sorting second half of the array // containing even positioned elements // in increasing order arr = arr.slice(Math.floor((n+1)/2), n).sort(function(a,b){return a-b;}); // Printing all elements for (let i = 0; i < Math.floor((n)/2); i++) console.log(arr[i]);}// Driver Codelet arr = [3, 2, 7, 6, 8];let n = arr.length;odd_even(arr, n);// This code is contributed by Arushi Jindal. |
Output
3 7 8 2 6
Time Complexity: O(n*log(n)) //the inbuilt sort function takes N log N time to complete all operations, hence the overall time taken by the algorithm is N log N
Auxiliary Space: O(1) // since no extra array is used so the space taken by the algorithm is constant
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
