logo

TechCodeview

Sorter lige-placeret i stigende og ulige-placeret i faldende rækkefølge

Vi får en matrix af n distinkte tal. Opgaven er at sortere alle lige-placerede tal i stigende og ulige-placerede tal i faldende rækkefølge. Den ændrede matrix skal indeholde alle sorterede lige-placerede tal efterfulgt af omvendt sorterede ulige-placerede tal.

mb vs gb

Bemærk, at det første element anses for at være lige placeret på grund af dets indeks 0. 

Eksempler:   



Input: arr[] = {0 1 2 3 4 5 6 7}
Produktion: arr[] = {0 2 4 6 7 5 3 1}
Forklaring:
Elementer på lige plads: 0 2 4 6
Elementer med ulige steder: 1 3 5 7
Lige-placerede elementer i stigende rækkefølge:
0 2 4 6
Ulige-Placer elementer i faldende rækkefølge:
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}
Forklaring:
Elementer på lige plads: 3 2 5 13 12
Elementer med ulige steder: 1 4 9 14
Lige-placerede elementer i stigende rækkefølge:
2 3 5 12 13
Ulige-Placer elementer i faldende rækkefølge:
14 9 4 1

[Naiv tilgang] - O(n Log n) Tid og O(n) Rum

Ideen er enkel. Vi opretter to hjælpearrays, evenArr[] og oddArr[]. Vi krydser input-array og sætter alle lige-placerede elementer i evenArr[] og ulige placerede elementer i oddArr[]. Så sorterer vi ligeArr[] i stigende og uligeArr[] i faldende rækkefølge. Kopier til sidst evenArr[] og oddArr[] for at få det ønskede 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

[Forventet tilgang - 1] - O(n Log n) Tid og O(1) Rum

Problemet kan også løses uden brug af hjælpeplads. Ideen er at bytte den første halvdels ulige indekspositioner med den anden halvdel lige indekspositioner og derefter sortere den første halve matrix i stigende rækkefølge og den anden halve matrix i faldende rækkefø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(' '));

Produktion 
1 2 3 6 8 9 7 5 4 0

Bemærk: Ovenstående Python- og JS-koder ser ud til at kræve ekstra plads. Fortæl os i kommentarer om dine tanker og eventuelle alternative implementeringer.

[Forventet tilgang - 2] - O(n Log n) Tid og O(1) Rum

En anden effektiv tilgang til at løse problemet i O(1) hjælperum er ved Brug af negativ multiplikation .

De involverede trin er som følger:

  1.  Multiplicer alle elementerne ved lige placeret indeks med -1.
  2. Sorter hele arrayet. På denne måde kan vi få alle lige placeret indeks i starten, da de er negative tal nu.
  3. Vend nu fortegnet af disse elementer tilbage.
  4. Efter dette vendes den første halvdel af arrayet, som indeholder et lige placeret tal, for at gøre det i stigende rækkefølge.
  5. Og vend derefter den resterende halvdel af arrayet for at lave ulige placerede tal i faldende rækkefølge.

Note: Denne metode er kun anvendelig, hvis alle elementer i arrayet er ikke-negative.

Et illustrativt eksempel på ovenstående fremgangsmåde:

Lad givet array: arr[] = {0 1 2 3 4 5 6 7}
Array efter at have ganget med -1 til lige placerede elementer: arr[] = {0 1 -2 3 -4 5 -6 7}
Array efter sortering: arr[] = {-6 -4 -2 0 1 3 5 7}
Array efter tilbageførsel af negative værdier: arr[] = {6 4 2 0 1 3 5 7}
Efter at have vendt den første halvdel af arrayet: arr[] = {0 2 4 6 1 3 5 7}
Efter at have vendt den anden halvdel af arrayet: arr[] = {0 2 4 6 7 5 3 1}

Nedenfor er koden for ovenstående tilgang:

fejl: kunne ikke finde eller indlæse 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(' '));

Produktion 
1 2 3 6 8 9 7 5 4 0

 

Opret Quiz