Finding fourth largest & fourth smallest number in an array

Question

I have tried the following method to find second largest & smallest number and it works :

class Test

{

static void main()throws IOException

{
    Scanner sc = new Scanner(System.in);
    System.out.println("Enter");
    int a[] = {45,79,2,5,74,4,19,56,2,888};
    int small= a[0];
    int big=a[0];
    int s=0,b=0;
    for(int i=0;i<10;i++)
    {
        if(small>a[i])
        {
            small=a[i];
        }
        if(big<a[i])
        {
            big=a[i];
        }
    }

    int small2=a[0],big2=a[0];

    for(int i=0;i<10;i++)
    {
        if(small2>a[i]&&a[i]!=small)
        {
            small2=a[i];
        }
        if(big2<a[i]&&a[i]!=big)
        {
            big2=a[i];
        }
    }
    System.out.println("second biggest = "+big2);
    System.out.println("second smallest = "+small2);
}
}

Now I want to find the fourth greatest and lowest. in this case i need to use 4 loops probably. but i want to do it in a shorter, smarter way. Can somebody help ?

Answer 1

here are some solutions:

1. if you don't wish to sort the whole input, you can put a temporary collection that you keep sorted ( or use one that is already always sorted).

   for example, if the input is "1,2,3,4,5,6,7,8,9,...1000" , and you wish to get the m-th largest number, you create a temporary collection of size m, and each number you go by, you decide if it should be inside the temporary array or not. you should always keep the temporary collection sorted (or just use one that is already always sorted), and put a new item into it, while removing the smallest one in case its size is over m.

   in terms of memory, you use a small size of collection items (m) and you don't modify the input array.

   in terms of operations number (complexity), you get about the same as of sorting the array - O(nlogn) ,because for each item you put into the temp array, the collection need to where to put it, and that takes logn (using binary search for example).

   btw, this solution is about the same as of getting the largest/smallest number, just that you don't need to sort items in the temporary collection, because it's of size 1 .

2. if you don't care about memory , but you just don't want to change the input, you can make a copy of the array and sort it instead...

3. there is a better algorithm that works in linear time , works similar to how you get a median (link here) . here's a link that shows it better.

Answer 2

You can use generic way.Sort the array using Arrays.sort(array); and then you can access it using index.

Answer 3

I think the easiest way is to order the Array (is Log(n)).

If you don't want to alter the original array you can do a clone first (int b[]= Arrays.copyOf(a, a.length);).

If you want the position in the array instead of the value tell me and I will find another solution.

Tell me if this helps:

    public static void main(String[] args) {

    Scanner sc = new Scanner(System.in);
    System.out.println("Enter");
    int a[] = { 45, 79, 2, 5, 74, 4, 19, 56, 2, 888 };

    Arrays.sort(a);
    System.out.print("ordered array: ");
    for(int i:a){
        System.out.print(i+", ");
    }
    System.out.println();
    System.out.println("the 4th smallest : " + a[3]);
    System.out.println("the 4th biggest: " + a[(a.length - 4)]);

}

Answer 4

Sorting a general array is O(nlogn), and then you can just pick your element by index.

You can also use the Select algorithm which has O(n) worst case time complexity. The algorithm gets an array and some k, and returns the k-th large element. I'm sure you can find an implementation of it.

Answer 5

public class FourthLargest {

    static int a[] = {45, 79, 2, 5, 74, 4, 19, 56, 2, 888};

    public static void main(String[] args) {
        Arrays.sort(a);
        System.out.println("The fourth smallest number = " + a[3]);
        System.out.println("The fourth largest number = " + a[a.length-4]);
    }
}

Answer 6

in order to find i-th element of unsorted array, There's a very simple randomized algorithm based on quicksort (quickselect) taking O(n) average time, and a pretty complicated non-randomized algorithm taking O(n) worst case time.

Everything you need is in these powerpoint slides. Just to extract the basic algorithm of the O(n) worst-case algorithm:

Select(A,n,i): Divide input into ⌈n/5⌉ groups of size 5.

/* Partition on median-of-medians */
medians = array of each group’s median.
pivot = Select(medians, ⌈n/5⌉, ⌈n/10⌉)
Left Array L and Right Array G = partition(A, pivot)

/* Find ith element in L, pivot, or G */
k = |L| + 1
If i = k, return pivot
If i < k, return Select(L, k-1, i)
If i > k, return Select(G, n-k, i-k)

It's also very nicely detailed in the Introduction to Algorithms book by Cormen et al.

for smallest element you can simply check every element and will take O(n) time.