배열 정렬은 Java 초보자가 수행 방법을 알아야 하는 가장 일반적인 작업 중 하나입니다. 배열이 항상 데이터를 정렬하는 가장 편리한 방법은 아니며 이는 대부분 작은 수에 적용되지만 배열 정렬의 개념은 복잡한 소프트웨어 및 데이터 과학에서 수많은 응용 프로그램을 가지고 있습니다. 이번 포스팅에서는 삽입정렬이 무엇인지 자세히 알아보도록 하겠습니다. 이 개념을 완전히 이해하는 데 도움이 되는 몇 가지 예와 연습 문제를 포함했습니다.
삽입 정렬이란?
기본적으로 삽입 정렬은 개발자가 작은 숫자의 문자열을 구성하는 데 사용하는 알고리즘입니다. 모든 값을 정렬된 스택과 정렬되지 않은 스택의 두 스택으로 나눕니다. 하나씩 "정렬되지 않은" 스택의 숫자가 선택되어 올바른 순서로 배치됩니다. 삽입 정렬의 입력과 출력을 자세히 살펴보겠습니다.
입력: 정렬되지 않은 숫자 요소가 있는 배열 A: A[0,1, n, n-2...].
출력: 동일한 숫자를 포함하지만 완전히 정렬된 배열. 이것은 일반적으로 B: B[0]B[1]...B[n-1]이라고 합니다.
삽입 정렬을 사용하는 몇 가지 방법이 있습니다. 가장 많이 사용되는 방법은 다음과 같습니다.
숫자 정렬(오름차순): [1, 2, 3, 4, 5]
숫자 정렬(내림차순): [5, 4, 3, 2, 1]
알파벳순 정렬: [a, b, c, d]
참고: 빈 배열이나 싱글톤이 있는 경우 기본적으로 정렬된 것으로 간주됩니다.
삽입 정렬 이론 이해
삽입 정렬 뒤의 코드를 탐색하기 전에 비기술적 언어를 사용하여 알고리즘을 분석해 보겠습니다. 오름차순으로 정렬하는 코드를 보여줄 것이기 때문에 이 게시물에서 알고리즘을 단계별로 설명하는 것이 좋습니다. 1단계.arr[1] 와 arr[n]사이 를 반복하며 n일반적으로 10보다 작은 숫자 값입니다. 2단계. 방법을 사용하여 선택한 요소( 로 알려짐 key)를 시퀀스의 이전 숫자와 비교합니다 sort(). 3단계. 모든 요소가 후속 요소보다 작으면 더 큰 값을 찾을 때까지 비교를 반복합니다. 4단계. 작은 값보다 한 위치 큰 값을 교체하여 정렬된 시퀀스를 만듭니다. 5단계. 정렬된 문자열을 얻을 때까지 프로세스를 반복합니다.
기본 배열 정렬
알고리즘은 가장 간단한 Java 작업 중 하나이므로 완전한 초보자도 구현하는 데 큰 어려움이 없습니다. 다음은 배열 정렬에 대한 단계별 가이드입니다.
1. 정렬을 위한 배열 선언
먼저 Java를 사용하여 나중에 표시할 값의 문자열을 만들어 보겠습니다. 삽입 정렬을 사용하려면 배열을 만들어야 합니다. 이를 위해int[]
int[] arrayA = {10, 14, 20, 30};
2. sort_arr을 사용하여 알고리즘 구현
sort_arr 메서드는 삽입 정렬을 구현하는 가장 일반적인 방법 중 하나입니다. 실제로는 다음과 같습니다.
for(int i=0; i< sort_arr.length; ++i){
int j = i;
3. 루프 및 반복자 만들기
삽입 정렬 알고리즘에서 루프를 사용하면 개발자가 모든 요소에 대해 논리를 반복할 필요가 없습니다. 루프를 만드는 것이 복잡해 보이지만 매우 간단합니다. 예를 들면 다음과 같습니다.
for(int i=0; i< sort_arr.length; ++i){
이제 작동하는 루프가 있으므로 모든 요소를 원하는 순서로 정렬하는 반복자를 만들 차례입니다. 이제부터는 이터레이터를 " j"라고 부르겠습니다.
int j = i;
4. "while 루프" 만들기
삽입 정렬의 경우 "while" 루프는 새로 정렬된 배열에 필수적입니다. 오름차순 삽입 정렬을 설정하려면 개발자가 다음 두 가지 조건을 준수해야 합니다.
j에 할당된 값은 0보다 커야 합니다.
에 할당된 값은 인덱스 j-1보다 커야 합니다.j
while 루프의 두 조건이 모두 참이면 배열의 키 값이 인덱스와 같아집니다 j.
5. 배열 정렬
while 루프를 설정한 후 while 루프의 조건 중 하나 또는 둘 모두가 실패할 때까지 j및 값이 교체됩니다. j-1마찬가지로 for 루프 조건도 실패할 때까지 for 루프의 모든 값에 대해 정렬이 반복됩니다. 삽입 정렬 프로세스가 실제로 작동하는 방식은 다음과 같습니다.
삽입 정렬 이면의 수학을 이해하는 것이 중요하지만 실제 소프트웨어 개발에서는 기본 배열의 시퀀스보다 ArrayList를 훨씬 더 많이 정렬하게 됩니다. 다음은 ArrayList 정렬에 대한 단계별 가이드입니다.
Element컬렉션에 속한 항목에 대한 새 클래스를 만듭니다 .
public class Element {
private int id;
public Element(int id) {
this.id = id;
}
컬렉션 내에는 compareTo()방법이 있습니다. 이 방법을 사용하여 두 요소의 ID를 비교할 것입니다.
public int compareTo(Element element) {
int res = 0;
if (this.id < element.getId()) {
res = -1;
}
if (this.id > element.getId()) {
res = 1;
}
return res;
}
}
ArrayList알고리즘을 적용하고 개체를 비교하는 대신 개체를 정렬하는 일부 루프를 만듭니다 .
public static void insertionSortArrayList(List<element> list) {
for (int j = 1; j < list.size(); j++) {
Element current = list.get(j);
int i = j-1;
while ((i > -1) && ((list.get(i).compareTo(current)) == 1)) {
list.set(i+1, list.get(i));
i--;
}
list.set(i+1, current);
}
}
ArrayList아래와 같이 더 많은 요소를 에 추가할 수도 있습니다 .
List<element> list = new ArrayList<>();
// Create elements w/ IDs 0-24
for (int i = 0; i < 25; i++) {
list.add(new Element(i));
}
// To use insertion sort, shuffle the values
Collections.shuffle(list);
이제 정렬할 시간입니다.
// This helps print values before sorting
list.forEach(e -> System.out.print(e.getId() + ", "));
// Sort the list
insertionSortArrayList(list);
System.out.println();
// Display a sorted array
list.forEach(e -> System.out.print(e.getId() + ", "));
이제 입력과 출력을 비교하여 실수가 없는지 확인하겠습니다. 다음은 예제로 사용한 문자열의 비교입니다.
이제 이 정렬 알고리즘에 익숙해졌으므로 이론 및 실제 기술을 테스트할 때입니다. 이론 퀴즈 #1 [1, 4, 6, 8] 배열에 n = 7이라는 새로운 원소를 추가하고 있습니다. 정렬된 숫자 시퀀스를 얻기 위해 필요한 비교 횟수는 얼마입니까? 배열에서 인덱스 n의 최종 값을 나타냅니다. 이론 퀴즈 #2 취업 면접에서 팀장이 정렬 삽입이 비효율적인 방법임을 입증하라고 요청합니다. 숫자 문자열 [0, 3, 6, 8, 9]가 주어지면 정렬에 필요한 실행 시간을 최대화하려면 입력 시퀀스의 순서는 무엇이어야 합니까? 실습 문제 Java용 삽입 정렬을 사용하여 [0, 1, 4, 5, 2, 3, 7, 9, 8] 배열을 오름차순으로 정렬합니다.
결론
삽입 정렬을 파악하는 데 있어 가장 큰 문제는 프로세스가 어떻게 작동하는지 이해하는 것입니다. 익숙해지면 템플릿을 코드로 바꾸는 것은 식은 죽 먹기입니다. 시간이 지남에 따라 관련 연습 문제를 연습하고 다시 방문하는 한 삽입 정렬 속도를 빠르게 향상시킬 수 있습니다.
삽입 정렬의 입력과 출력을 자세히 살펴보겠습니다.
GO TO FULL VERSION