반응형
삽입정렬이란?
주어진 원소들을 하나씩 뽑은 후, 나열된 원소들이 항상 정렬된 형태를 가지도록 뽑은 원소를 바른 위치에 삽입하여 나열하는 정렬방식
삽입정렬의 특징
1. 입력이 거의 정렬된 경우 빠른 수행시간을 보인다.
2. 안정적인 정렬이다.
- 두 데이터가 정렬되지 않은 경우에만 교환이 일어난다.
3. 제자리 정렬이다.
- 데이터를 움직이는 경우는 두원소를 서로 교환하는 경우밖에 없으므로, 데이터가 저장된 공간 이외에 별도 공간을 상수 개만 사용한다.
뽑은 원소를 어떻게 바른 위치에 삽입할 수 있을까?
- 컴퓨터에서는 나열된 원소를 하나씩 차례대로 비교하면서 삽입된 위치를 찾을 수 있다.
#include<stdio.h>
int temp, n= 10;
InsertSort(int A[],int n){
for(int i = 0; i<n; i++){
for(int j = i; j>0 && A[j]<A[j-1]; j--){ //정렬된 원소들과 비교
temp = A[j]; // 원소를 서로 교환
A[j] = A[j-1];
A[j-1] = temp;
}
printf("%d단계를 출력 :", i);
for(int k=0; k<n; k++){ //정렬되는 과정 출력
printf("%d ", A[k]);
}
printf("\n");
}
}
int main(){
int n = 10; //원소의 개수
int A[10]; //정렬 선언
printf("입력하세요 :");
for(int i= 0; i<n; i++){ //정렬할 배열 입력하기
scanf("%d",&A[i]);
}
InsertSort(A, n);
for(int i=0; i<n; i++){
printf("%d ", A[i]); //정렬완료
}
}
/*
입력하세요 :5 4 3 2 1
0단계를 출력 :5 4 3 2 1
1단계를 출력 :4 5 3 2 1
2단계를 출력 :3 4 5 2 1
3단계를 출력 :2 3 4 5 1
4단계를 출력 :1 2 3 4 5
1 2 3 4 5
--------------------------------
Process exited after 3.268 seconds with return value 0
계속하려면 아무 키나 누르십시오 . . .
*/정렬 공부하면서 느꼈던 건데 내 입장에서는 단순하게 오름차 or 내림차순으로 정렬하면 되니까 쉽다고 생각되는데 컴퓨터로 구현해보면 생각보다 복잡함.(대충알면 쉽다고 느껴지는데 공부할 수록 때려치고 싶음.) 특히 자료구조 시험을 치면서 느낀건데 대충 정렬 안되어있는 상태에서 오름차순으로 정렬할때까지 몇단계가 필요한가? 이런 문제는 비교적 쉬운데 초기 상태에 숫자들이 많다거나 아니면 어떤수가 어디에 위치되어 있는 경우는 몇단계인가? 이런식의 질문은 많이 화가남. 특히 중간에서 계산실수하면 멘탈나가는거임. 신기한 건 나이를 먹어갈 수록 사칙연산을 못하는 거 같은 느낌 이상하다. 왜 반비례하는 건지 사칙연산은 초등학교 2학년때 가장 잘했던 거 같다.
반응형
'2019~2020 > 자료구조' 카테고리의 다른 글
| 선택정렬이란 (0) | 2019.09.11 |
|---|---|
| 버블정렬 (0) | 2019.09.11 |
| 최댓값 찾기 알고리즘 (0) | 2019.09.03 |
| bfs-dfs (0) | 2019.08.26 |
| 행렬을 이용한 BFS (c) (0) | 2019.08.20 |