POZIȚIA UNUI ELEMENT DUPĂ SORTAREA STABILĂ

Încercați-l pe GfG Practice

#practiceLinkDiv { display: none !important; }

Având în vedere o matrice de numere întregi care pot conține elemente duplicate, un element din această matrice ne este dat, trebuie să spunem poziția finală a acestui element în matrice dacă este aplicat un algoritm de sortare stabil.

Exemple:

Input : arr[] = [3 4 3 5 2 3 4 3 1 5] index = 5 Output : 4 Element initial index – 5 (third 3) After sorting array by stable sorting algorithm we get array as shown below [1(8) 2(4) 3(0) 3(2) 3(5) 3(7) 4(1) 4(6) 5(3) 5(9)] with their initial indices shown in parentheses next to them Element's index after sorting = 4

Recommended Practice Sortare și poziție stabilă Încearcă!

O modalitate ușoară de a rezolva această problemă este să utilizați orice algoritm de sortare stabil, cum ar fi Sortare prin inserare Merge Sort etc și apoi obțineți noul index al elementului dat, dar putem rezolva această problemă fără a sorta matricea.

Deoarece poziția unui element într-o matrice sortată este decisă doar de acele elemente care sunt mai mici decât elementul dat. Numărăm toate elementele matricei mai mici decât elementul dat și pentru acele elemente care sunt egale cu elementele elementului dat care apar înainte ca indicele elementelor date vor fi incluse în numărarea elementelor mai mici, acest lucru va asigura stabilitatea indexului rezultatului.

Codul simplu de implementat abordarea de mai sus este implementată mai jos:

C++

    // C++ program to get index of array element in    // sorted array    #include             using     namespace     std  ;      // Method returns the position of arr[idx] after    // performing stable-sort on array    int     getIndexInSortedArray  (  int     arr  []     int     n       int     idx  )      {         /* Count of elements smaller than current     element plus the equal element occurring     before given index*/      int     result     =     0  ;         for     (  int     i     =     0  ;     i      <     n  ;     i  ++  )     {         // If element is smaller then increase       // the smaller count       if     (  arr  [  i  ]      <     arr  [  idx  ])         result  ++  ;         // If element is equal then increase count       // only if it occurs before       if     (  arr  [  i  ]     ==     arr  [  idx  ]     &&     i      <     idx  )         result  ++  ;         }         return     result  ;      }      // Driver code to test above methods    int     main  ()      {         int     arr  []     =     {     3       4       3       5       2       3       4       3       1       5     };         int     n     =     sizeof  (  arr  )     /     sizeof  (  arr  [  0  ]);         int     idxOfEle     =     5  ;         cout      < <     getIndexInSortedArray  (  arr       n       idxOfEle  );         return     0  ;      }

Java

    // Java program to get index of array   // element in sorted array   class   ArrayIndex     {      // Method returns the position of      // arr[idx] after performing stable-sort      // on array      static     int     getIndexInSortedArray  (  int     arr  []        int     n       int     idx  )      {      /* Count of elements smaller than     current element plus the equal element    occurring before given index*/      int     result     =     0  ;      for     (  int     i     =     0  ;     i      <     n  ;     i  ++  )     {      // If element is smaller then      // increase the smaller count      if     (  arr  [  i  ]      <     arr  [  idx  ]  )      result  ++  ;      // If element is equal then increase      // count only if it occurs before      if     (  arr  [  i  ]     ==     arr  [  idx  ]     &&     i      <     idx  )      result  ++  ;      }      return     result  ;      }      // Driver code to test above methods      public     static     void     main  (  String  []     args  )      {      int     arr  []     =     {     3       4       3       5       2       3       4       3       1       5     };      int     n     =     arr  .  length  ;      int     idxOfEle     =     5  ;      System  .  out  .  println  (  getIndexInSortedArray  (  arr        n       idxOfEle  ));      }   }   // This code is contributed by Raghav sharma

