problems on algorithms for Miscellaneous, sorting, Show that n positive interger

Question

problems on algorithms for Miscellaneous, sorting,

Show that n positive intergers in the range 1 to k can be sorted in timeO(n log k)

13.1 SORTING AND ORDER STATISTICS This section contains questions on sorting and order statistics (the latter is a fancy name for "find the k smallest element"). These are mainly upper bounds. Problems on lower bounds are mostly (but not exclusively) found in Section 13.2. er bounds are mostly (but not exclhusively) found in Section 13.2 607. Show that n positive integers in the range 1 to k can be sorted in time

Explanation / Answer

In sorting n positive integers in the range 1 to k can be sorted in o(n log n) using the Mergesort/HeapSort/QuickSort.

i am using merge sort to show the above statement in java

//merge sort program takes o(nlogn) time to sort the given n elements.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

//
public class MergeSort {
  
           public static void main(String[] args) throws IOException{
               int n;
              
               System.out.println(" enter array size:");
              
               BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
               n=Integer.parseInt(br.readLine());
              
               if(n==0) n=10;
          
               Integer a[] = new Integer[n];
               Integer b[]=new Integer[n]; //b is temparary array.
          
               System.out.println(" enter array elements to sort:");
               for(int i=0;i<n;i++)
               a[i]=Integer.parseInt(br.readLine()); //getting the values from keyboard.
      
               //printing the array values prior to sort
               System.out.println("Before Merge Sort: ");
               System.out.println(Arrays.toString(a));
                      
               //printing the array values after mergesort
               mergeSort(a,b,0,a.length-1);
               System.out.println("After Merge Sort: ");
               System.out.println(Arrays.toString(a));
       }

      

       private static void mergeSort(Integer[] a,Integer[ ] tmp, int left, int right){
           if( left < right ){
               int center = (left + right) / 2;
               mergeSort(a, tmp, left, center);//doing the mergesort for first half
               mergeSort(a, tmp, center + 1, right);//doing the mergesort for second half
               merge(a, tmp, left, center + 1, right);//merging the first and second half
           }
       }

   private static void merge(Integer[ ] a,Integer[ ] tmp, int left, int right, int rEnd ){
   int lEnd = right - 1;
   int k = left;
   int num = rEnd - left + 1;

   while(left <= lEnd && right <= rEnd){
   if(a[left].compareTo(a[right]) <= 0)// comparing the both first and second half.
   tmp[k++] = a[left++];
   else
   tmp[k++] = a[right++];
   }
   while(left <= lEnd) // Copying the rest of first half in a to tmp
   tmp[k++] = a[left++];

   while(right <= rEnd) // Copying the rest of second half in a into tmp
   tmp[k++] = a[right++];

   // Copying the remaining tmp values into a
   for(int i = 0; i < num; i++, rEnd--)
   a[rEnd] = tmp[rEnd];
   }
   }

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.