뽕구의 개발일지

삽입 정렬선택, 버블, 삽입 정렬 다음으로 세번째 순서, 삽입 정렬입니다.삽입 정렬은 아래와 같이 이해하였습니다. "원소를 이전 순서에 이미 정렬된 원소들과 비교해 작은 수가 되는 위치에 넣는다."  최악의 경우 O(N^2) 시간 복잡도를 갖지만 이전 인덱스의 수들이 정렬이 되어있다는 가정 때문에 모든 원소를 비교하지 않아 정렬 중 성능이 좋은편이라고 합니다. 나동빈 님의 알고리즘 강좌를 보고 구현해보았습니다.구현#include #include using namespace std;int main() { int j, temp; int arr[10] = { 1,10,5,8,7,6,4,3,2,9 }; //비교 횟수 == 원소 갯수 -1 == i = 9 for (int i = 0; i arr[j + 1]) ..

백준 #2751 수 정렬하기https://www.acmicpc.net/problem/2751 버블 정렬 공부하면서 이번 문제는 버블정렬로 풀어야지! 했는데 계속 시간 초과가 났습니다. 분명히 2750 문제랑 똑같았다고 생각했는데 원인을 찾아보니 입력 수가 1,000,000 으로 늘어난 걸 캐치를 못했어요 ㅠㅠ그래서 오래 걸리는 버블이랑 선택 정렬로 풀어도 #2750은 풀렸는데 #2751은 안풀렸습니다. 그래서 이번에는 C++ STL 함수 sort()를 사용했습니다. "algorithm.h" 에 포함되어 있는 함수이니까 #inlcude 해주세요~ Sort() 는 퀵 정렬을 기반으로 힙 정렬과 삽입 정렬이 혼합된 방식으로 구현되어 있다고 하네요.따라서 O(N^2) 시간 복잡도를 갖는 퀵 정렬과 다르게 O(..