C 언어로 구현한 삽입 정렬 알고리즘 C++, Java, Python 예
사라 첸
⚡ 스마트 요약
삽입 정렬은 비교 기반의 제자리 정렬 방법으로, 리스트의 요소를 하나씩 정렬해 나갑니다. 안정적이고 적응력이 뛰어나며 구현이 간단하고, 실제 데이터셋의 크기가 작거나 거의 정렬된 데이터에 적합합니다.
삽입 정렬이란 무엇입니까?
삽입 정렬은 비교 정렬 알고리즘 중 하나로, 요소를 하나씩 순회하며 이미 정렬된 영역 내의 올바른 위치에 배치하는 방식으로 요소를 정렬합니다.
각 요소는 이미 정렬된 리스트에 순차적으로 삽입됩니다. 정렬된 리스트의 초기 크기는 1입니다. 삽입 정렬 알고리즘은 외부 루프의 k번째 반복 후에 처음 k개의 요소가 정렬되도록 보장합니다.
삽입 정렬은 결과를 점진적으로 구축하기 때문에 직관적으로 가르칠 수 있고, 디버깅이 용이하며, 복잡한 알고리즘이 측정 가능한 이점 없이 오버헤드만 추가하는 매우 작은 입력에 대한 강력한 기준점이 됩니다.
삽입정렬 알고리즘의 특징
삽입 정렬 알고리즘은 실제 작업 부하에서 동작 방식을 설명하는 다음과 같은 중요한 특징을 가지고 있습니다.
- 이는 안정적인 정렬 기술이므로 동일한 요소의 상대적 순서를 변경하지 않습니다.
- 이 방법은 소규모 데이터 세트에는 효율적이지만, 2차 함수적 증가가 지배적인 대규모 목록에서는 효과적이지 않습니다.
- 삽입 정렬은 적응형 정렬로, 입력 데이터가 부분적으로 정렬되어 있으면 전체 단계 수를 줄입니다. 배열 입력으로 제공되는 이유는 무작위 접근을 통해 내부 루프 동안 일정한 시간 간격의 시프트가 가능하기 때문에 효율성을 높이기 위함입니다.
- 이는 제자리 알고리즘이므로 입력 크기에 비례하는 보조 저장 공간이 필요하지 않습니다.
이러한 특징들을 염두에 두고, 다음 섹션에서는 알고리즘의 모든 단계를 구동하는 핵심 삽입 연산에 대해 설명합니다.
삽입 방법 Opera일?
삽입 정렬 알고리즘에서 삽입 연산은 정렬되지 않은 요소를 정렬하는 데 사용됩니다. 이 연산은 이미 정렬된 리스트에 새 요소를 삽입하면서 기존 정렬 순서를 유지하는 데 도움이 됩니다.
삽입 작업의 의사 코드:
N개 요소로 구성된 목록 A를 생각해 보세요.
// Insert A[N-1] into sorted sublist A[0..N-2] for i = N-1 to 1: if A[i] < A[i-1], then swap A[i] and A[i-1] else stop
위 예시에서는 이미 정렬된 리스트에 새로운 요소 6이 삽입됩니다. 다음 단계는 다음과 같습니다. trac새로운 요소가 왼쪽으로 이동하여 올바른 위치에 도달함에 따라 내부 루프가 생성됩니다.
단계 1) A[5]의 왼쪽 인접 요소인 9 > 6과 비교하여 9와 6의 위치를 바꿉니다. 이제 요소 6이 A[4]로 이동됩니다.
단계 2) 이제 A[4]와 A[3]을 비교해 보면 A[3] > A[4]이므로 6과 8의 위치를 다시 바꿉니다.
단계 3) 이제 A[3]과 A[2]를 비교해 보겠습니다. A[2] > A[3]이므로 7과 6의 위치를 바꿉니다.
단계 4) 우리는 A[1]과 A[2]를 비교합니다. A[1] < A[2]이므로 왼쪽 인접 요소가 더 이상 크지 않습니다. 따라서 6이 올바르게 삽입되었다고 결론짓고 내부 루프를 여기서 종료합니다.
삽입 정렬의 작동 방식
위에서 설명한 삽입 연산은 삽입 정렬의 핵심입니다. 삽입 절차는 모든 요소에 대해 실행되며, 최종적으로 정렬된 리스트를 얻게 됩니다. 정렬된 영역은 매 단계마다 하나의 요소를 추가하며 확장됩니다.
위 그림은 데이터 구조에서 삽입 정렬의 작동 방식을 보여줍니다. 처음에는 정렬된 부분 목록에 요소가 하나만 있습니다. 즉, 4입니다. A[1]을 삽입하면 3이 되고, 정렬된 부분 목록의 크기는 2로 늘어나며, 모든 요소가 배치될 때까지 이 패턴이 계속됩니다.
개념적 흐름이 확립되었으므로, 다음 섹션에서는 구체적인 구현 사례를 보여줍니다. C++, C 및 Python 이를 통해 여러 언어의 반복문 구조를 비교할 수 있습니다.
C++ 삽입정렬 프로그램
The C++ 아래 구현은 두 개의 중첩 루프를 사용합니다. 바깥쪽 루프는 정렬되지 않은 다음 요소를 선택하고, 안쪽 루프는 올바른 위치를 찾을 때까지 왼쪽으로 이동시킵니다.
#include <iostream> using namespace std; int main(){ //unsorted list int unsorted[] = {9,8,7,6,5,4,3,3,2,1}; //size of list int size_unsorted = sizeof(unsorted) / sizeof(unsorted[0]); //printing unsorted list cout << "\nUnsorted: "; for(int i = 0 ; i < size_unsorted ; i++){ cout << unsorted[i] << " "; } int current_element,temp; for(int i = 1; i < size_unsorted; i++){ current_element = unsorted[i]; for(int j = i-1; j >= 0 && unsorted[j] > current_element; j--){ //swapping if current element is lesser temp = unsorted[j+1]; unsorted[j+1] = unsorted[j]; unsorted[j] = temp; } } //printing sorted list cout << "\nSorted: "; for(int i = 0 ; i < size_unsorted ; i++){ cout << unsorted[i] << " "; } return 0; }
출력:
Unsorted: 9 8 7 6 5 4 3 3 2 1 Sorted: 1 2 3 3 4 5 6 7 8 9
C Code 삽입 정렬의 경우
동일한 논리가 C 언어에도 그대로 적용됩니다. 표준 printf 호출은 스트림 출력을 대체하지만 내부 루프 내부의 교환 패턴은 동일합니다. C++ 번역.
#include <stdio.h> int main() { //unsorted list int unsorted[] = {9,8,7,6,5,4,3,3,2,1}; //size of list int size_unsorted = sizeof(unsorted) / sizeof(unsorted[0]); //printing unsorted list printf("\nUnsorted: "); for(int i = 0 ; i < size_unsorted ; i++){ printf("%d ", unsorted[i]); } int current_element, temp; for(int i = 1; i < size_unsorted; i++){ current_element = unsorted[i]; for(int j = i-1; j >= 0 && unsorted[j] > current_element; j--){ //swapping if current element is lesser temp = unsorted[j+1]; unsorted[j+1] = unsorted[j]; unsorted[j] = temp; } } //printing sorted list printf("\nSorted: "); for(int i = 0 ; i < size_unsorted ; i++){ printf("%d ", unsorted[i]); } return 0; }
출력:
Output: Unsorted: 9 8 7 6 5 4 3 3 2 1 Sorted: 1 2 3 3 4 5 6 7 8 9
Python 삽입정렬 프로그램
Python 튜플 스왑을 지원합니다ping 단일 표현식으로 표현되므로 내부 루프는 C보다 더 간결합니다. C++ 동일한 알고리즘 동작을 유지하면서 대응되는 기능을 제공합니다.
#unsorted list unsorted = [9,8,7,6,5,4,3,3,2,1] #size of list size_unsorted = len(unsorted) #printing unsorted list print("\nUnsorted: ", end="") for i in range(size_unsorted): print(unsorted[i], end=" ") for i in range(1, size_unsorted): current_element = unsorted[i] j = i - 1 while j >= 0 and unsorted[j] > current_element: #swapping if current element is lesser unsorted[j+1], unsorted[j] = unsorted[j], unsorted[j+1] j -= 1 #printing sorted list print("\nSorted: ", end="") for i in range(size_unsorted): print(unsorted[i], end=" ")
출력:
Unsorted: 9 8 7 6 5 4 3 3 2 1 Sorted: 1 2 3 3 4 5 6 7 8 9
삽입 정렬의 속성
삽입 정렬이 적합한 도구인지 판단하는 데 도움이 되는 중요한 속성은 다음과 같습니다.
- 온라인 : 삽입 정렬은 요소를 받는 즉시 정렬할 수 있습니다. 이미 정렬된 리스트에 새로운 요소를 추가하더라도 전체 정렬 과정을 다시 실행할 필요 없이 새로 추가된 요소에 대해서만 정렬하면 됩니다.
- 내부: 삽입 정렬 알고리즘의 공간 복잡도는 상수이며 추가 공간을 필요로 하지 않습니다. 이 알고리즘은 제자리에서 요소를 정렬합니다.
- 안정된: 삽입 정렬에서는 값이 같은 요소는 서로 교환하지 않습니다. 예를 들어, 두 요소 x와 y의 값이 같고 정렬되지 않은 리스트에서 x가 y보다 앞에 있다면, 정렬된 리스트에서도 x는 여전히 y보다 앞에 위치합니다. 이것이 삽입 정렬의 안정성입니다.
- 적응 형 : A 정렬 알고리즘 입력 요소 또는 요소의 부분 집합이 이미 정렬되어 있을 때 시간이 덜 걸린다면 적응형 정렬이라고 합니다. 위에서 논의했듯이 삽입 정렬의 최적 실행 시간은 O(N)이고, 최악 실행 시간은 O(N^2)입니다. 삽입 정렬은 적응형 정렬 알고리즘 중 하나입니다.
삽입 정렬의 복잡성
아래의 복잡성 분석에서는 메모리 사용량과 실행 시간을 모두 다루므로 삽입 정렬을 다른 정렬 방식과 비교할 수 있습니다. Bubble 정렬 빠른 정렬.
공간 복잡성
삽입 정렬은 요소를 정렬하기 위해 추가 공간을 필요로 하지 않습니다. 입력 크기에 관계없이 몇 개의 임시 변수만 사용되므로 공간 복잡도는 상수, 즉 O(1)입니다.
시간 복잡성
삽입 정렬은 한 번에 하나의 요소씩 순회하기 때문에 N개의 요소를 정렬하는 데 N-1번의 순회가 필요합니다. 각 순회에서 요소들이 이미 정렬되어 있는 경우에는 교환이 전혀 필요하지 않을 수 있지만, 요소들이 내림차순으로 정렬되어 있는 경우에는 여러 번의 교환이 필요할 수 있습니다.
- 패스 1의 경우 필요한 최소 스왑은 1이고 필요한 최대 스왑은 XNUMX입니다.
- 패스 2의 경우 필요한 최소 스왑은 2이고 필요한 최대 스왑은 XNUMX입니다.
- 패스 N의 경우 필요한 최소 스왑은 XNUMX이고 필요한 최대 스왑은 N입니다.
- 최소 스왑은 0이므로 N번 패스를 반복하는 경우 최적의 시간 복잡도는 O(N)입니다.
- 최대 교환 횟수는 총 (1+2+3+4+…+N) 즉 N(N+1)/2이므로 최악의 시간 복잡도는 O(N^2)입니다.
삽입 정렬의 중요한 시간 복잡도는 다음과 같습니다.
- 최악의 경우 복잡성: O(n^2): 배열을 오름차순으로 정렬해야 할 때 내림차순으로 정렬하는 것은 최악의 시나리오입니다.
- 최고의 사례 복잡성: O(n): 최적의 경우는 배열이 이미 정렬된 경우입니다. 외부 루프는 n번 실행되고 내부 루프는 전혀 실행되지 않습니다. 비교 횟수는 n번뿐이므로 시간 복잡도는 선형입니다.
- 평균 케이스 복잡도: O(n^2): 이는 배열의 요소들이 오름차순이나 내림차순이 아닌 뒤죽박죽 순서로 배열되어 있을 때 발생합니다.
