Çift yerleşimli olarak artan, tek yerleşimli olarak azalan düzende sırala
Bize n farklı sayıdan oluşan bir dizi veriliyor. Görev, tüm çift yerleştirilmiş sayıları artan düzende ve tek yerleştirilmiş sayıları azalan düzende sıralamaktır. Değiştirilen dizi tüm sıralanmış çift sıralı sayıları ve ardından ters sıralanmış tek sıralı sayıları içermelidir.
İlk elemanın indeksi 0 olduğundan çift yerleştirilmiş olarak kabul edildiğini unutmayın.
Örnekler:
Giriş: dizi[] = {0 1 2 3 4 5 6 7}
Çıkış: dizi[] = {0 2 4 6 7 5 3 1}
Açıklama:
Eşit yerleştirme elemanları : 0 2 4 6
Tek yer elemanları : 1 3 5 7
Artan düzende eşit yerleştirme elemanları:
0 2 4 6
Tek Yerleştirme öğeleri azalan sırada:
7 5 3 1
Giriş: dizi[] = {3 1 2 4 5 9 13 14 12}
Çıkış: {2 3 5 12 13 14 9 4 1}
Açıklama:
Eşit yerleştirme elemanları : 3 2 5 13 12
Tek yer elemanları : 1 4 9 14
Artan düzende eşit yerleştirme elemanları:
2 3 5 12 13
Tek Yerleştirme öğeleri azalan sırada:
14 9 4 1
[Naif Yaklaşım] - O(n Log n) Zaman ve O(n) Uzay
Fikir basit. Sırasıyla evenArr[] ve oddArr[] olmak üzere iki yardımcı dizi oluşturuyoruz. Giriş dizisini geçiyoruz ve tüm çift yerleştirilmiş elemanları evenArr[]'a ve tek yerleştirilmiş elemanları oddArr[]'a koyuyoruz. Daha sonra evenArr[]'ı artan şekilde ve oddArr[]'ı azalan şekilde sıralarız. Son olarak gerekli sonucu elde etmek için evenArr[] ve oddArr[]'ı kopyalayın.
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);
Çıkış
1 2 3 6 8 9 7 5 4 0
[Beklenen Yaklaşım - 1] - O(n Log n) Zaman ve O(1) Uzay
Sorun, Yardımcı alan kullanılmadan da çözülebilir. Buradaki fikir, ilk yarı tek dizin konumlarını ikinci yarı çift dizin konumlarıyla değiştirmek ve ardından ilk yarı dizisini artan sırada ve ikinci yarı dizisini azalan sırada sıralamaktır.
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 ( ' ' ));
Çıkış
1 2 3 6 8 9 7 5 4 0
Not: Yukarıdaki Python ve JS kodları ekstra alan gerektiriyor gibi görünüyor. Düşünceleriniz ve alternatif uygulamalar hakkındaki yorumlarınızı bize bildirin.
[Beklenen Yaklaşım - 2] - O(n Log n) Zaman ve O(1) Uzay
O(1) yardımcı uzayındaki problemi çözmek için bir başka etkili yaklaşım da şudur: Negatif çarpmayı kullanma .
İlgili adımlar aşağıdaki gibidir:
- Eşit yerleştirilmiş indeksteki tüm elemanları -1 ile çarpın.
- Tüm diziyi sıralayın. Bu şekilde, artık negatif sayılar oldukları için başlangıçta tüm çift yerleştirilmiş indeksleri alabiliriz.
- Şimdi bu elemanların işaretini tersine çevirin.
- Bundan sonra, artan sırada yapmak için çift yerleştirilmiş bir sayı içeren dizinin ilk yarısını ters çevirin.
- Daha sonra azalan sırada tek yerleştirilmiş sayılar oluşturmak için dizinin geri kalan yarısını ters çevirin.
Not: Bu yöntem yalnızca dizideki tüm öğelerin negatif olmaması durumunda uygulanabilir.
Yukarıdaki yaklaşımın açıklayıcı bir örneği:
Verilen diziye izin verin: dizi[] = {0 1 2 3 4 5 6 7}
Eşit yerleştirilmiş öğelere -1 ile çarpıldıktan sonra dizi: dizi[] = {0 1 -2 3 -4 5 -6 7}
Sıralamadan sonraki dizi: arr[] = {-6 -4 -2 0 1 3 5 7}
Negatif değerleri geri döndürdükten sonraki dizi: arr[] = {6 4 2 0 1 3 5 7}
Dizinin ilk yarısını tersine çevirdikten sonra: arr[] = {0 2 4 6 1 3 5 7}
Dizinin ikinci yarısını tersine çevirdikten sonra: arr[] = {0 2 4 6 7 5 3 1}
Yukarıdaki yaklaşımın kodu aşağıdadır:
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 ( ' ' ));
Çıkış
1 2 3 6 8 9 7 5 4 0
Test Oluştur
