Sort an Array which contain 1 to N values in O ( N ) using Cycle Sort | Java program for the above approach ; Function to print array element ; Traverse the array ; Function to sort the array in O ( N ) ; Traverse the array ; If the current element is at correct position ; Else swap the current element with it 's correct position ; Swap the value of arr [ i ] and arr [ arr [ i ] - 1 ] ; Driver Code ; Function call to sort the array ; Function call to print the array
class Main { public static void printArray ( int arr [ ] , int N ) { for ( int i = 0 ; i < N ; i ++ ) { System . out . print ( arr [ i ] + " ▁ " ) ; } } public static void sortArray ( int arr [ ] , int N ) { for ( int i = 0 ; i < N ; ) { if ( arr [ i ] == i + 1 ) { i ++ ; } else { int temp1 = arr [ i ] ; int temp2 = arr [ arr [ i ] - 1 ] ; arr [ i ] = temp2 ; arr [ temp1 - 1 ] = temp1 ; } } } public static void main ( String [ ] args ) { int arr [ ] = { 2 , 1 , 5 , 3 , 4 } ; int N = arr . length ; sortArray ( arr , N ) ; printArray ( arr , N ) ; } }