Sortera jämnt placerat i ökande och udda placerat i fallande ordning
Vi får en matris med n distinkta tal. Uppgiften är att sortera alla jämna nummer i ökande och udda nummer i fallande ordning. Den modifierade matrisen ska innehålla alla sorterade jämna nummer följt av omvänt sorterade udda nummer.
Observera att det första elementet anses vara jämnt placerat på grund av dess index 0.
Exempel:
Input: arr[] = {0 1 2 3 4 5 6 7}
Produktion: arr[] = {0 2 4 6 7 5 3 1}
Förklaring:
Element på jämna ställen: 0 2 4 6
Element på udda plats: 1 3 5 7
Jämnt placerade element i ökande ordning:
0 2 4 6
Udda-Placera element i fallande ordning:
7 5 3 1
Input: arr[] = {3 1 2 4 5 9 13 14 12}
Produktion: {2 3 5 12 13 14 9 4 1}
Förklaring:
Element på jämna ställen: 3 2 5 13 12
Element på udda plats: 1 4 9 14
Jämnt placerade element i ökande ordning:
2 3 5 12 13
Udda-Placera element i fallande ordning:
14 9 4 1
[Naiv tillvägagångssätt] - O(n Log n) Tid och O(n) Space
Tanken är enkel. Vi skapar två hjälparrayer evenArr[] respektive oddArr[]. Vi går igenom inmatningsmatrisen och lägger alla jämnt placerade element i evenArr[] och udda placerade element i oddArr[]. Sedan sorterar vi evenArr[] i stigande och oddArr[] i fallande ordning. Kopiera slutligen evenArr[] och oddArr[] för att få önskat resultat.
C++ // Program to separately sort even-placed and odd // placed numbers and place them together in sorted // array. #include using namespace std ; void bitonicGenerator ( vector < int >& arr ) { // create evenArr[] and oddArr[] vector < int > evenArr ; vector < int > oddArr ; // Put elements in oddArr[] and evenArr[] as // per their position for ( int i = 0 ; i < arr . size (); i ++ ) { if ( ! ( i % 2 )) evenArr . push_back ( arr [ i ]); else oddArr . push_back ( arr [ i ]); } // sort evenArr[] in ascending order // sort oddArr[] in descending order sort ( evenArr . begin () evenArr . end ()); sort ( oddArr . begin () oddArr . end () greater < int > ()); int i = 0 ; for ( int j = 0 ; j < evenArr . size (); j ++ ) arr [ i ++ ] = evenArr [ j ]; for ( int j = 0 ; j < oddArr . size (); j ++ ) arr [ i ++ ] = oddArr [ j ]; } // Driver Program int main () { vector < int > arr = { 1 5 8 9 6 7 3 4 2 0 }; bitonicGenerator ( arr ); for ( int i = 0 ; i < arr . size (); i ++ ) cout < < arr [ i ] < < ' ' ; return 0 ; }
Java // Program to separately sort even-placed and odd // placed numbers and place them together in sorted // array. import java.util.* ; public class Main { public static void bitonicGenerator ( int [] arr ) { // create evenArr[] and oddArr[] List < Integer > evenArr = new ArrayList <> (); List < Integer > oddArr = new ArrayList <> (); // Put elements in oddArr[] and evenArr[] as // per their position for ( int i = 0 ; i < arr . length ; i ++ ) { if ( i % 2 == 0 ) evenArr . add ( arr [ i ] ); else oddArr . add ( arr [ i ] ); } // sort evenArr[] in ascending order // sort oddArr[] in descending order Collections . sort ( evenArr ); Collections . sort ( oddArr Collections . reverseOrder ()); int i = 0 ; for ( int num : evenArr ) arr [ i ++] = num ; for ( int num : oddArr ) arr [ i ++] = num ; } public static void main ( String [] args ) { int [] arr = { 1 5 8 9 6 7 3 4 2 0 }; bitonicGenerator ( arr ); for ( int num : arr ) System . out . print ( num + ' ' ); } }
Python # Program to separately sort even-placed and odd # placed numbers and place them together in sorted # array. def bitonic_generator ( arr ): # create evenArr[] and oddArr[] evenArr = [] oddArr = [] # Put elements in oddArr[] and evenArr[] as # per their position for i in range ( len ( arr )): if i % 2 == 0 : evenArr . append ( arr [ i ]) else : oddArr . append ( arr [ i ]) # sort evenArr[] in ascending order # sort oddArr[] in descending order evenArr . sort () oddArr . sort ( reverse = True ) i = 0 for num in evenArr : arr [ i ] = num i += 1 for num in oddArr : arr [ i ] = num i += 1 # Driver Program arr = [ 1 5 8 9 6 7 3 4 2 0 ] bitonic_generator ( arr ) print ( ' ' . join ( map ( str arr )))
C# // Program to separately sort even-placed and odd // placed numbers and place them together in sorted // array. using System ; using System.Collections.Generic ; using System.Linq ; class Program { static void BitonicGenerator ( int [] arr ) { // create evenArr[] and oddArr[] List < int > evenArr = new List < int > (); List < int > oddArr = new List < int > (); // Put elements in oddArr[] and evenArr[] as // per their position for ( int i = 0 ; i < arr . Length ; i ++ ) { if ( i % 2 == 0 ) evenArr . Add ( arr [ i ]); else oddArr . Add ( arr [ i ]); } // sort evenArr[] in ascending order // sort oddArr[] in descending order evenArr . Sort (); oddArr . Sort (( a b ) => b . CompareTo ( a )); int index = 0 ; foreach ( var num in evenArr ) arr [ index ++ ] = num ; foreach ( var num in oddArr ) arr [ index ++ ] = num ; } static void Main () { int [] arr = { 1 5 8 9 6 7 3 4 2 0 }; BitonicGenerator ( arr ); Console . WriteLine ( string . Join ( ' ' arr )); } }
JavaScript // Program to separately sort even-placed and odd // placed numbers and place them together in sorted // array. function bitonicGenerator ( arr ) { // create evenArr[] and oddArr[] const evenArr = []; const oddArr = []; // Put elements in oddArr[] and evenArr[] as // per their position for ( let i = 0 ; i < arr . length ; i ++ ) { if ( i % 2 === 0 ) evenArr . push ( arr [ i ]); else oddArr . push ( arr [ i ]); } // sort evenArr[] in ascending order // sort oddArr[] in descending order evenArr . sort (( a b ) => a - b ); oddArr . sort (( a b ) => b - a ); let i = 0 ; for ( const num of evenArr ) arr [ i ++ ] = num ; for ( const num of oddArr ) arr [ i ++ ] = num ; } // Driver Program const arr = [ 1 5 8 9 6 7 3 4 2 0 ]; bitonicGenerator ( arr ); console . log ( arr . join ( ' ' ));
PHP // Program to separately sort even-placed and odd // placed numbers and place them together in sorted // array. function bitonicGenerator(&$arr) { // create evenArr[] and oddArr[] $evenArr = []; $oddArr = []; // Put elements in oddArr[] and evenArr[] as // per their position foreach ($arr as $i => $value) { if ($i % 2 === 0) $evenArr[] = $value; else $oddArr[] = $value; } // sort evenArr[] in ascending order // sort oddArr[] in descending order sort($evenArr); rsort($oddArr); $i = 0; foreach ($evenArr as $num) { $arr[$i++] = $num; } foreach ($oddArr as $num) { $arr[$i++] = $num; } } // Driver Program $arr = [1 5 8 9 6 7 3 4 2 0]; bitonicGenerator($arr); echo implode(' ' $arr);
Produktion
1 2 3 6 8 9 7 5 4 0
[Förväntad tillvägagångssätt - 1] - O(n Log n) Tid och O(1) Mellanrum
Problemet kan också lösas utan användning av extra utrymme. Tanken är att byta den första halvan udda indexpositioner med den andra halvan jämna indexpositioner och sedan sortera den första halvan i ökande ordning och den andra halvan i fallande ordning.
C++ #include using namespace std ; void bitonicGenerator ( vector < int >& arr ) { // first odd index int i = 1 ; // last index int n = arr . size (); int j = n - 1 ; // if last index is odd if ( j % 2 != 0 ) // decrement j to even index j -- ; // swapping till half of array while ( i < j ) { swap ( arr [ i ] arr [ j ]); i += 2 ; j -= 2 ; } // Sort first half in increasing sort ( arr . begin () arr . begin () + ( n + 1 ) / 2 ); // Sort second half in decreasing sort ( arr . begin () + ( n + 1 ) / 2 arr . end () greater < int > ()); } // Driver Program int main () { vector < int > arr = { 1 5 8 9 6 7 3 4 2 0 }; bitonicGenerator ( arr ); for ( int i = 0 ; i < arr . size (); i ++ ) cout < < arr [ i ] < < ' ' ; return 0 ; }
Java import java.util.Arrays ; class BitonicGenerator { public static void bitonicGenerator ( int [] arr ) { // first odd index int i = 1 ; // last index int n = arr . length ; int j = n - 1 ; // if last index is odd if ( j % 2 != 0 ) // decrement j to even index j -- ; // swapping till half of array while ( i < j ) { int temp = arr [ i ] ; arr [ i ] = arr [ j ] ; arr [ j ] = temp ; i += 2 ; j -= 2 ; } // Sort first half in increasing order Arrays . sort ( arr 0 ( n + 1 ) / 2 ); // Sort second half in decreasing order Arrays . sort ( arr ( n + 1 ) / 2 n ); reverse ( arr ( n + 1 ) / 2 n ); } private static void reverse ( int [] arr int start int end ) { end -- ; while ( start < end ) { int temp = arr [ start ] ; arr [ start ] = arr [ end ] ; arr [ end ] = temp ; start ++ ; end -- ; } } // Driver Program public static void main ( String [] args ) { int [] arr = { 1 5 8 9 6 7 3 4 2 0 }; bitonicGenerator ( arr ); for ( int num : arr ) { System . out . print ( num + ' ' ); } } }
Python def bitonic_generator ( arr ): # first odd index i = 1 # last index n = len ( arr ) j = n - 1 # if last index is odd if j % 2 != 0 : # decrement j to even index j -= 1 # swapping till half of array while i < j : arr [ i ] arr [ j ] = arr [ j ] arr [ i ] i += 2 j -= 2 # Sort first half in increasing arr [:( n + 1 ) // 2 ] = sorted ( arr [:( n + 1 ) // 2 ]) # Sort second half in decreasing arr [( n + 1 ) // 2 :] = sorted ( arr [( n + 1 ) // 2 :] reverse = True ) # Driver Program arr = [ 1 5 8 9 6 7 3 4 2 0 ] bitonic_generator ( arr ) print ( ' ' . join ( map ( str arr )))
C# // Function to generate a bitonic sequence using System ; using System.Collections.Generic ; using System.Linq ; class Program { static void BitonicGenerator ( List < int > arr ) { // first odd index int i = 1 ; // last index int n = arr . Count ; int j = n - 1 ; // if last index is odd if ( j % 2 != 0 ) // decrement j to even index j -- ; // swapping till half of array while ( i < j ) { int temp = arr [ i ]; arr [ i ] = arr [ j ]; arr [ j ] = temp ; i += 2 ; j -= 2 ; } // Sort first half in increasing arr . Sort ( 0 ( n + 1 ) / 2 ); // Sort second half in decreasing arr . Sort (( n + 1 ) / 2 n - ( n + 1 ) / 2 Comparer < int > . Create (( x y ) => y . CompareTo ( x ))); } // Driver Program static void Main () { List < int > arr = new List < int > { 1 5 8 9 6 7 3 4 2 0 }; BitonicGenerator ( arr ); Console . WriteLine ( string . Join ( ' ' arr )); } }
JavaScript // Function to generate a bitonic sequence function bitonicGenerator ( arr ) { // first odd index let i = 1 ; // last index let n = arr . length ; let j = n - 1 ; // if last index is odd if ( j % 2 !== 0 ) // decrement j to even index j -- ; // swapping till half of array while ( i < j ) { [ arr [ i ] arr [ j ]] = [ arr [ j ] arr [ i ]]; i += 2 ; j -= 2 ; } // Sort first half in increasing arr . sort (( a b ) => a - b ); // Sort second half in decreasing arr . slice (( n + 1 ) / 2 ). sort (( a b ) => b - a ); } // Driver Program let arr = [ 1 5 8 9 6 7 3 4 2 0 ]; bitonicGenerator ( arr ); console . log ( arr . join ( ' ' ));
Produktion
1 2 3 6 8 9 7 5 4 0
Obs: Ovanstående Python- och JS-koder verkar kräva extra utrymme. Låt oss veta i kommentarer om dina tankar och eventuella alternativa implementeringar.
[Förväntad tillvägagångssätt - 2] - O(n Log n) Tid och O(1) Mellanrum
En annan effektiv metod för att lösa problemet i O(1) hjälputrymme är genom Använder negativ multiplikation .
De inblandade stegen är följande:
- Multiplicera alla element vid jämnt placerat index med -1.
- Sortera hela arrayen. På så sätt kan vi få alla jämnt placerade index i början då de är negativa tal nu.
- Återställ nu tecknet för dessa element.
- Efter detta vänder den första halvan av arrayen som innehåller ett jämnt placerat nummer för att göra det i ökande ordning.
- Och vänd sedan resten av arrayen för att göra udda placerade nummer i fallande ordning.
Notera: Denna metod är endast tillämplig om alla element i arrayen är icke-negativa.
Ett illustrativt exempel på ovanstående tillvägagångssätt:
Låt given array: arr[] = {0 1 2 3 4 5 6 7}
Array efter multiplicering med -1 till jämna placerade element: arr[] = {0 1 -2 3 -4 5 -6 7}
Array efter sortering: arr[] = {-6 -4 -2 0 1 3 5 7}
Array efter återställning av negativa värden: arr[] = {6 4 2 0 1 3 5 7}
Efter att ha vänt den första halvan av arrayen: arr[] = {0 2 4 6 1 3 5 7}
Efter att ha vänt den andra halvan av arrayen: arr[] = {0 2 4 6 7 5 3 1}
Nedan är koden för ovanstående tillvägagångssätt:
C++ #include using namespace std ; void bitonicGenerator ( vector < int >& arr ) { // Making all even placed index // element negative for ( int i = 0 ; i < arr . size (); i ++ ) { if ( i % 2 == 0 ) arr [ i ] = -1 * arr [ i ]; } // Sorting the whole array sort ( arr . begin () arr . end ()); // Finding the middle value of // the array int mid = ( arr . size () - 1 ) / 2 ; // Reverting the changed sign for ( int i = 0 ; i <= mid ; i ++ ) { arr [ i ] = -1 * arr [ i ]; } // Reverse first half of array reverse ( arr . begin () arr . begin () + mid + 1 ); // Reverse second half of array reverse ( arr . begin () + mid + 1 arr . end ()); } // Driver Program int main () { vector < int > arr = { 1 5 8 9 6 7 3 4 2 0 }; bitonicGenerator ( arr ); for ( int i = 0 ; i < arr . size (); i ++ ) cout < < arr [ i ] < < ' ' ; return 0 ; }
Java import java.util.Arrays ; import java.util.List ; public class BitonicGenerator { public static void bitonicGenerator ( List < Integer > arr ) { // Making all even placed index // element negative for ( int i = 0 ; i < arr . size (); i ++ ) { if ( i % 2 == 0 ) arr . set ( i - 1 * arr . get ( i )); } // Sorting the whole array Collections . sort ( arr ); // Finding the middle value of // the array int mid = ( arr . size () - 1 ) / 2 ; // Reverting the changed sign for ( int i = 0 ; i <= mid ; i ++ ) { arr . set ( i - 1 * arr . get ( i )); } // Reverse first half of array Collections . reverse ( arr . subList ( 0 mid + 1 )); // Reverse second half of array Collections . reverse ( arr . subList ( mid + 1 arr . size ())); } // Driver Program public static void main ( String [] args ) { List < Integer > arr = Arrays . asList ( 1 5 8 9 6 7 3 4 2 0 ); bitonicGenerator ( arr ); for ( int i : arr ) System . out . print ( i + ' ' ); } }
Python def bitonic_generator ( arr ): # Making all even placed index # element negative for i in range ( len ( arr )): if i % 2 == 0 : arr [ i ] = - 1 * arr [ i ] # Sorting the whole array arr . sort () # Finding the middle value of # the array mid = ( len ( arr ) - 1 ) // 2 # Reverting the changed sign for i in range ( mid + 1 ): arr [ i ] = - 1 * arr [ i ] # Reverse first half of array arr [: mid + 1 ] = reversed ( arr [: mid + 1 ]) # Reverse second half of array arr [ mid + 1 :] = reversed ( arr [ mid + 1 :]) # Driver Program arr = [ 1 5 8 9 6 7 3 4 2 0 ] bitonic_generator ( arr ) print ( ' ' . join ( map ( str arr )))
C# using System ; using System.Collections.Generic ; using System.Linq ; class BitonicGenerator { public static void BitonicGeneratorMethod ( List < int > arr ) { // Making all even placed index // element negative for ( int i = 0 ; i < arr . Count ; i ++ ) { if ( i % 2 == 0 ) arr [ i ] = - 1 * arr [ i ]; } // Sorting the whole array arr . Sort (); // Finding the middle value of // the array int mid = ( arr . Count - 1 ) / 2 ; // Reverting the changed sign for ( int i = 0 ; i <= mid ; i ++ ) { arr [ i ] = - 1 * arr [ i ]; } // Reverse first half of array arr . Take ( mid + 1 ). Reverse (). ToList (). CopyTo ( arr ); // Reverse second half of array arr . Skip ( mid + 1 ). Reverse (). ToList (). CopyTo ( arr mid + 1 ); } // Driver Program public static void Main () { List < int > arr = new List < int > { 1 5 8 9 6 7 3 4 2 0 }; BitonicGeneratorMethod ( arr ); Console . WriteLine ( string . Join ( ' ' arr )); } }
JavaScript function bitonicGenerator ( arr ) { // Making all even placed index // element negative for ( let i = 0 ; i < arr . length ; i ++ ) { if ( i % 2 === 0 ) arr [ i ] = - 1 * arr [ i ]; } // Sorting the whole array arr . sort (( a b ) => a - b ); // Finding the middle value of // the array const mid = Math . floor (( arr . length - 1 ) / 2 ); // Reverting the changed sign for ( let i = 0 ; i <= mid ; i ++ ) { arr [ i ] = - 1 * arr [ i ]; } // Reverse first half of array arr . slice ( 0 mid + 1 ). reverse (). forEach (( val index ) => arr [ index ] = val ); // Reverse second half of array arr . slice ( mid + 1 ). reverse (). forEach (( val index ) => arr [ mid + 1 + index ] = val ); } // Driver Program let arr = [ 1 5 8 9 6 7 3 4 2 0 ]; bitonicGenerator ( arr ); console . log ( arr . join ( ' ' ));
Produktion
1 2 3 6 8 9 7 5 4 0
Skapa frågesport
