Home-theater-designers
삽입 정렬은 정렬된 하위 목록을 활용하고 전체 목록이 정렬될 때까지 정렬되지 않은 목록의 값을 계속 추가하여 작동하는 기술입니다.
알고리즘은 첫 번째 목록 항목을 정렬된 하위 목록으로 시작합니다. 그런 다음 다음 숫자를 첫 번째 숫자와 비교합니다. 더 크면 첫 번째 인덱스에 삽입됩니다. 그렇지 않으면 인덱스에 남아 있습니다.
그런 다음 세 번째 값을 다른 두 값과 비교한 다음 올바른 인덱스에 삽입합니다. 이 프로세스는 전체 목록이 정렬될 때까지 계속됩니다.
삽입 정렬 자세히 살펴보기
위의 설명이 이해가 되지 않을 수 있습니다. 예는 훨씬 더 잘 이해하는 데 도움이 됩니다.
[39, 6, 2, 51, 30, 42, 7] 목록이 있다고 가정합니다.
알고리즘은 정렬된 하위 목록의 첫 번째 값으로 39를 식별합니다. 그런 다음 평가는 두 번째 위치로 이동합니다.
관련 항목: 동적 프로그래밍: 예제, 일반적인 문제 및 솔루션
그런 다음 6은 39와 비교됩니다. 6은 39보다 작으므로 첫 번째 위치에 6이 삽입되고 두 번째 위치에 39가 삽입됩니다. 새 목록 순서는 첫 번째 패스 이후입니다.
[6, 39, 2, 51, 30, 42, 7]
평가는 이제 세 번째 위치로 이동합니다. 2는 마지막 두 숫자와 비교하여 올바른 위치에 삽입됩니다. 새 목록 순서는 두 번째 패스 이후입니다.
[2, 6, 39, 51, 30, 42, 7]
세 번째 패스의 경우 목록 순서는 다음과 같습니다.
[2, 6, 39, 51, 30, 42, 7]
전체 목록이 정렬될 때까지 프로세스가 반복됩니다.
이러한 작업을 요약한 아래 다이어그램을 참조하십시오.
알고리즘 분석
삽입 정렬의 시간 복잡도는 O(n2), 처럼 버블 정렬 . 최악의 시나리오에서 비교 횟수는 1에서 (n-1)까지의 모든 정수의 합으로 2차 합을 제공합니다.
코드 구현
아래의 Python 및 Java 코드는 삽입 정렬 방법을 구현하는 방법을 보여줍니다.
파이썬:
def insertionSort(mylist):
for step in range(1, len(mylist)):
current_element = mylist[step]
position = step
while position > 0 and mylist[position - 1] > current_element:
mylist[position] = mylist[position - 1]
position = position - 1
mylist[position] = current_element자바:
void insertionSort(int[] myarray) {
int n = myarray.length;
for (int x = 1; x int key = myarray[x];
int y = x-1;
while ( (y > -1) && ( myarray [y] > key ) ) {
myarray [y+1] = myarray [y];
y--;
}
myarray[y+1] = key;
}
} 의사 코드로 더 나은 코딩
위의 코드 예제는 다른 언어로 이 알고리즘을 작성하기 위해 참조할 수 있는 의사 코드 없이 제공되었습니다. 대부분의 프로그래머(저자 포함)는 프로그램 작동 방식에 대해 '속삭이는 소리'를 들은 후 키보드로 실행하는 것을 좋아합니다.
이 접근 방식은 불행히도 프로그램 논리가 더 복잡해짐에 따라 오류가 발생하기 쉽습니다. 의사 코드를 사용하는 방법을 학습하여 프로그래밍 게임의 수준을 어떻게 높이고 싶습니까?
공유하다 공유하다 트위터 이메일 Pseudocode란 무엇이며 어떻게 더 나은 개발자를 만들 수 있습니까?프로그래밍을 배우기 어려우신가요? 의사 코드를 학습하여 코드를 파악하십시오. 그러나 의사 코드는 무엇이며 실제로 도움이 될 수 있습니까?
다음 읽기 관련 항목- 프로그램 작성
- 자바
- 파이썬
- 코딩 튜토리얼
Jerome은 MakeUseOf의 스태프 라이터입니다. 그는 프로그래밍 및 Linux에 대한 기사를 다룹니다. 그는 또한 암호화폐 애호가이며 항상 암호화폐 산업을 주시하고 있습니다.
내 아이폰 찾기 위치를 찾을 수 없습니다제롬 데이비슨이 참여한 작품 더보기
뉴스레터 구독
뉴스레터에 가입하여 기술 팁, 리뷰, 무료 전자책 및 독점 거래를 확인하십시오!
구독하려면 여기를 클릭하세요.