[#84][자격증] 정보처리기사 실기 알고리즘 (삽입정렬)
정보처리기사 실기 알고리즘 (삽입정렬) |
제시된 순서도는 100보다 작은 30개의 자연수가 배열 AR(30)에 정렬되지 않은 상태로 저장되어 있을 때 이 데이터를 오름차순으로 정렬하는 삽입정렬 알고리즘을 나타낸 것이다.
(배열의 크기가 n일 경우 배열의 요소는 1부터 n까지 구성되는 것으로 한다.)
 |
아직 정렬되지 않은 임의의 데이터를 이미 정렬된 부분의 적절한 위치에 삽입해 가며 정렬하는 방식이다.
![[그림 8-2] 정렬되지 않은 데이터](http://terms.naver.com/imageDetail.nhn?docId=2270436&imageUrl=http%3A%2F%2Fdbscthumb.phinf.naver.net%2F3523_000_1%2F20141020113521435_NDB0NLBWN.jpg%2Fka7_126_i1.jpg%3Ftype%3Dm4500_4500_fst_n%26wm%3DY){kind=small}
[그림 8-2] 정렬되지 않은 데이터
① 두 번째 데이터 11과 바로 앞에 위치한 15의 크기를 비교한다. 두 번째 데이터가 작으므로 15를 한 칸 뒤로 보내고 11을 15 앞에 위치시킨다.
② 세 번째 데이터인 1과 앞에 위치한 11, 15의 크기를 비교한다. 1이 가장 작으므로 11과 15를 한 칸씩 뒤로 보내고 1을 가장 앞에 위치시킨다.
③ 네 번째 데이터인 3과 앞에 위치한 1, 11, 15의 크기를 비교한다. 3은 1보다 크고 11, 15보다 작으므로 11과 15를 한 칸씩 뒤로 보내고 3을 11 앞에 위치시킨다.
④ 마지막 데이터인 8과 앞에 위치한 1, 3, 11, 15의 크기를 비교한다. 1, 3보다 크고 11, 15보다 작으므로 11과 15를 한 칸씩 뒤로 보내고 8을 11 앞에 위치시킨다.
⑤ 데이터들에 대한 정렬이 완료된다.
시간복잡도
- 최악의 경우(거꾸로 정렬된 경우 O(n²)
- 이미 정렬된 경우 O(n)
공간복잡도 = O(n) , 주어진 배열 안에서만 진행한다.
----------------------------정답----------------------------------
- 최악의 경우(거꾸로 정렬된 경우 O(n²)
- 이미 정렬된 경우 O(n)
공간복잡도 = O(n) , 주어진 배열 안에서만 진행한다.
----------------------------정답----------------------------------
① m = 2
② w = m - 1
③ AR(w+1) = AR(w)
④ w >= 1
⑤ AR(w+1)
-------------------------------------------------------------------
C++구현
#include <iostream>
#include <time.h>
using namespace std;
int main() {
int m, w, KEY, AR[31];
//랜덤함수
srand(time(NULL));
for (int i = 1; i <= 30; i++) {
AR[i] = rand();
}
//알고리즘 구현부
for (m = 2; m <= 30; m++) {
//KEY값, w설정
KEY = AR[m];
w = m - 1;
while (w >= 1) {
if (KEY < AR[w]) {
//뒤로 한 칸씩 땡기기
AR[w + 1] = AR[w];
w = w - 1;
}
else {
break;
}
AR[w + 1] = KEY;
}
}
//출력
for (int i = 1; i <= 30; i++) {
cout << AR[i] << endl;
}
return 0;
}
| cs |
정리한 코드
#include <iostream>
#include <time.h>
using namespace std;
int KEY, m, w;
void insertionSort(int arr[]) {
for (m = 2; m <= 30; m++) {
KEY = arr[m];
w = m - 1;
while (w >= 1 && KEY < arr[w]) {
arr[w + 1] = arr[w];
w--;
}
arr[w + 1] = KEY;
}
}
int main() {
int AR[31];
//랜덤함수
srand(time(NULL));
for (int i = 1; i <= 30; i++) {
AR[i] = rand();
}
insertionSort(AR);
//출력
for (int i = 1; i <= 30; i++) {
cout << AR[i] << endl;
}
return 0;
}
| cs |
댓글
댓글 쓰기