자바에서 버블 정렬 혼돈

Question

배열을 사용하여 버블 정렬에 대한 질문이 있습니다. 여기에 몇 가지 예제 코드는 다음과 같습니다

public class SortArray 
{ 
    public static void main(String[] args) 
    { 
     int[] arr = {4,6,4,2,764,23,23}; 
     sort(arr); 
    } 
    static void sort(int[] arr) 
    { 
     int k; 
     for(int i = 0; i < arr.length; i++) { for(int j = i; j < arr.length-1; j++) { 
       if(arr[i] < arr[j+1]) 
       { 
        k = arr[j+1]; 
        arr[j+1] = arr[i]; 
        arr[i] = k; 
       } 
      } 
      System.out.print(arr[i] + " "); 
     } 
    } 
}

두 번째에 대한이, 내가 처음 루프는 배열의 각 요소를 통해 이동하는 것입니다 이해 배열을 확인하기위한 두 개의 루프가 있지만 어떻게? j이 i에서 시작하는 이유는 무엇이며 길이가 1을 뺀 이유는 무엇입니까?

또한 거품 정렬을 사용하여 ArrayList을 정렬 할 수 있습니까?

Answer 1

첫 번째 루프는 i에있는 요소를 보유하고 두 번째 루프는 다음에 각 요소를 검사하여 보유한 i과 비교합니다. 그것들을 바꿀 수 있으면, 알고리즘은 그들의 위치를 ​​바꾸고 계속 움직인다. 외부 루프가 반복을 완료하면 i 이전의 모든 요소가 정렬되므로 j은 i에서 시작합니다.

종이에이 작업을 한 번 수행하면 의미가 있습니다.

편집 : 당신이 당신의 알고리즘, 두 번째 루프 조건에 대한 이유를 완료, 당신은 j+1와 i을 교환한다는 것입니다. 따라서 j이 배열의 마지막 요소로 이동하면 다음 요소는 존재하지 않고 예외가 발생합니다. 또한이 코드를 사용하여 ArrayList을 정렬 할 수 있습니다. 적절한 setter 및 getter를 사용하여 코드 스와핑 값을 변경하십시오.

Answer 2

당신이 가지고있는 것은 selection sort이 아니라 bubble sort입니다.

버블 정렬은 인접한 요소 만 바꿉니다. 그러나 배열의 나머지 부분을 살펴보고 최소 정렬을 찾으려고합니다. 이는 정확하게 선택 정렬이하는 것입니다. 당신이 서로를 좀 더 명확 찾고 있다는

이제

for(int j = i + 1; j < arr.length; j++) 
{ 
    if(arr[i] < arr[j]) 
    { 
     k = arr[j]; 
     arr[j] = arr[i]; 
     arr[i] = k; 
    } 
} 

: 당신이 arr[j+1]을 사용하기 때문에

, 당신은 arr[j]을 사용하여 다음과 같이 하나의 범위를 이동하는 내부 루프를 다시 작성할 수 있습니다 나머지 요소를 사용하여 최소값을 찾습니다.

예, 당신은 단지 대신 배열의 ArrayList.get에 액세스하고 대신 배열 할당 ArrayList.set, 즉 사용하여 대신 ArrayList를 정렬 할 배열에서 작동 어떤 종류를 수정할 수 있습니다

for(int i = 0; i < arr.size(); i++) 
{ 
    for(int j = i + 1; j < arr.size(); j++) 
    { 
     if(arr.get(i) < arr.get(j)) 
     { 
      int k = arr.get(j); 
      arr.set(j, arr.get(i)); 
      arr.set(i, k); 
     } 
    } 
} 

참고가 모두 선택 정렬 및 버블 정렬은 매우 비효율적이며 (O(n^2)), 빠른 정렬이나 병합 정렬 (O(n log n)에서 실행)과 같은 there are more efficient sorting algorithms입니다.