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

Java 선택 정렬:방법 가이드

Java 선택 정렬은 목록에서 가장 작은 항목을 찾아 해당 값을 목록의 시작 부분으로 이동합니다. 이것은 첫 번째 목록의 모든 요소가 정렬될 때까지 반복적으로 발생합니다. 선택 정렬은 정렬된 목록을 반환합니다.

Java에서 목록을 어떻게 정렬합니까? 몇 가지 옵션이 있습니다. 한 가지 일반적인 옵션은 선택 정렬입니다.

이 가이드에서는 선택 정렬이 무엇이며 어떻게 작동하는지 설명합니다. 또한 Java에서 선택 정렬을 작성하는 방법을 살펴보고 자신만의 선택 정렬을 작성하는 방법을 알게 될 것입니다. 시작하겠습니다!

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

선택 정렬은 목록에서 최소 항목을 반복적으로 찾아 목록에서 정렬되지 않은 항목의 시작 부분으로 이동합니다. 이 프로세스는 목록이 주문될 때까지 목록의 모든 항목에 대해 반복됩니다.

목록의 첫 번째 항목은 가장 작은 항목으로 간주됩니다. 이 항목은 다음 요소와 비교됩니다. 다음 요소가 더 작으면 요소가 바뀝니다. 이 알고리즘은 마지막 요소에 도달할 때까지 최소 요소를 찾습니다. 그런 다음 프로그램은 가장 작은 항목을 목록의 시작 부분으로 이동합니다.

선택 정렬에서 목록은 정렬된 목록과 정렬되지 않은 목록의 두 부분으로 구성됩니다. 요소가 정렬되면 정렬되지 않은 하위 배열에서 정렬된 하위 배열로 이동합니다.

목록을 오름차순 또는 내림차순으로 정렬할 수 있습니다.

선택 정렬을 언제 사용해야 합니까?

선택 정렬은 작은 목록을 정렬해야 할 때 최적입니다. 큰 목록을 정렬하는 더 효율적인 방법이 있기 때문입니다. 병합 정렬, 삽입 정렬 및 빠른 정렬과 같은 알고리즘은 Java 프로그래밍에서 선택 정렬보다 효율적입니다.

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

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

선택 정렬은 배열의 모든 요소를 ​​필수로 검사할 때 가장 잘 수행됩니다. 목록의 항목이 거의 또는 전혀 정렬되지 않은 경우입니다. 선택 정렬은 일반적으로 이해하기 쉬운 버블 정렬보다 성능이 뛰어납니다.

선택 정렬은 어떻게 작동합니까?

알고리즘이 무엇을 원하는지 먼저 알지 못한 채 Java에서 알고리즘을 구현하려고 시도하는 것은 아무 소용이 없습니다. 먼저 목록을 순서대로 정렬하기 위해 선택 정렬이 수행하는 단계를 살펴보겠습니다.

다음 정렬되지 않은 배열을 고려하십시오.

17 14 9 12

선택 정렬은 첫 번째 항목을 목록에서 가장 작은 항목으로 설정합니다. 이것은 프로그램이 비교할 때마다 변경되는 임시 값입니다. 이 값은 자체 변수에 저장됩니다.

최소 =17


17 14 9 12

"최소" 항목은 두 번째 요소와 비교됩니다. 이 요소는 배열의 정렬되지 않은 부분에 있습니다. 정렬된 요소 다음의 모든 요소는 정렬되지 않습니다.

두 번째 요소가 "최소" 항목보다 작다고 가정합니다. 이 경우 "최소" 항목의 값은 두 번째 항목의 값으로 설정됩니다. 14는 17보다 작으므로 새로운 최소값은 14가 됩니다.

최소 =14


17 14 9 12

이 프로세스는 목록의 각 항목에 대해 반복됩니다. 9는 14보다 작습니다. 따라서 "minimum"의 값은 9가 됩니다. 9는 12보다 작지 않으므로 minimum 값은 동일하게 유지됩니다.

한 번 반복한 후 목록에서 9가 가장 작은 숫자임을 발견했습니다. 이 항목은 목록의 시작 부분으로 이동됩니다:

9 17 14 12

이 프로세스는 정렬되지 않은 첫 번째 요소에서 다시 시작됩니다. 따라서 다음 비교 세트는 17로 시작합니다.

  • 17은 최소값과 같습니다.
  • 저희 프로그램은 17과 14를 비교합니다. "최소값"의 값은 14가 됩니다.
  • 우리 프로그램은 14를 12와 비교합니다. "최소값"의 값은 12가 됩니다.
  • 우리 프로그램은 목록에서 정렬된 항목의 끝으로 12를 이동합니다.

목록은 다음과 같습니다.

9 12 17 14

이 프로세스는 목록이 주문될 때까지 반복됩니다. 알고리즘 실행이 완료되면 다음 목록이 반환됩니다.

9 12 14 17

목록은 오름차순으로 정렬됩니다.

자바에서 선택 정렬을 작성하는 방법

선택 정렬이 어떻게 작동하는지 아는 것은 한 가지입니다. 그것은 하나를 구축하는 또 다른 것입니다. 실습에서 논의한 논리를 사용하여 Java에서 선택 정렬을 코딩해 보겠습니다.

