logo

TechCodeview

Sorter partallsplassert i økende og oddetallsplassert i synkende rekkefølge

Vi får en matrise med n distinkte tall. Oppgaven er å sortere alle partallsplasserte tall i økende og oddetall i synkende rekkefølge. Den modifiserte matrisen skal inneholde alle sorterte partallsplasserte tall etterfulgt av omvendt sorterte oddetall.

10 av 40

Merk at det første elementet anses som jevnt plassert på grunn av indeksen 0. 

Eksempler:   



Inndata: arr[] = {0 1 2 3 4 5 6 7}
Produksjon: arr[] = {0 2 4 6 7 5 3 1}
Forklaring:
Elementer på jevn plass: 0 2 4 6
Elementer med oddetall: 1 3 5 7
Elementer med jevn plass i økende rekkefølge:
0 2 4 6
Odd-Placer elementer i synkende rekkefølge:
7 5 3 1

Inndata: arr[] = {3 1 2 4 5 9 13 14 12}
Produksjon: {2 3 5 12 13 14 9 4 1}
Forklaring:
Elementer på jevn plass: 3 2 5 13 12
Elementer på oddetall: 1 4 9 14
Elementer med jevn plass i økende rekkefølge:
2 3 5 12 13
Odd-Placer elementer i synkende rekkefølge:
14 9 4 1

[Naiv tilnærming] - O(n Logg n) Tid og O(n) Mellomrom

Tanken er enkel. Vi lager to hjelpearrayer, evenArr[] og oddArr[]. Vi krysser input-array og legger alle partallsplasserte elementer i evenArr[] og oddetallsplasserte elementer i oddArr[]. Deretter sorterer vi evenArr[] i stigende og oddArr[] i synkende rekkefølge. Kopier til slutt evenArr[] og oddArr[] for å få det nødvendige resultatet.

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);

Produksjon 
1 2 3 6 8 9 7 5 4 0

[Forventet tilnærming - 1] - O(n Logg n) Tid og O(1) Mellomrom

Problemet kan også løses uten bruk av hjelpeplass. Ideen er å bytte den første halvdelens odde indeksposisjoner med den andre halvdelens jevne indeksposisjoner og deretter sortere den første halvdelen i økende rekkefølge og den andre halvdelen i synkende rekkefølge.

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(' '));

Produksjon 
1 2 3 6 8 9 7 5 4 0

Merk: Python- og JS-kodene ovenfor ser ut til å kreve ekstra plass. Gi oss beskjed i kommentarer om dine tanker og eventuelle alternative implementeringer.

[Forventet tilnærming - 2] - O(n Logg n) Tid og O(1) Mellomrom

En annen effektiv tilnærming for å løse problemet i O(1) hjelperom er ved Bruker negativ multiplikasjon .

Trinnene som er involvert er som følger:

  1.  Multipliser alle elementene ved jevn plassert indeks med -1.
  2. Sorter hele matrisen. På denne måten kan vi få alle jevne plasserte indekser i starten da de er negative tall nå.
  3. Vend tilbake tegnet til disse elementene.
  4. Etter dette reverserer den første halvdelen av matrisen som inneholder et partall plassert tall for å gjøre det i økende rekkefølge.
  5. Og reverser deretter resten av matrisen for å lage oddetallsplasserte tall i synkende rekkefølge.

Note: Denne metoden er bare aktuelt hvis alle elementene i matrisen er ikke-negative.

Et illustrerende eksempel på tilnærmingen ovenfor:

La gitt array: arr[] = {0 1 2 3 4 5 6 7}
Array etter å ha multiplisert med -1 til jevnt plasserte elementer: arr[] = {0 1 -2 3 -4 5 -6 7}
Matrise etter sortering: arr[] = {-6 -4 -2 0 1 3 5 7}
Matrise etter tilbakestilling av negative verdier: arr[] = {6 4 2 0 1 3 5 7}
Etter å ha reversert den første halvdelen av matrisen: arr[] = {0 2 4 6 1 3 5 7}
Etter å ha reversert andre halvdel av matrisen: arr[] = {0 2 4 6 7 5 3 1}

Nedenfor er koden for tilnærmingen ovenfor:

feil: kunne ikke finne eller laste inn hovedklassen
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(' '));

Produksjon 
1 2 3 6 8 9 7 5 4 0

 

Lag quiz