최악의 경우가 로컬 삽입 정렬일까요?

-1

어떻게 로컬 insetion 정렬에 대한 최악의 경우를 생성하고 인쇄 할 수 있습니까? 내가 최악의 경우을 생성하기 위해 수정할 수있는 방법최악의 경우가 로컬 삽입 정렬일까요?

public class InsertionSort{ 
    public static void main(String a[]){ 
     int i; 
     int array[] = {12,9,4,99,120,1,3,10}; 
     System.out.println("Values Before the sort:\n"); 

     for(i = 0; i < array.length; i++) 
      System.out.print(array[i]+" "); 
     System.out.println(); 

     insertion_srt(array, array.length); 
     System.out.print("Values after the sort:\n"); 

     for(i = 0; i <array.length; i++) 
      System.out.print(array[i]+" "); 

     System.out.println(); 
     System.out.println("PAUSE"); 
    } 

    public static void insertion_srt(int array[], int n){ 
     for (int i = 1; i < n; i++){ 
      int j = i; 
      int B = array[i]; 
      while ((j > 0) && (array[j-1] > B)){ 
       array[j] = array[j-1]; 
       j--; 
      } 
      array[j] = B; 
     } 
    } 
}

:이 지역 삽입 정렬의 내 구현?.

출처

2013-10-20 winston smith

기존 스타일을 사용하여 코드를 포맷 할 수 있다면 코드가 무엇을하는지 쉽게 알 수 있습니다. –

삽입 정렬에서 왼쪽 요소 양식을 사용하여 값을 변수에 할당하십시오. 그런 다음 이전 값과 비교하십시오. 값이 이전 값보다 작아야하는 값을 입력하십시오. 그런 다음 변수에 다음 값을 할당하고 비교가 배열의 끝까지 도달하지 않을 때까지 동일한 단계를 따르십시오. –

@winstonsmith 읽을 수없는 코드 벽에시를 추가하는 대신 읽을 수있는 미리보기를 만들면 훨씬 더 쉽습니다. – BartoszKP

내림차순으로 정렬 된 배열은 최악의 경우가 될 수 있습니다 (또는 일반적인 구현의 경우 정렬 순서와 반대).

이를 확인하려면, 삽입 정렬 작동 방법을 고려해야 : 어떤 시점에서

를 입력 두 가지로 나뉩니다 - 왼쪽에 정렬 정렬되지 않은 오른쪽 : 처음

sorted | unsorted

정렬 된 부분 빈 상태로 시작한 다음, 정렬되지 않은 부분의 맨 왼쪽 요소를 반복적으로 삽입하여 값을 오른쪽으로 이동하여 공간을 만듭니다.

이제 각 삽입에 대한 최악의 경우는 왼쪽 끝까지 삽입해야 할 때입니다. 다른 모든 값을 올리면 위치를 변경해야합니다. 이것이 언제 일어날까요? 삽입 할 요소가 왼쪽의 모든 요소보다 작은 경우.

그래서 최악의 경우는 각 요소가 왼쪽의 모든 요소보다 작 으면서 내림차순으로 배열입니다.

출처

2013-10-20 22:21:42 Dukeling

최악의 경우가 로컬 삽입 정렬일까요?

답변

관련 문제