삽입 정렬

🥕 [ 백준 2750, 2751 ] 수 정렬하기 문제 링크 url : https://www.acmicpc.net/problem/2750 2750번: 수 정렬하기 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수 주어진다. 이 수는 절댓값이 1,000보다 작거나 같은 정수이다. 수는 중복되지 않는다. www.acmicpc.net 문제 링크 url : https://www.acmicpc.net/problem/2751 2751번: 수 정렬하기 2 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 절댓값이 1,000,000보다 작거나 같은 정수이다. 수는 중복되지 않는다. www.acmicpc...

[삽입 정렬] 정렬되어 있는 자료 배열과 비교해서, 정렬 위치를 찾는다. 버블 정렬은 큰숫자를 뒤로 밀어내며 정렬하는 반면, 삽입 정렬은 정렬이 이미 되어있는 앞부분과 나 자신을 비교해서, 나 자신이 어디에 삽입되면 되는지를 찾는다. 데이터가 거의 정렬되어있다면 매우 효율적인 알고리즘이다. 정렬되어 있는 배열과 비교할 때도, 자기보다 작은 데이터를 만나면 그 위치에서 멈추면 되므로 모든 데이터를 다 볼 필요가 없다. 시간 복잡도는 $O(N^2)$ 이며, 최선의 경우 $O(N)$ 을 갖는다. 빨간 박스는 이미 정렬되어 있는 부분을 말한다. 1. 처음에는 자료에서 두 번째 요소를 가지고 이전 데이터와 비교를 시작하며 빨간색 박스를 찾는다. 2. 정렬되어있지 않은 값을 하나하나 정렬된 배열(빨간..