아웃 [ArrayList에와 버블 선택]

Question

나는이 자격 증명을 사용하여 작동합니다 버블 선택 방법, 코딩 해요 :

/* Write code for a Bubble Sort algorithm that starts at the right side of 
* of ArrayList of Comparable objects and "bubbles" the largest item to the 
* left of the list. The result should be an ArrayList arranged in descending 
* order. 
*/ 
@SuppressWarnings("unchecked") 
void bubbleSort(ArrayList <Comparable> list) { 

    int end = list.size(); 

    for (int i = 0 ; i < end; i++){ 
     for (int j = end; j > 0; j--){ 
      if (list.get(j).compareTo(list.get(j-1)) > 0){ 
       //swap 
       Comparable temp = list.get(j); 
       list.set(j,list.get(j - 1)); 
       list.set(j - 1, temp); 
       //System.out.println(list); 
      } 
     } 
     end--; 
    } 
} 

문제는이다, 자바는 그것을 밖으로 나에게 말할 것이다 경계.

내가 대신 그러나 그것은 완전히 (이것은 앞서 한 루프를 중지 일명) 정렬 완료 할 목록을 실행하는 데 필요한 횟수를 실행하지 않습니다,

for (int j = end - 1; j > 0; j--) 

코드가 다음 실행

를 사용하는 경우

Answer 1

이 코드를 사용하면 배열 구현에서 요구 사항에 맞게 작동합니다. 크기이 배열 길이입니다.

for (int i = 0; i < size - 1; j++) { 
    for (int j = i + 1; j < size - 1; k++){ 
     if (array[i] > array[j]) { 
      int temp = array[i]; 
      array[i] = array[j]; 
      array[j] = temp; 
     } 
    } 
} 

Answer 2

배열이 길면 배열 [3]이 (가) 범위를 벗어납니다. 배열 [lenght]로 시작 했으므로 제공 한 코드와 같이 for주기에 들어가기 전에이를 줄여야합니다.

Answer 3

위에서 설명한대로 끝에서 1부터 시작해야합니다. 그렇지 않으면 배열 범위를 벗어나 액세스 할 수 있습니다.

---

의 당신이 정수의 배열이 있다고 가정 해 봅시다 :이 할 것입니다 귀하의 algorith

5 1 4 :

1 회 반복 -> 난 = 0/j는 2

1 5 4 

에서 시작 두 번째 반복 -> i = 1/j 1부터 시작

이제는 5가 높기 때문에 5와 1을 유지하고 전환하지 마십시오. 그래서, 그리고 4와 5? 그들은 교환되어야합니다. 알고리즘 구현이 잘못되었습니다.

end--;을 제거하면 올바르게 작동합니다. 그러나, 이것은 당신이 ArrayOutOfBound Exception을 줄 것이다 지난 후 인덱스에서 마지막 값과 가치를 비교하려고합니다 end를 사용하는 경우 목록 에 마지막과 마지막에서 두 번째 값을 비교합니다 end - 1를 사용

Answer 4

을 최적화 할 수 있습니다.

for (int i = 0 ; i < end; i++){ 
     for (int j = end -1; j > 0; j--){ 
      if (list.get(j).compareTo(list.get(j-1)) > 0){ 
       //swap 
       Comparable temp = list.get(j); 
       list.set(j,list.get(j - 1)); 
       list.set(j - 1, temp); 
      } 
     } 
     //remove below line 
     end--; 
    } 

이 아래 그림에 따라

지금 올바른 출력을 위해 당신이 end--; 줄을 제거해야합니다 짧은 마우스 오른쪽 측면에서 하나 개의 값을 기준으로 목록. 그래서 제거 할 것입니다