Python3

    # Python program to get index of array element in   # sorted array   # Method returns the position of arr[idx] after   # performing stable-sort on array   def   getIndexInSortedArray  (  arr     n     idx  ):   # Count of elements smaller than current   # element plus the equal element occurring   # before given index   result   =   0   for   i   in   range  (  n  ):   # If element is smaller then increase   # the smaller count   if   (  arr  [  i  ]    <   arr  [  idx  ]):   result   +=   1   # If element is equal then increase count   # only if it occurs before   if   (  arr  [  i  ]   ==   arr  [  idx  ]   and   i    <   idx  ):   result   +=   1   return   result  ;   # Driver code to test above methods   arr   =   [  3     4     3     5     2     3     4     3     1     5  ]   n   =   len  (  arr  )   idxOfEle   =   5   print   (  getIndexInSortedArray  (  arr     n     idxOfEle  ))   # Contributed by: Afzal Ansari

    // C# program to get index of array   // element in sorted array   using     System  ;   class     ArrayIndex     {          // Method returns the position of      // arr[idx] after performing stable-sort      // on array      static     int     getIndexInSortedArray  (  int  []     arr        int     n       int     idx  )      {      /* Count of elements smaller than     current element plus the equal element    occurring before given index*/      int     result     =     0  ;      for     (  int     i     =     0  ;     i      <     n  ;     i  ++  )     {          // If element is smaller then      // increase the smaller count      if     (  arr  [  i  ]      <     arr  [  idx  ])      result  ++  ;      // If element is equal then increase      // count only if it occurs before      if     (  arr  [  i  ]     ==     arr  [  idx  ]     &&     i      <     idx  )      result  ++  ;      }      return     result  ;      }      // Driver code to test above methods      public     static     void     Main  ()      {      int  []     arr     =     {     3       4       3       5       2       3       4       3       1       5     };      int     n     =     arr  .  Length  ;      int     idxOfEle     =     5  ;      Console  .  WriteLine  (  getIndexInSortedArray  (  arr       n           idxOfEle  ));      }   }   // This code is contributed by vt_m

PHP

       // PHP program to get index of   // array element in sorted array   // Method returns the position of    // arr[idx] after performing    // stable-sort on array   function   getIndexInSortedArray  (   $arr     $n     $idx  )   {   /* Count of elements smaller    than current element plus     the equal element occurring    before given index */   $result   =   0  ;   for  (  $i   =   0  ;   $i    <   $n  ;   $i  ++  )   {   // If element is smaller then   // increase the smaller count   if   (  $arr  [  $i  ]    <   $arr  [  $idx  ])   $result  ++  ;   // If element is equal then   // increase count only if    // it occurs before   if   (  $arr  [  $i  ]   ==   $arr  [  $idx  ]   and   $i    <   $idx  )   $result  ++  ;   }   return   $result  ;   }   // Driver Code   $arr   =   array  (  3     4     3     5     2     3     4     3     1     5  );   $n   =  count  (  $arr  );   $idxOfEle   =   5  ;   echo   getIndexInSortedArray  (  $arr     $n     $idxOfEle  );   // This code is contributed by anuj_67.   ?>

JavaScript

     <  script  >   // JavaScript program to get index of array   // element in sorted array      // Method returns the position of      // arr[idx] after performing stable-sort      // on array      function     getIndexInSortedArray  (  arr        n       idx  )      {      /* Count of elements smaller than     current element plus the equal element    occurring before given index*/      let     result     =     0  ;      for     (  let     i     =     0  ;     i      <     n  ;     i  ++  )     {          // If element is smaller then      // increase the smaller count      if     (  arr  [  i  ]      <     arr  [  idx  ])      result  ++  ;          // If element is equal then increase      // count only if it occurs before      if     (  arr  [  i  ]     ==     arr  [  idx  ]     &&     i      <     idx  )      result  ++  ;      }      return     result  ;      }   // Driver Code      let     arr     =     [     3       4       3       5       2       3       4       3       1       5     ];      let     n     =     arr  .  length  ;          let     idxOfEle     =     5  ;      document  .  write  (  getIndexInSortedArray  (  arr        n       idxOfEle  ));       // This code is contributed by code_hunt.     <  /script>