자바의 삽입정렬

프로그래머라면 정렬에 대해 이미 많이 들어봤을 것입니다. 정렬은 기본적으로 요소를 오름차순 또는 내림차순으로 정렬하는 것입니다. 요소를 정렬하는 데 사용할 수 있는 정렬 알고리즘은 매우 많으며 모든 알고리즘에는 정렬 방법과 복잡성이 다릅니다. 따라서 어떤 알고리즘을 사용해야 하는지는 특정 시나리오와 요소 수에 따라 달라집니다. 삽입은 O(n^2) 복잡도로 일반적으로 사용되는 정렬 알고리즘 중 하나이며 손에 카드를 정렬하는 것처럼 수행됩니다. 이번 주제에서는 자바의 삽입정렬에 대해 알아보겠습니다.

무료 소프트웨어 개발 과정 시작

웹 개발, 프로그래밍 언어, 소프트웨어 테스팅 등

Java에서 삽입 정렬은 어떻게 작동하나요?

예제를 통해 삽입 정렬의 동작을 이해해 봅시다.

아래 언급된 요소를 포함하는 arr이라는 이름의 배열이 있다고 가정합니다.

10 5 8 20 30 2 9 7

1단계 – 삽입 정렬은 배열의 두 번째 요소, 즉 5부터 시작합니다. 배열의 첫 번째 요소가 자체적으로 정렬되어 있는 것을 고려합니다. 이제 5가 10보다 작으므로 요소 5를 10과 비교하므로 10이 한 위치 앞으로 이동하고 5가 그 앞에 삽입됩니다.

이제 결과 배열은 다음과 같습니다.

5 10 8 20 30 2 9 7

2단계 – 이제 arr[2] 요소, 즉 8이 요소 arr[1], 즉 10과 비교됩니다. 8이 이전 요소 10보다 작으므로 하나 이동합니다. 그 위치보다 한발 앞서서 5와 비교합니다. 8은 5보다 크므로 그 뒤에 삽입됩니다.

결과 배열은 다음과 같습니다.

5 8 10 20 30 2 9 7

3단계 – 이제 요소 20이 10보다 크기 때문에 10과 비교되었으므로 해당 위치는 그대로 유지됩니다.

5 8 10 20 30 2 9 7

4단계 – 요소 30을 20과 비교하고 20보다 크므로 변경 사항이 없으며 배열은 그대로 유지됩니다. 이제 배열은

5 8 10 20 30 2 9 7

5단계 – 요소 2는 30과 비교됩니다. 30보다 작기 때문에 한 자리 앞으로 이동한 다음 20,10, 8, 5와 하나씩 비교하고 모든 요소가 앞쪽의 1 위치로 이동되고 2가 5 앞에 삽입됩니다.

결과 배열은 다음과 같습니다.

2 5 8 10 20 30 9 7

6단계 – 요소 9는 30보다 작으므로 30과 비교됩니다. 20, 10을 하나씩 비교하여 요소가 1자리 앞으로 이동하고 9가 10 앞에 삽입되고 8 뒤에 삽입됩니다.

결과 배열은 다음과 같습니다.

2 5 8 9 10 20 30 7

7단계 – 요소 7을 30과 비교하고 30보다 작으므로 30, 20, 10, 9, 8과 비교하여 모든 요소를 ​​1자리 이동합니다. 8 앞에 7이 삽입됩니다.

결과 배열은 다음과 같습니다.

2 5 7 8 9 10 20 30

이러한 방식으로 배열의 모든 요소는 삽입 정렬을 사용하여 정렬되어 이전 요소와 비교를 시작합니다.

Java에서 삽입 정렬을 구현하는 예

Java의 삽입 정렬은 모든 소규모 데이터 세트에 적합한 간단한 정렬 알고리즘입니다.

코드:

public class InsertionSort {
public static void insertionSort(int arr[]) { for (int j = 1; j < arr.length; j++) { int key = arr[j]; int i = j-1;
while ( (i > -1) && ( arr[i] > key ) ) { arr[i+1] = arr[i]; i--; }
arr[i+1] = key;
}
}
static void printArray(int arr[]) { int len = arr.length;
//simple for loop to print the elements of sorted array for (int i= 0; i<len; i++)
System.out.print(arr[i] + " " );
System.out.println();
}
public static void main(String args[]){ int[] arr1 = {21,18,15,23,52,12,61};
//calling the sort function which performs insertion sort insertionSort(arr1);
//calling the printArray function which performs printing of array printArray(arr1);
}
}

출력:

12 15 18 21 23 52 61

설명:

• 위의 삽입 정렬 프로그램에서는 삽입 정렬() 함수를 사용하여 원래 배열 요소를 정렬합니다. 정렬은 첫 번째 요소가 자체적으로 정렬된 것으로 간주되므로 두 번째 요소부터 시작됩니다. 따라서 'j'의 루프는 배열의 인덱스 1부터 시작됩니다. 'i'는 값을 비교하기 위해 'j' 바로 앞의 인덱스를 추적하는 변수입니다.'
• key'는 정렬된 위치에 정렬될 현재 요소의 값을 보유하는 변수입니다. 현재 값이 가장 왼쪽 값보다 작을 경우 while() 루프를 실행하여 요소 이동을 처리하고 마지막에는 현재 요소를 오른쪽 위치에 삽입합니다. printArray() 함수는 정렬된 배열을 최종적으로 인쇄하는 데 사용됩니다.

1. 최선의 사례

삽입 정렬에서는 배열의 모든 요소가 이미 정렬되어 있는 경우가 가장 좋습니다. 따라서 요소를 가장 왼쪽 요소와 비교할 때 항상 더 크므로 요소 이동 및 삽입이 처리되지 않습니다. 이 경우 가장 좋은 경우의 복잡성은 선형, 즉 O(n)입니다.

2. 최악의 경우

위의 삽입 정렬 코드에서 최악의 경우는 배열이 역순이므로 요소가 가장 왼쪽 요소와 비교될 때마다 항상 작아지고 이후에 오는 모든 요소와 비교됩니다. 배치 및 이동과 삽입이 완료됩니다. 이 경우 삽입 정렬의 복잡도는 O(n^2)입니다.

3. 평균 사례

일반적인 경우에도 삽입 정렬은 O(n^2) 복잡도로 일부 요소는 이동이 필요하지 않지만 일부 요소는 원래 위치에서 이동하여 올바른 위치에 삽입됩니다.

4. 최고의 활용

삽입 정렬은 배열의 크기가 그리 크지 않거나 거의 모든 요소가 정렬되어 있는 소수의 요소만 정렬하고 일부만 변경하면 되는 경우에 사용하는 것이 가장 좋습니다. 삽입 정렬은 작은 크기의 배열에 대한 가장 빠른 알고리즘 중 하나이며 빠른 정렬보다 훨씬 빠릅니다. 실제로 퀵 정렬은 배열의 작은 부분을 정렬할 때 삽입 정렬을 사용합니다.

결론

위의 설명은 Java에서 삽입 정렬의 작동 및 구현을 명확하게 보여줍니다. 다른 프로그래밍 언어에서도 삽입 정렬을 수행하는 논리는 구문만 변경되어 동일하게 유지됩니다. 모든 정렬 알고리즘이 모든 시나리오에 적합한 것은 아니므로 정렬 알고리즘을 구현하기 전에 정렬을 수행해야 하는 시나리오를 분석하는 것이 매우 중요합니다.

위 내용은 자바의 삽입정렬의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!