Computer >> 컴퓨터 >  >> 프로그램 작성 >> JavaScript

Java의 삽입 정렬:방법 가이드

Java 삽입 정렬은 목록의 각 항목을 평가합니다. 항목이 이전 항목보다 작으면 정렬에서 항목을 바꿉니다. 그렇지 않으면 항목이 같은 위치에 유지되고 다음 두 항목이 목록에서 비교됩니다.

컴퓨터는 항목 목록을 정렬하는 데 능숙합니다. 루프를 사용하여 목록의 모든 항목을 검색하고 특정 방식으로 나타날 때까지 순서를 변경할 수 있습니다.

프로그래밍에는 목록을 정렬하는 몇 가지 표준 방법이 있습니다. 우리는 이러한 정렬 알고리즘을 호출합니다. 정렬 알고리즘은 목록의 모든 항목을 읽고 특정 명령 집합을 사용하여 정렬합니다. 가장 일반적인 정렬 알고리즘 중 하나는 삽입 정렬입니다.

이 가이드에서는 Java 삽입 정렬 알고리즘을 구현하는 방법에 대해 설명합니다. 이 정렬의 논리가 어떻게 작동하는지 배울 수 있도록 예제를 통해 살펴보겠습니다.

시작하겠습니다!

자바 삽입 정렬이란 무엇입니까?

Java 삽입 정렬은 카드 게임에서 손에 있는 카드를 정렬하는 것과 유사하게 작동합니다. 삽입 정렬은 목록의 각 항목을 확인하고 왼쪽에 있는 항목으로 교체합니다. 아이템 교환 여부는 아이템이 이전 아이템보다 크거나 작은지에 따라 달라집니다.

잠시 동안 당신이 카드 게임을 하고 있다고 상상해보십시오. 휘파람, 러미, 무엇이든. 카드를 분류할 때 무엇을 하시나요?

왼쪽에서 시작하여 두 번째 카드가 정렬되었는지 확인합니다. 그 카드가 마지막 카드보다 크면 같은 위치에 있어야 합니다. 그렇지 않으면 목록에서 한 위치 위로 이동해야 합니다.

참가자의 81%는 부트캠프에 참석한 후 기술 직업 전망에 대해 더 자신감을 느꼈다고 말했습니다. 지금 부트캠프에 참여하십시오.

부트캠프 졸업생은 부트캠프 시작부터 첫 직장을 찾는 데까지 6개월도 채 걸리지 않았습니다.

손에 있는 모든 카드를 살펴보고 모든 카드가 올바른 순서로 나타날 때까지 이 작업을 수행합니다.

언제 삽입 정렬을 사용해야 합니까?

삽입 정렬은 왼쪽에 정렬해야 하는 요소가 몇 개 없을 때 가장 많이 사용됩니다.

병합 정렬과 같이 큰 데이터 목록을 정렬하는 데 사용할 수 있는 보다 효율적인 알고리즘이 있습니다. 이것이 항상 기본적으로 삽입 정렬을 사용해서는 안 되는 이유입니다. 즉, 삽입 정렬은 목록의 요소를 정렬할 때 버블 정렬 및 선택 정렬보다 더 효율적입니다.

삽입 정렬은 초보자가 배우기에 좋은 간단한 정렬 알고리즘입니다.

삽입 정렬 연습

카드 더미를 시각화하는 것은 세상에서 가장 직관적이지 않습니다. 시작하기 위해 프로그래밍 예제를 살펴보겠습니다. 다음 목록을 고려하십시오.

8 6 3 9

이 목록에서는 첫 번째 요소가 정렬되었다고 가정합니다.

다음 단계는 목록의 두 번째 항목을 첫 번째 항목과 비교하는 것입니다. 첫 번째 항목이 두 번째 항목보다 크면 해당 항목이 첫 번째 항목 앞에 배치됩니다.

이 경우 6은 8보다 큽니다. 즉, 6은 목록에서 한 위치 뒤로 이동하고 8은 한 위치 앞으로 이동합니다.

6 8 3 9

이제 세 번째 요소를 왼쪽 요소와 비교해야 합니다. 3은 8보다 큽니까? 아니요, 따라서 8은 위치를 오른쪽으로 이동합니다.

6 3 8 9

3은 6보다 크다? 아니요, 숫자 6을 이동합니다.

3 6 8 9

이제 목록의 네 번째 항목인 마지막 항목이 목록의 다른 모든 항목보다 큰지 비교해야 합니다. 이 경우 9는 그 앞에 오는 모든 항목(8, 6, 3)보다 큽니다.

다음은 목록을 정렬하는 데 사용한 알고리즘입니다.

  • 첫 번째 요소가 정렬됩니다.
  • 두 번째 항목을 왼쪽 항목과 비교합니다.
  • 이 항목이 왼쪽 값보다 크면 항목이 같은 위치에 유지됩니다. 그렇지 않으면 값을 왼쪽으로 이동합니다.
  • 모든 항목이 순서대로 나타날 때까지 반복합니다.

