삽입정렬
-
3. 삽입정렬전공 공부/알고리즘 2019. 3. 12. 16:11
이제는 안 보면 섭섭한 동영상부터 삽입정렬 알고리즘은 배열의 앞에서부터 차례대로 비교하면서 적절한 위치를 찾아 삽입하면서 데이터를 정렬한다.배열이 길어질수록 효율성은 떨어지지만 구현이 간단하고시간 복잡도는 O(n^2) 이지만 선택정렬이나 버블정렬보다 빠르다. 영상에서 일어나는 일을 그림으로 풀면 삽입정렬의 특징은 반복문을 j번 실행했을 시 배열의 앞에서부터 j+1 항목까지 정렬된다는 점이다. 무슨 말이냐면 for 문을 2번 실행하고 나면 배열의 세번째 항목까지는 정렬된 상태라는 것 이 점을 이용해서 실제 코드로 구현할 때에는 j번째 원소와 j+1번째 원소의 크기를 비교하였을 때 j번째 원소가 더 클 경우① 두 원소의 위치를 교환하고 ② 인덱스 값을 하나 줄여서③ j번째 원소와 j-1번째 원소의 크기를 비..