삽입정렬

알고리즘에서 정렬이란?: 데이터를 특정한 기준에 따라 순서대로 정렬하는 것을 의미한다.  이진검색에서 빠른 알고리즘을 사용하기 위해서는 배열정렬이 필요하고, 다양한 정렬 알고리즘이 중요하다. ps에서는 어떤 정렬방식이 복잡도가 최소화되는지 생각하면서 접근해야 한다.  더보기💡 Tips 1. 정렬의 순서 관계를 정한다2. 첫 번째 조건부터 차례대로 , 같으면 다음 조건으로 넘긴다. 3. 마지막 조건을 바로 리턴한다.   우선, 최악의 경우 O(N^2) 시간복잡도를 깆는 삽입 정렬, 선택 정렬, 버블 정렬에 대해 알아보자 !  1. 삽입정렬 Insert sorting: 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교해 자신의 위치를 찾아 삽입한다. (오름차순)1. 두 번째 원소부..

Priority Queue 큐는 먼저 삽입되는 데이터가 먼저 나가는 FIFO(First In First Out) 형식의 자료구조이다. : 우선순위 큐는, 삽입 순서가 아닌, 우선순위가 높은 데이터가 먼저 나가는 형태의 자료구조로 구현 방식에 따라 running-time이 달라질 수 있다.     Sequeunce-based priority queue(시퀀스 기반 우선순위 큐)1. Selected List(선택정렬) O(n^2): 1.unsorted list와 함께 구현되는 우선순위 큐 방식→ 무순리스트S → 우선순위 큐 P- 우선순위 큐에서 삭제할 때 모든 원소를 비교- 우선순위 큐에 삽입 하는 데 n개의 원소 삽입하므로 O(n)-time- 정렬순서로 삭제하는 데 n + (n-1) + ```  + 1 s..