Зная, когда закончится цикл в пузырьковой сортировки

Question

public class sortem { 

/** 
* @param args 
*/ 
private static void sort(int s[], int len){ 
    boolean swap = true; 
    int upperBound = 0; 
    while(swap){ 
     swap = false; 
     for(int i=0;i<len-(upperBound+1);i++) 
      if(s[i]> s[i+1]){ 
       int t=s[i]; 
       s[i]=s[i+1]; 
       s[i+1] = t; 
       swap = true; 

      } 
     upperBound++; 
    } 
} 
private static void print(int s[], int len){ 
    for(int i=0;i<len;i++) 
     System.out.println(s[i]); 

} 
public static void main(String[] args) { 
    int size = 10; 
    int s[] = new int [size]; 

    s[0] = 23; s[1] = 34; s[2] = 56; s[3] = 17; s[4] = 61; 
    s[5] = 3; s[6] = 92; s[7] = 44; s[8] = 19; s[9] = 63; 
    sort(s, size); 
    print(s, size); 
} 

} 

Вот мой вопрос:

Переменная UpperBound находится вне для цикла и внутри время цикла, но зачем мне нужна эта переменная. Я не уверен, что понимаю его «контроль» для цикла for. Когда я первоначально написал это сам я не имел этот переменный UpperBound и мой цикл закончится, когда я стал больше, чем длина массива, так:

for(int i = 0; i > len; i++) 

это не сработало. .. Может кто-нибудь помочь мне понять, как эта переменная upperBound помогает контролировать границы цикла? Я вижу, что +1 рядом с ним необходим для первого запуска, но будет ли он таким же, как инициализация upperBound до 1 вместо 0?

Answer 1

Идея состоит в том, что при первом запуске цикла for наибольший элемент заканчивается в конце массива. Второй раз, второй по величине элемент заканчивается индексом прямо до конца и т. Д.

Точка позади указания переменной upperBound здесь является то, что после того, как вы запустите Петлю k раз, последние k элементы в массиве являются k крупнейшими элементами в правильном порядке. Таким образом, нет необходимости рассматривать их в цикле снова (мы уже знаем, что они находятся в правильном месте). Каждый раз, когда мы запускаем цикл, другой элемент заканчивается в нужном месте, и, таким образом, это один из меньших элементов, который нам нужно рассмотреть (следовательно, поэтому условие цикла равно i < len - (upperBound+1), последние пары элементов, которые мы сравниваем, будут теми, которые справа до элементов, которые мы разместили в предыдущих итерациях).