Given an integer array a[o..n-1], please design an algorithm to output all the a

Question

Given an integer array a[o..n-1], please design an algorithm to output all the a[i] which satisfy: all the elements from a[0] to a[i] are larger than or equal to a[i], and all the elements from a[i] to a[n-1] are less than or equal to a[i] For example: a [0.4] = {32, 22, 19, 6, 10}; then output: 32, 22, 19 Assuming there are n elements in the integer array. Now the time complexity and space complexity of your algorithm are both restricted to o(n). Please design and implement an algorithm to solve this problem. Explain your idea first, and implement it using pseudocode Now we will see how prior knowledge about data distribution can allow us to achieve a faster sorting algorithm. Assume for the given integer array a[o..n-1], all the integers a[i], 0 lessthanorequalto I lessthanorequalto n-1, are in the range [0..99]. Please design and implement a sorting algorithm to sort the integer array, whose time complexity is restricted to 0(n) Explain your idea first, and implement it either using Java, C/C++ code or pseudocode.

Explanation / Answer

1. Take two array of same length n, left and right. If original array is a[0..n-1],
   then left[i] means smallest element among a[0] to a[i-1], +Infinity for the leftmost element
   and right[i] means greatest element among a[i+1] to a[n-1], -1 for the right most element

   Now for whichever element in a[i], a[i] < left[i] and a[i] > right[i], that is the solution element.

So for example,

for result, We will traverse the original array from right to left, and check which element satisfies the condition of A[i] <= Left[i] and a[i] >= right[i]. We can see that i=4, means a[i] = 7 satisfies the condition. All the elements to the left are greater than this and to the right are lesser than this.



2. As the elements are for sure in the range of 0..99, we will take an array of count[100] for 100 elements in range of 0-99 inclusive(All counts initialised from 0). We will traverse the original array a[0..n-1] and whatever element we get, we will increase the count for that in the count array. Like if a[i] = 4, we will increaese the count[4] element by 1. In this way, once we are done traversing the original array, we can traverse the count array and print iTh element count[i] times. Like if count[0] = 5, means, we encouter 5 zeroes in the original array. hence print them in the result for 5 times.. If count[i] = 0, means ith elment was not part of the original array, hence we will not print the ith element in result. This is known as count sort.

// Java implementation of Counting Sort
class CountingSort
{
   void sort(int numbers[])
   {
       int n = numbers.length;

       // Create a count array to store count of inidividual
       // numbers and initialize count array as 0
       int count[] = new int[100];
       for (int i=0; i<100; ++i)
           count[i] = 0;

       // store count of each number
       for (int i=0; i<n; ++i)
           ++count[numbers[i]];

       System.out.print("Sorted number array is ");
       for (int i = 0; i<100; ++i)
       {
       for(int j=0; j < count[i]; j++) {
       System.out.print(i + " ");
       }
       }
   }

   // Driver method
   public static void main(String args[])
   {
       CountingSort ob = new CountingSort();
       int arr[] = {2, 4,6, 7, 3,4, 2, 1, 0, 56, 43, 5, 43};

       ob.sort(arr);
   }
}

Sample Output:

i 0 1 2 3 4 5 6 A 12 15 13 10 7 4 6 Left +Infinity 12 12 12 10 7 4 Right 15 13 10 7 6 6 -1

Related Questions

Navigate

• Browse (All)
• Browse G
• Subjects

---

---

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