insertion sort java insertion sort algorithm examples
이 자습서에서는 알고리즘, 의사 코드 및 배열 정렬, 단일 연결 및 이중 연결 목록의 예를 포함하여 Java의 삽입 정렬에 대해 설명합니다.
삽입 정렬 알고리즘 기술은 버블 정렬과 유사하지만 약간 더 효율적입니다. 삽입 정렬은 적은 수의 요소가 관련 될 때 더 실행 가능하고 효과적입니다. 데이터 세트가 더 크면 데이터를 정렬하는 데 더 많은 시간이 걸립니다.
=> 여기에서 Java Beginners Guide를 살펴보십시오.
안드로이드를위한 최고의 무료 음악 다운로더 앱
학습 내용 :
Java에서 삽입 정렬 소개
삽입 정렬 기술에서는 목록의 첫 번째 요소가 이미 정렬되었다고 가정하고 두 번째 요소부터 시작합니다. 두 번째 요소는 첫 번째 요소와 비교되고 순서가 맞지 않으면 교체됩니다. 이 프로세스는 모든 후속 요소에 대해 반복됩니다.
일반적으로 삽입 정렬 기술은 각 요소를 이전 요소와 비교하고 요소를 정렬하여 적절한 위치에 배치합니다.
이미 언급했듯이 삽입 정렬 기술은 더 작은 데이터 집합에 더 적합하므로 효율적인 삽입 정렬을 사용하여 요소 수가 적은 배열을 정렬 할 수 있습니다.
삽입 정렬은 연결 목록 데이터 구조를 정렬 할 때 특히 유용합니다. 아시다시피, 연결된 목록에는 다음 요소 (단일 연결 목록)와 이전 요소 (이중 연결 목록)를 가리키는 포인터가 있습니다. 이렇게하면 이전 및 다음 요소를 쉽게 추적 할 수 있습니다.
따라서 연결 목록을 정렬하기 위해 삽입 정렬을 사용하는 것이 더 쉽습니다. 그러나 데이터 항목이 더 많으면 정렬하는 데 많은 시간이 걸립니다.
이 튜토리얼에서는 알고리즘, 의사 코드 및 예제를 포함한 삽입 정렬 기술에 대해 설명합니다. 또한 삽입 정렬을 사용하여 배열, 단일 연결 목록 및 이중 연결 목록을 정렬하는 Java 프로그램을 구현합니다.
삽입 정렬 알고리즘
삽입 정렬 알고리즘은 다음과 같습니다.
1 단계 : K = 1 ~ N-1에 대해 2 ~ 5 단계 반복
2 단계 : 설정 온도 = A (K)
3 단계 : 세트 J = K – 1
4 단계 :
임시로 반복<=A(J)
세트 A (J + 1) = A (J)
세트 J = J – 1
(내부 루프 끝)
5 단계 :
세트 A (J + 1) = 온도
(루프 끝)
6 단계 : 종료
아시다시피 삽입 정렬은 첫 번째 요소가 이미 정렬되었다고 가정하고 두 번째 요소에서 시작됩니다. 위의 단계는 두 번째 요소부터 목록의 모든 요소에 대해 반복되고 원하는 위치에 배치됩니다.
삽입 정렬을위한 의사 코드
삽입 정렬 기술에 대한 의사 코드는 다음과 같습니다.
procedure insertionSort(array,N ) array – array to be sorted N- number of elements begin int freePosition int insert_val for i = 1 to N -1 do: insert_val = array(i) freePosition = i //locate free position to insert the element while freePosition > 0 and array(freePosition -1) > insert_val do: array (freePosition) = array (freePosition -1) freePosition = freePosition -1 end while //insert the number at free position array (freePosition) = insert_val end for end procedure다음으로 삽입 정렬을 사용하여 배열을 정렬하는 방법을 보여주는 그림을 보겠습니다.
삽입 정렬을 사용하여 배열 정렬
배열을 사용한 삽입 정렬의 예를 살펴 보겠습니다.
정렬 할 배열은 다음과 같습니다.
이제 각 패스에 대해 현재 요소를 모든 이전 요소와 비교합니다. 따라서 첫 번째 단계에서는 두 번째 요소부터 시작합니다.
따라서 N 개의 요소를 포함하는 배열을 완전히 정렬하려면 N 개의 패스가 필요합니다.
단위 테스트 대 기능 테스트 대 통합 테스트
위의 그림은 아래와 같이 표 형식으로 요약 할 수 있습니다.
| 통과하다 | 정렬되지 않은 목록 | 비교 | 정렬 된 목록 |
|---|---|---|---|
| 1 | {10,2,6,15,4,1} | {10.2} | {2,10, 6,15,4,1} |
| 두 | {2,10, 6,15,4,1} | {2,10, 6} | {2,6,10,15,4,1} |
| 삼 | {2,6,10,15,4,1} | {2.6, 10.15} | {2,6,10,15,4,1} |
| 4 | {2,6,10,15,4,1} | {2.6, 10.15.4} | {2,4,6,10,15,1} |
| 5 | {2,4,6,10,15,1} | {2,4,6,10,15,1} | {1,2,4,6, 10,15} |
| 6 | {} | {} | {1,2,4,6, 10,15} |
위의 그림에 표시된대로 각 패스가 끝날 때 하나의 요소가 적절한 위치에 배치됩니다. 따라서 일반적으로 N 요소를 적절한 위치에 배치하려면 N-1 패스가 필요합니다.
자바에서 삽입 정렬 구현
다음 프로그램은 Java에서 삽입 정렬의 구현을 보여줍니다. 여기에 삽입 정렬을 사용하여 정렬 할 배열이 있습니다.
import java.util.*; public class Main { public static void main(String() args) { //declare an array and print the original contents int() numArray = {10,6,15,4,1,45}; System.out.println('Original Array:' + Arrays.toString(numArray)); //apply insertion sort algorithm on the array for(int k=1; k=0 && temp <= numArray(j)) { numArray(j+1) = numArray(j); j = j-1; } numArray(j+1) = temp; } //print the sorted array System.out.println('Sorted Array:' + Arrays.toString(numArray)); } } 산출:
원래 배열 : (10, 6, 15, 4, 1, 45)
정렬 된 배열 : (1, 4, 6, 10, 15, 45)
위의 구현에서 정렬은 2부터 시작됩니다.nd배열의 요소 (루프 변수 j = 1)이고 현재 요소는 모든 이전 요소와 비교됩니다. 그런 다음 요소가 올바른 위치에 배치됩니다.
삽입 정렬은 더 작은 배열과 더 적은 패스로 정렬이 완료되는 부분적으로 정렬 된 배열에 대해 효과적으로 작동합니다.
삽입 정렬은 안정적인 정렬입니다. 즉, 목록에서 동일한 요소의 순서를 유지합니다.
삽입 정렬을 사용하여 연결된 목록 정렬
다음 Java 프로그램은 삽입 정렬을 사용하여 단일 연결 목록의 정렬을 보여줍니다.
import java.util.*; class Linkedlist_sort { node head; node sorted; //define node of a linked list class node { int val; node next; public node(int val) { this.val = val; } } //add a node to the linked list void add(int val) { //allocate a new node node newNode = new node(val); //link new node to list newNode.next = head; //head points to new node head = newNode; } // sort a singly linked list using insertion sort void insertion_Sort(node headref) { // initially, no nodes in sorted list so its set to null sorted = null; node current = headref; // traverse the linked list and add sorted node to sorted list while (current != null) { // Store current.next in next node next = current.next; // current node goes in sorted list Insert_sorted(current); // now next becomes current current = next; } // update head to point to linked list head = sorted; } //insert a new node in sorted list void Insert_sorted(node newNode) { //for head node if (sorted == null || sorted.val >= newNode.val) { newNode.next = sorted; sorted = newNode; } else { node current = sorted; //find the node and then insert while (current.next != null && current.next.val 산출:
원래 연결 목록 :
1 8 32 2 10
정렬 된 링크 목록 :
12 8 10 32
위의 프로그램에서 우리는 연결 목록을 생성하고 노드를 추가하고 정렬하는 클래스를 정의했습니다. 단일 연결 목록에는 다음 포인터가 있으므로 목록을 정렬 할 때 노드를 추적하는 것이 더 쉽습니다.
삽입 정렬을 사용하여 이중 연결 목록 정렬
다음 프로그램은 삽입 정렬을 사용하여 이중 연결 목록을 정렬합니다. 이중 연결 목록에는 이전 및 다음 포인터가 모두 있으므로 데이터를 정렬하는 동안 포인터를 업데이트하고 다시 연결하는 것이 쉽습니다.
Windows 10을위한 최고의 MP3 다운로더
class Main { // doubly linked list node static class Node { int data; Node prev, next; }; // return a new node in DLL static Node getNode(int data){ //create new node Node newNode = new Node(); // assign data to node newNode.data = data; newNode.prev = newNode.next = null; return newNode; } // insert a node in sorted DLL static Node insert_Sorted(Node head_ref, Node newNode) { Node current; //list is empty if (head_ref == null) head_ref = newNode; // node is inserted at the beginning of the DLL else if ((head_ref).data >= newNode.data) { newNode.next = head_ref; newNode.next.prev = newNode; head_ref = newNode; } else { current = head_ref; // find the node after which new node is to be inserted while (current.next != null && current.next.data prev points to new node / if ((head_ref) != null) (head_ref).prev = newNode; // move the head to point to the new node / (head_ref) = newNode; return head_ref; } public static void main(String args()) { // create empty DLL Node head = null; // add nodes to the DLL head=addNode(head, 5); head=addNode(head, 3); head=addNode(head, 7); head=addNode(head, 2); head=addNode(head, 11); head=addNode(head, 1); System.out.println( 'Original doubly linked list:'); print_DLL(head); head=insertion_Sort(head); System.out.println('
Sorted Doubly Linked List:'); print_DLL(head); } } 산출:
원래 이중 연결 목록 :
1 11 2 7 3 5
이중 연결 목록 정렬 :
12 3 5 7 11
자주 묻는 질문
Q # 1) Java에서 삽입 정렬이란 무엇입니까?
대답: 삽입 정렬은 더 작은 데이터 세트에 효율적인 Java의 간단한 정렬 기술입니다. 첫 번째 요소는 항상 정렬 된 다음 각 후속 요소가 모든 이전 요소와 비교되고 적절한 위치에 배치된다고 가정합니다.
질문 # 2) 삽입 정렬이 더 나은 이유는 무엇입니까?
대답: 빠른 정렬과 같은 다른 기술이 재귀 호출을 통해 오버 헤드를 추가 할 때 삽입 정렬이 더 작은 데이터 세트의 경우 더 빠릅니다. 삽입 정렬은 다른 정렬 알고리즘보다 비교적 안정적이며 메모리가 덜 필요합니다. 삽입 정렬은 배열이 거의 정렬 된 경우에도 더 효율적으로 작동합니다.
질문 # 3) 삽입 정렬의 용도는 무엇입니까?
대답: 삽입 정렬은 주로 파일 검색, 경로 찾기 및 데이터 압축과 같은 복잡한 프로그램을 빌드하는 컴퓨터 응용 프로그램에서 사용됩니다.
질문 # 4)삽입 정렬의 효율성은 무엇입니까?
대답: 삽입 정렬은 평균 케이스 성능이 O (n ^ 2)입니다. 삽입 정렬의 가장 좋은 경우는 배열이 이미 정렬되어 있고 O (n) 인 경우입니다. 삽입 정렬의 최악의 경우 다시 O (n ^ 2)입니다.
결론
삽입 정렬은 배열 또는 연결 목록에서 작동하는 간단한 정렬 기술입니다. 데이터 세트가 더 작을 때 유용합니다. 데이터 세트가 커질수록이 기술은 느려지고 비효율적입니다.
삽입 정렬은 다른 정렬 기술보다 더 안정적이고 제자리에 있습니다. 정렬 된 요소를 저장하는 데 별도의 구조가 사용되지 않으므로 메모리 오버 헤드가 없습니다.
삽입 정렬은 단일 및 이중 연결 목록 인 연결 목록을 정렬하는 데 효과적입니다. 연결 목록이 포인터를 통해 연결된 노드로 구성되기 때문입니다. 따라서 노드 정렬이 더 쉬워집니다.
다가오는 튜토리얼에서는 Java의 또 다른 정렬 기술에 대해 논의 할 것입니다.
추천 도서
