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 ++ 언어로 구현 된 삽입 정렬 기술을 보여줍니다.
Windows 10에서 BIOS를 업데이트하는 방법
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 < 산출:
입력 목록은
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)를 사용하고 현재 요소를 모든 이전 요소와 반복적으로 비교 한 다음 현재 요소가 모든 이전 요소와 순서가 맞지 않으면 올바른 위치에 배치되도록 요소를 정렬합니다.
삽입 정렬이 가장 잘 작동하며 배열이 부분적으로 정렬 된 경우 더 적은 패스로 완료 할 수 있습니다. 그러나 목록이 커지면 성능이 저하됩니다. 삽입 정렬의 또 다른 장점은 목록에서 동일한 요소의 순서를 유지하는 안정적인 정렬이라는 것입니다.
인터뷰에서 요구되는 기본 자바 프로그램 pdf
삽입 정렬 알고리즘의 복잡성 분석
위의 의사 코드와 그림에서 삽입 정렬은 버블 정렬 또는 선택 정렬과 비교할 때 효율적인 알고리즘입니다. for 루프와 현재 조건을 사용하는 대신 배열이 정렬 될 때 더 이상 추가 단계를 수행하지 않는 while 루프를 사용합니다.
그러나 정렬 된 배열을 삽입 정렬 기술에 전달하더라도 외부 for 루프를 계속 실행하므로 이미 정렬 된 배열을 정렬하려면 n 개의 단계가 필요합니다. 이것은 삽입 정렬의 최고의 시간 복잡도를 N의 선형 함수로 만듭니다. 여기서 N은 배열의 요소 수입니다.
따라서 삽입 정렬 기술의 다양한 복잡성은 다음과 같습니다.
최악의 시간 복잡성 O (n 2) 최상의 경우 시간 복잡성 의 위에) 평균 시간 복잡성 O (n 2) 공간 복잡성 O (1)
이러한 복잡성에도 불구하고 삽입 정렬이 버블 정렬 및 선택 정렬과 같은 다른 정렬 기술과 비교할 때 가장 효율적인 알고리즘이라는 결론을 내릴 수 있습니다.
결론
삽입 정렬은 지금까지 설명한 세 가지 기술 중 가장 효율적입니다. 여기서는 첫 번째 요소가 정렬 된 다음 모든 요소를 이전 요소와 반복적으로 비교 한 다음 현재 요소를 배열의 올바른 위치에 배치한다고 가정합니다.
이 튜토리얼에서 삽입 정렬에 대해 논의하는 동안 1의 증분을 사용하여 요소를 비교하고 또한 연속적임을 알았습니다. 이 기능을 사용하면 정렬 된 목록을 가져 오기 위해 더 많은 패스가 필요합니다.
다음 자습서에서는 선택 정렬보다 향상된 '셸 정렬'에 대해 설명합니다.
쉘 정렬에서는 '증가'또는 '간격'이라는 변수를 도입하여 목록을 '간격'하는 연속되지 않은 요소를 포함하는 하위 목록으로 나눕니다. 셸 정렬은 삽입 정렬에 비해 패스가 더 적고 더 빠릅니다.
앞으로의 자습서에서는 데이터 목록을 정렬하기 위해 '분할 및 정복'전략을 사용하는 '빠른 정렬'및 '병합 정렬'의 두 가지 정렬 기술에 대해 알아 봅니다.
=> 여기에서 초보자 C ++ 교육 가이드를 확인하십시오.
추천 도서