Java 선택 정렬

Question

모든 색인을 확인하는 데 문제가 있습니다. j의 세 번째 인덱스는 건너 뜁니다. i[0], j[2], i[0], j[4] 왜 그렇게하는지 모르겠습니다. 또한, 실제로 번호를 교환하는 데 문제가 있습니다. 아무도 내 오류가 어디 있는지 아십니까?

static void selectionSort(int[] arr) { 
     final long startTime = System.nanoTime(); // starts timer 
     System.out.println("Selection Sort"); 
     //************** Code For Sorting *****************// 
     //*************************************************// 
     int counter = 0; 
     int first = 0; 
     int second = 0; 
     //int[] sorted = Arrays.copyOf(arr, arr.length); // Copies unsorted array to new array 
     //Arrays.sort(sorted); // sorts unsorted array for compairison later on 
     for(int i = 0; i < arr.length-1; i++) // comparing the first index value to the rest of the values in the array 
     { 
      int minIndex = i; 

      for(int j = 1; j < arr.length-1; j++) // representing the next index value to the original and comparing it 
      { 
       int nextIndex = j; 

       if(arr[minIndex] < arr[nextIndex]) 
       { 
        System.out.println("i: " +i); 
        System.out.println("j: " +j); 
        System.out.println("Checking next index"); 

       } 
       if(arr[minIndex] > arr[nextIndex]) 
       { 
        System.out.println("i: " +i); 
        System.out.println("j: " +j); 
        //counter = j; // getting array index 
        first = arr[minIndex]; 
        second = arr[nextIndex]; 
        minIndex = second; 
        arr[minIndex] = second; 
        System.out.println("first:" + first); 
        System.out.println("second:" + second); 
        System.out.println("minIndex:" + minIndex); 
        System.out.println("arr[minIndex]:" + arr[minIndex]) ; 
        System.out.println("Possible lowest unsorted value"); 

       } 
       //Swap here 
       if(arr[arr.length-1] == arr[j]){ 
        arr[0] = second; 
        arr[counter] = first; 
        counter = 0; 
        //minIndex= i+1; 
       } 
      } 
      for(int k = 0; k < arr.length; k++) 
      { 
       System.out.print(arr[k] + ", "); 
      } 
      System.out.println(); 
     } 

Answer 1

첫 번째 실수는 중첩 된 for 루프 내에 있습니다. 외부 루프에 대한 시작 인덱스 (j)는 루프 이 아닌j = 1 번 반복 할 때마다 항상 i + 1 (인덱서앞에 1 자)에서 시작해야합니다.

두 번째로 j < arr.length-1 조건을 사용하면 항상은 배열 내의 마지막 요소를 제외합니다.

변경이이에

for(int j = 1; j < arr.length-1; j++) 

:

for(int j = i + 1; j < arr.length; j++) 

가 이동은, 그래서 당신의 swap 기능을 포함하여 알고리즘 몇 가지 문제를 수의 다시 시작하자 것 같습니다.

선택 정렬은 배열이 왼쪽 끝에 정렬 된 부분과 오른쪽 끝에 정렬되지 않은 부분의 두 부분으로 나뉘어있는 비교 기반 알고리즘입니다. 처음에 정렬 된 부분은 비어 있고 정렬되지 않은 부분은 전체 배열입니다.

가장 작은 요소는 정렬되지 않은 배열에서 선택되고 가장 왼쪽 요소와 교체되며 해당 요소는 정렬 된 배열의 일부가됩니다. 이 프로세스는 정렬되지 않은 배열 경계를 한 요소만큼 오른쪽으로 계속 이동합니다.

염두에두고 이제 알고리즘을 시작할 수 있습니다. 사이드 참고로

public static void selectionSort(int[] arr){ 
    for(int i = 0; i < arr.length-1; i++){ 
     int minIndex = i; // smallest element index 
     for(int j = i + 1; j < arr.length; j++){ 
      if(arr[j] < arr[i]){ // find smallest element 
       if(arr[j] < arr[minIndex]) 
       minIndex = j; // update smallest element index 
      } 
     } 

     if(i != minIndex){ // swap 
      int temp = arr[minIndex]; 
      arr[minIndex] = arr[i]; 
      arr[i] = temp; 
     } 
    } 
    // print the result 
    Arrays.stream(arr).forEach(System.out::println); 
} 

는 선택 정렬 복잡성 N는 어레이 내의 요소의 수이다 Ο(N2),로된다.