[자료구조] Selection Sort(선택정렬), Insersion Sort(삽입정렬)
·
자료구조
이번에 소개할 알고리즘은 정렬 알고리즘인 Selection Sort와 Insersion Sort이다.두 알고리즘은 모두 최악의 경우 O(N2)의 시간복잡도를 갖는 알고리즘이다. Selection Sort란?Selection Sort는 말 그대로 선택하면서 정렬하는 알고리즘이다.과정은 아래와 같다.1. 앞에서부터 순회하면서 가장 큰 수를 발견하면 맨 뒤로 보내고 고정2. 다시 순회하면서 고정된 범위를 제외하고 가장 큰 수를 발견하면 고정 범위의 앞으로 보내고 고정3. 1과 2의 방법을 반복하면서 고정범위 == 배열의 크기가 될 때까지 진행아래는 정렬되는 예시이다.Selection Sort의 시간복잡도(n-1) 회 반복 * (각 반복마다 최소 요구되는 상수시간 + 적절한 인덱스를 찾는 시간)== O(N2)의..