Plassering av et element etter stabil sortering
Prøv det på GfG Practice 
#practiceLinkDiv { display: ingen !viktig; }
Produksjon
#practiceLinkDiv { display: ingen !viktig; } Gitt en rekke heltall som kan inneholde dupliserte elementer et element i denne matrisen er gitt til oss, må vi fortelle den endelige posisjonen til dette elementet i matrisen hvis en stabil sorteringsalgoritme brukes.
Eksempler:
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 = 4Recommended Practice Stabil sortering og plassering Prøv det!
En enkel måte å løse dette problemet på er å bruke en hvilken som helst stabil sorteringsalgoritme som Innsettingssortering Sort går etc og få den nye indeksen for gitt element, men vi kan løse dette problemet uten å sortere matrisen.
Posisjonen til et element i en sortert matrise bestemmes kun av de elementene som er mindre enn gitt element. Vi teller alle matriseelementer som er mindre enn gitt element, og for de elementene som er lik gitte elementelementer som forekommer før gitte elementers indeks vil bli inkludert i antallet av mindre elementer, vil dette sikre stabiliteten til resultatets indeks.
Enkel kode for å implementere tilnærmingen ovenfor er implementert nedenfor:
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# // 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>
Produksjon
4
Tidskompleksitet: På) hvor n er størrelsen på matrisen.
Hjelpeområde: O(1)
Lag quiz