이제 정렬된 배열이 있습니다. 삽입 정렬은 한 번에 하나의 항목을 정렬합니다. Java에서 이 정렬 알고리즘을 구현하는 방법에 대해 논의해 보겠습니다.

자바에서 삽입 정렬을 수행하는 방법

정렬 기능이 실행될 때마다 비교되는 두 값 중 가장 높은 값이 오른쪽으로 한 위치에 삽입됩니다.

이론적으로 이것에 대해 잘 이야기하고 있지만 Java에서 어떻게 구현합니까? 그건 좋은 질문이야. 학생 성적 목록에 삽입 정렬을 수행하는 클래스를 작성해 보겠습니다.

배열 라이브러리 준비

Array 라이브러리를 Java 프로그램으로 가져오는 것으로 시작하겠습니다. 정렬이 완료되면 이 라이브러리를 사용하여 목록을 콘솔에 인쇄합니다.

import java.util.Arrays;

정렬 방법 선언

목록을 살펴보고 오름차순으로 데이터를 정렬하는 메서드를 선언하는 것으로 시작하겠습니다. :

class SortGrades {
public static void insertionSort(int [] numbersToSort) {
	int itemCount = numbersToSort.length;

	for (int value = 1; value < itemCount; value++) {
		int key = numbersToSort[value];
		int last = value - 1;

		while (last >= 0 && key < numbersToSort[last]) {
			numbersToSort[last + 1] = numbersToSort[last];
			--last;
		}

		numbersToSort[last + 1] = key;
	}
}
}

입력 배열의 항목 수를 찾는 것으로 시작합니다. 이를 통해 목록의 모든 항목을 통과하는 루프를 만들 수 있습니다. 목록을 정렬할 때까지 반복되는 for 루프를 초기화합니다.

for 루프 내에서 key와 last라는 두 개의 변수를 선언했습니다.

"key" Java 변수는 현재 정렬 중인 항목을 추적합니다. "마지막" 변수는 항목 왼쪽에 정렬해야 하는 항목 수를 추적합니다.

우리 프로그램은 더 작은 요소를 찾을 때까지 "key" 값을 왼쪽에 있는 각 요소와 비교합니다. 이것은 Java "while" 루프에서 발생합니다.

주요 기능 정의

이 코드를 실행하면 아무 일도 일어나지 않습니다. 아직 main 함수를 정의하지 않았기 때문입니다. int 배열(숫자의 배열)을 정의하는 메인 함수를 정의합시다. 이 주요 함수는 insertionSort() 이 숫자를 정렬하기 위해 선언한 함수입니다. insertSort Java 메소드를 선언한 후 이 코드를 붙여넣으세요.

public static void main(String args[]) {
	int[] numbers = { 8, 6, 3, 9 };
	InsertionSort sortNumbers = new InsertionSort();
	sortNumbers.insertionSort(numbers);

	String arrayToString = Arrays.toString(numbers);
	System.out.println("Sorted list: " + arrayToString);
}

기본 메소드에서 정렬하려는 숫자 목록을 선언했습니다. InsertionSort()의 인스턴스를 만들었습니다. sortNumbers라는 메소드 . 이 방법을 사용하여 숫자 목록을 오름차순으로 정렬합니다. 이 메서드는 "숫자" 배열 내부의 값을 변경합니다. 값을 저장할 별도의 배열을 선언하지 않았습니다.

다음으로 Arrays.toString()을 사용했습니다. 숫자 배열을 문자열로 변환하는 메서드입니다. 정렬된 목록을 콘솔에 출력합니다.

복잡성 검토

삽입 정렬의 평균 케이스 복잡도는 O(n^2)입니다. 이것은 정렬된 요소가 없을 때 발생합니다.

배열이 정렬되면 최상의 복잡성이 발생합니다. 이것은 O(n)의 시간 복잡도를 생성합니다. 이 경우 삽입 정렬의 내부 루프가 전혀 실행되지 않기 때문입니다.

최악의 경우 삽입 정렬은 O(n^2)에서 수행됩니다. 이것은 배열이 오름차순 또는 내림차순이고 역으로 정렬하려는 경우(즉, 오름차순에서 내림차순으로) 발생합니다. 여기에는 모든 요소를 ​​다른 모든 요소와 비교하는 작업이 포함됩니다.

결론

삽입 정렬은 데이터를 정렬하는 효율적인 방법입니다. 삽입 정렬은 목록의 두 번째 값부터 시작하여 값을 비교합니다. 이 값이 왼쪽에 있는 값보다 크면 목록이 변경되지 않습니다. 그렇지 않으면 왼쪽에 있는 항목이 그보다 작을 때까지 값을 이동합니다.

이제 Java로 삽입 정렬 알고리즘을 작성할 준비가 되었습니다! 더 많은 Java 학습 리소스를 찾고 있다면 Java 학습 방법 가이드를 확인하세요.