insertion sort c with examples
고전적인 예를 사용하여 삽입 정렬에 대한 심층 조사.
삽입 정렬은 우리가 직접 카드를 사용하는 방식으로 볼 수있는 정렬 기술입니다. 카드를 데크에 삽입하거나 제거하는 방식, 삽입 정렬도 비슷한 방식으로 작동합니다.
삽입 정렬 알고리즘 기술은 버블 정렬 및 선택 정렬 기술보다 효율적이지만 Quicksort 및 Merge 정렬과 같은 다른 기술보다 덜 효율적입니다.
=> 여기에서 최고의 C ++ 교육 자습서를 확인하십시오.
학습 내용 :
개요
삽입 정렬 기법에서는 두 번째 요소부터 시작하여 첫 번째 요소와 비교하여 적절한 위치에 배치합니다. 그런 다음 후속 요소에 대해이 프로세스를 수행합니다.
각 요소를 모든 이전 요소와 비교하고 요소를 적절한 위치에 배치하거나 삽입합니다. 삽입 정렬 기술은 요소 수가 더 적은 배열에 더 적합합니다. 연결 목록을 정렬하는데도 유용합니다.
연결 목록에는 다음 요소에 대한 포인터 (단일 연결 목록의 경우)와 이전 요소에 대한 포인터 (이중 연결 목록의 경우)도 있습니다. 따라서 연결 목록에 대한 삽입 정렬을 구현하는 것이 더 쉬워집니다.
C ++에서 char를 int로 변환
이 튜토리얼에서 삽입 정렬에 대한 모든 것을 살펴 보겠습니다.
일반 알고리즘
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 whilefreePosition> 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 | {12,3,5,10,8,1} | {12.3} | {3,12,5,10,8,1} |
| 두 | {3,12,5,10,8,1} | {3,12,5} | {3,5,12,10,8,1} |
| 삼 | {3,5,12,10,8,1} | {3,5,12,10} | {3,5,10,12,8,1} |
| 4 | {3,5,10,12,8,1} | {3,5,10,12,8} | {3,5,8,10,12,1} |
| 5 | {3,5,8,10,12,1} | {3,5,8,10,12,1} | {1,3,5,8,10,12} |
| 6 | {} | {} | {1,3,5,8,10,12} |
위의 그림과 같이 2로 시작합니다.nd첫 번째 요소는 항상 정렬되어 있다고 가정합니다. 따라서 두 번째 요소를 첫 번째 요소와 비교하고 두 번째 요소가 첫 번째 요소보다 작 으면 위치를 바꿉니다.
이 비교 및 교체 프로세스는 두 요소를 적절한 위치에 배치합니다. 다음으로 세 번째 요소를 이전 (첫 번째 및 두 번째) 요소와 비교하고 동일한 절차를 수행하여 세 번째 요소를 적절한 위치에 배치합니다.
이러한 방식으로 각 패스에 대해 그 자리에 하나의 요소를 배치합니다. 첫 번째 패스에서는 두 번째 요소를 그 자리에 배치합니다. 따라서 일반적으로 N 요소를 적절한 위치에 배치하려면 N-1 패스가 필요합니다.
다음으로 C ++ 언어로 구현 된 삽입 정렬 기술을 보여줍니다.
C ++ 예
#include using namespace std; int main () { int myarray[10] = { 12,4,3,1,15,45,33,21,10,2}; cout<<'
Input list is
'; for(int i=0;i<10;i++) { cout < 산출:
Windows 10에서 BIOS를 업데이트하는 방법
입력 목록은
12 4 3 1 15 45 33 21 10 2
정렬 된 목록은
12 34 10 12 15 21 33 45
다음으로 삽입 정렬 기술의 Java 구현을 살펴 보겠습니다.
자바 예
public class Main { public static void main(String[] args) { int[] myarray = {12,4,3,1,15,45,33,21,10,2}; System.out.println('Input list of elements ...'); for(int i=0;i<10;i++) { System.out.print(myarray[i] + ' '); } for(int k=1; k=0 && temp <= myarray[j]) { myarray[j+1] = myarray[j]; j = j-1; } myarray[j+1] = temp; } System.out.println('
sorted list of elements ...'); for(int i=0;i<10;i++) { System.out.print(myarray[i] + ' '); } } } 산출:
요소 목록 입력…
12 4 3 1 15 45 33 21 10 2
정렬 된 요소 목록…
12 34 10 12 15 21 33 45
두 구현 모두에서 우리는 2에서 정렬을 시작하는 것을 볼 수 있습니다.nd배열의 요소 (루프 변수 j = 1)를 사용하고 현재 요소를 모든 이전 요소와 반복적으로 비교 한 다음 현재 요소가 모든 이전 요소와 순서가 맞지 않으면 올바른 위치에 배치되도록 요소를 정렬합니다.
삽입 정렬이 가장 잘 작동하며 배열이 부분적으로 정렬 된 경우 더 적은 패스로 완료 할 수 있습니다. 그러나 목록이 커지면 성능이 저하됩니다. 삽입 정렬의 또 다른 장점은 목록에서 동일한 요소의 순서를 유지하는 안정적인 정렬이라는 것입니다.
삽입 정렬 알고리즘의 복잡성 분석
위의 의사 코드와 그림에서 삽입 정렬은 버블 정렬 또는 선택 정렬과 비교할 때 효율적인 알고리즘입니다. for 루프와 현재 조건을 사용하는 대신 배열이 정렬 될 때 더 이상 추가 단계를 수행하지 않는 while 루프를 사용합니다.
인터뷰에서 요구되는 기본 자바 프로그램 pdf
그러나 정렬 된 배열을 삽입 정렬 기술에 전달하더라도 외부 for 루프를 계속 실행하므로 이미 정렬 된 배열을 정렬하려면 n 개의 단계가 필요합니다. 이것은 삽입 정렬의 최고의 시간 복잡도를 N의 선형 함수로 만듭니다. 여기서 N은 배열의 요소 수입니다.
따라서 삽입 정렬 기술의 다양한 복잡성은 다음과 같습니다.
최악의 시간 복잡성 O (n 2) 최상의 경우 시간 복잡성 의 위에) 평균 시간 복잡성 O (n 2) 공간 복잡성 O (1)
이러한 복잡성에도 불구하고 삽입 정렬이 버블 정렬 및 선택 정렬과 같은 다른 정렬 기술과 비교할 때 가장 효율적인 알고리즘이라는 결론을 내릴 수 있습니다.
결론
삽입 정렬은 지금까지 설명한 세 가지 기술 중 가장 효율적입니다. 여기서는 첫 번째 요소가 정렬 된 다음 모든 요소를 이전 요소와 반복적으로 비교 한 다음 현재 요소를 배열의 올바른 위치에 배치한다고 가정합니다.
이 튜토리얼에서 삽입 정렬에 대해 논의하는 동안 1의 증분을 사용하여 요소를 비교하고 또한 연속적임을 알았습니다. 이 기능을 사용하면 정렬 된 목록을 가져 오기 위해 더 많은 패스가 필요합니다.
다음 자습서에서는 선택 정렬보다 향상된 '셸 정렬'에 대해 설명합니다.
쉘 정렬에서는 '증가'또는 '간격'이라는 변수를 도입하여 목록을 '간격'하는 연속되지 않은 요소를 포함하는 하위 목록으로 나눕니다. 셸 정렬은 삽입 정렬에 비해 패스가 더 적고 더 빠릅니다.
앞으로의 자습서에서는 데이터 목록을 정렬하기 위해 '분할 및 정복'전략을 사용하는 '빠른 정렬'및 '병합 정렬'의 두 가지 정렬 기술에 대해 알아 봅니다.
=> 여기에서 초보자 C ++ 교육 가이드를 확인하십시오.
추천 도서