![]()
제목 : 삽입 정렬 (Insertion Sort) - with Java기초적인 정렬 중, $ O(N^2) $ 를 가진 방법이다.바로 직전에 선택 정렬 (Selection Sort) 에 대해서 주제를 다뤘는데,선택 정렬과 삽입 정렬은, 현재 인덱스 이전이 완벽하게 정렬 되어 있는가? 로 나뉜다고 생각한다.선택 정렬의 경우, 현재 인덱스 이전이 완벽하게 정렬되어 있다.삽입 정렬의 경우, 현재 인덱스 이전 요소들에 한하여, 해당 영역은 정렬되어 있다.하지만, 결과적으로 봤을 때 완벽하게 정렬되어 있지 않다.또 다른 관점에서 둘을 비교해 보자.Selection Sort 의 경우, i 번째 요소에 넣기 위한 "결과론적으로 완벽한" 요소를 찾는다.Insertion Sort 의 경우, i 번째 요소는 1 번째 부터,..
![]()
제목 : 선택 정렬 (Selection sort) 에 대하여 - With Java가장 기초적인 정렬 중 하나이다.시간 복잡도는 $ O(N^2) $ 이다.나는 선택 정렬을 설명하기 위해 이러한 상황을 예시로 들고 싶다.상황 : 선생님이 걷어온 쪽지 시험을 학생의 고유 번호대로 상승하도록 정렬 해 달라고 부탁하셨다.그렇다면, 약 40장 정도가 존재한다고 가정한다면 나는 어떻게 정렬해야 할까?믈론 사람마다 종이를 순서대로 나열하는 데 있어 다른 방식이 있을 수도 있다.하지만, 1 번부터 찾고 왼쪽에 둔다. 그 다음 2 번을 찾아 1 번의 밑에 둔다.그리고 또 3 번을 찾고 2번의 밑에 둔다. 그리고 4번도...이러한 방식으로 1 번부터 40 번 까지 정렬 할 수 있다.이 방식이 바로 선택 정렬(Selectio..
