How to get smallest number from a Circular list in Java?

Question

Let us suppose i have a circulatList something like this

circularList = [12, 62, 76, 92, 3, 7, 12, 19].

What will be most efficent way to get smallest number from the above list.

Answer 1

move through the list, remembering and comparing the first item, remembering the smallest number so far and returning it when we got back to the start of the list

here you can see how it is done.

int findMinimum(Node* start) 
{ 
    int min = start -> data; 
    Node* t = start -> link; 
    while(t != start) 
    { 
        if(t -> data < min) 
            min = t -> data; 
        t = t -> link; 
    } 
    return min; 
}  

Answer 2

Depending on the type of data structure you have stored those elements in you can either:

1) Iterate through the list and compare every value with the current smallest value:

int compareValue = Integer.MAX_VALUE;
for(int value: circularList){
    if(value < compareValue);
        compareValue = value;
}

2) Sort the list if the data type implements Collections.sort and just extract the smallest value.

Collections.sort(circularList);

Answer 3

In addition to @No Idea For Name: Collections.min(yourCollection)

Answer 4

i must say something before my answer that:

first, what you say and your example doesn't match. [12, 62, 76, 92, 3, 7] is circular sorted array. however your example :

[12, 62, 76, 92, 3, 7, 12, 19]

is not a circular, that's just combination of two sorted arrays.

And second, If you talk about the abstract way to do it. You need to modify some searching algorithm method. the efficiency of the method is depend on the case you have. so the algorithm will have its Worst case, Best case, and Average case performance. So what you call "most efficent way" is something that you need to try with your own test case.

Then my answer, if what you need to get smallest number from combination of two sorted arrays, i have something that more efficient way than bold compare:

int a;
int b = 0;\\your minimum possible value
//l= your array
for(int i=1; i<l.size;i++){
  b=l[i-1];
  a=l[i];
  if(b>a) // find the break point of the two sorted arrays
    if(a<l[0])
      return a;
    else 
      return l[0];
}
return l[0]; // in case the array already sorted(break point in 0 and l.size)

with this your looping will stop when they find the break point of the array, and return the smallest number by comparing the first number(12) with second array first number(3).

Answer 5

There is fundamentally only one algorithm for getting the smallest element from an arbitrary list:

  smallest = unset
  for each element in list:
      if smallest is unset OR element less than smallest:
          smallest = element

How this maps to code depends on the specific list data structure, or even a specific programming language can vary. But the basic structure is the same, and there are no specially efficient ways of doing it. (The complexity is O(N) where N is the list length.)

The only way you can improve on this is by constraining the list. For instance, if the list is already sorted with smallest first, then the getting the smallest element is simply a matter of getting the first one.

(But the cost of sorting the list is going to be at least O(N) ... and probably O(NlogN). Sorting to get the smallest value is going to be less efficient than just iterating and testing, as above.)

Answer 6

A single-thread solution to a generic list is:

int minValue= Integer.MAX_VALUE ;
for(int e: circularList )
    if( e < minValue ) minValue= e ;

For an array-based, sorted circular list where the first element's position is known:

minValue= circularList[firstElement] ;

For an array-based, sorted circular list where the last element's position is known:

if( lastElement+1 >= circularList.length )
    minValue= circularList[0] ;
else
    minValue= circularList[lastElement+1] ;

For an array-based, sorted circular list where first and last element's positions are unknown:

int minValue= Integer.MAX_VALUE ;
int prevValue= Integer.MIN_VALUE ;
for(int e: circularList ) {
    if( e < minValue )
        minValue= e ;
    if( e < prevValue ) {
        break;
    }
    prevValue= e ;
}

A multiprocessor-friendly solution to a generic list is:

int threadCount= 8 ;
int nextStart= 0 ;
MinimumFindingThread[] threads= MinimumFindingThread[threadCount] ;
while( threadCount > 0 ) {
    count= ( circularList.size() - nextStart ) / threadCount ;
    threads[threadCount-1]= new MinimumFindingThread(circularList,nextStart,nextStart+count) ;
    threads[threadCount-1].start();
    nextStart= nextStart+count ;
    threadCount--;
}
int threadCount= 8 ;
int minValue= Integer.MAX_VALUE ;
while( threadCount > 0 ) {
    threads[threadCount-1].join();
    theadMin= threads[threadCount-1].getResult() ;
    if( theadMin < minValue ) minValue= theadMin ;
    threadCount--;
}
class MinimumFindingThread extends Thread {
    int[] list;
    int from;
    int to;
    int minValue;
    public MinimumFindingThread(int[] list,int from,int to) {
        this.list= list ;
        this.from= from ;
        this.to= this.to ;
    }
    public void run() {
        int minValue= Integer.MAX_VALUE ;
        for(int e: this.list[this.from:this.to] )
            if( e < minValue ) minValue= e ;
        this.minValue= minValue ; ;
    }
    public int getResult() {
        return this.minValue ;
    }
}