프로그램 설정

selection_sort.java라는 파일을 작성하십시오. Java Arrays 라이브러리를 코드로 가져오는 것으로 시작하겠습니다.

import java.util.Arrays;

이 라이브러리는 나중에 코드에서 사용합니다. 이를 사용하여 정렬된 배열을 문자열로 변환하여 콘솔에 출력할 수 있습니다.

정렬 함수 생성

다음으로, 우리는 클래스를 선언하고 선택 정렬을 수행하는 메소드를 생성할 것입니다. selection_sort.java에 다음을 추가하세요. 파일:

class SelectionSort {
	void sortNumbers(int array[]) {
		int size = array.length;

		for (int item = 0; item < size - 1; item++) {
			int minimum = item;
			for (int number = minimum + 1; number < size; number++) {
				if (array[number] < array[minimum]) {
					minimum = number;
				}
			}
			
			int temporary = array[item];
			array[item] = array[minimum];
			array[minimum] = temporary;
		}
	}
}

우리 클래스에서는 sortNumbers라는 메소드를 정의했습니다. 우리의 정렬을 수행합니다. 배열의 길이를 계산하는 것으로 시작합니다. 배열의 길이를 Java 변수에 저장합니다.

그런 다음 Java for 루프를 만듭니다. 이 루프는 목록의 모든 항목을 반복합니다. 이 for 루프 내에서 목록의 첫 번째 항목인 최소 항목을 찾습니다.

그런 다음 최소 항목을 목록의 모든 항목과 비교하기 위해 또 다른 for 루프를 시작합니다.

for 루프가 읽고 있는 숫자가 최소 숫자보다 작으면 "최소" 값이 그 숫자가 됩니다. 루프에서 "숫자"는 최소값과 비교할 숫자의 인덱스 값을 나타냅니다.

최소 숫자가 목록의 모든 숫자와 비교되면 내부 for 루프가 중지됩니다. 그런 다음 목록에서 정렬된 모든 숫자 뒤에 최소 숫자가 이동합니다.

정렬 함수 호출

우리 코드는 아직 아무것도 하지 않습니다. 아직 클래스를 호출하지 않고 정렬할 목록을 제공하지 않았습니다.

sortNumbers 아래 목록에 메서드를 추가하려면 다음 코드를 추가하세요.

public static void main(String args[]) {
	int[] toSort = { 17, 14, 9, 12 };
	SelectionSort newSort = new SelectionSort();
	newSort.sortNumbers(toSort);
	
	System.out.println(Arrays.toString(toSort));
}

기본 메소드 내에서 정렬할 항목 목록을 toSort라고 선언했습니다. . 그런 다음 newSort라는 SelectionSort 클래스의 인스턴스를 초기화합니다. 이것을 사용하여 sortNumbers를 호출합니다. toSort 배열의 값을 정렬하는 메서드입니다.

sortNumbers 메소드가 실행된 후 정렬된 배열을 콘솔에 출력합니다. Array.toString()을 사용하여 이 작업을 수행합니다. 배열을 문자열 목록으로 변환하는 메서드입니다.

코드를 실행해 보겠습니다.

[9, 12, 14, 17]

목록이 정렬되었습니다!

Java 선택 정렬:값을 내림차순으로 정렬

값을 내림차순으로 정렬할 수 있다는 점은 주목할 가치가 있습니다. 이렇게 하려면 sortNumbers에서 다음 코드 줄을 바꾸세요. 방법:

if (array[number] < array[minimum]) {

이 코드로:

if (array[number] > array[minimum]) {

이 코드는 "최소" 값이 for 루프에서 액세스하는 값보다 큰지 확인합니다. 즉, "최소" 값은 목록에서 가장 낮은 값 대신 가장 높은 값을 반영합니다.

혼동을 방지하려면 목록을 내림차순으로 정렬하는 경우 "최소"를 "최대"로 이름을 변경해야 합니다.

해냈습니다. 선택 정렬 알고리즘을 사용하여 Java에서 목록을 정렬했습니다.

Java 선택 정렬의 복잡성은 무엇입니까?

알고리즘을 평가할 때 고려해야 할 세 가지 시간 복잡성이 있습니다:최상의 경우, 최악의 경우 및 평균의 경우.

선택 정렬은 O(n^2)의 최고, 평균 및 최악의 복잡성을 갖습니다. 즉, 목록의 항목 수가 증가하면 알고리즘이 기하급수적으로 길어집니다.

알고리즘의 복잡성 때문에 혼란스럽습니까? Big O 표기법에 대한 2부작 시리즈를 확인하십시오. 이것은 알고리즘의 복잡성을 설명하는 데 사용하는 표기법입니다.

결론

선택 정렬은 데이터 목록을 정렬하는 효율적인 방법입니다. 정렬되지 않은 목록에서 가장 작은 항목을 선택하고 해당 항목을 정렬되지 않은 목록의 시작 부분으로 이동하여 작동합니다. 이 과정은 목록이 정렬될 때까지 반복됩니다.

자바 개발자가 되고 싶습니까? Java 학습 방법 가이드를 확인하십시오. 이 가이드에서 최고의 온라인 코스와 학습 리소스에 대한 최고의 학습 팁과 조언을 찾을 수 있습니다.