3. 삽입정렬

이제는 안 보면 섭섭한 동영상부터

삽입정렬 알고리즘은 배열의 앞에서부터 차례대로 비교하면서 적절한 위치를 찾아 삽입하면서 데이터를 정렬한다.

배열이 길어질수록 효율성은 떨어지지만 구현이 간단하고

시간 복잡도는 O(n^2) 이지만 선택정렬이나 버블정렬보다 빠르다.

영상에서 일어나는 일을 그림으로 풀면

삽입정렬의 특징은 반복문을 j번 실행했을 시 배열의 앞에서부터 j+1 항목까지 정렬된다는 점이다. 

무슨 말이냐면 for 문을 2번 실행하고 나면 배열의 세번째 항목까지는 정렬된 상태라는 것

이 점을 이용해서 실제 코드로 구현할 때에는 

j번째 원소와 j+1번째 원소의 크기를 비교하였을 때 j번째 원소가 더 클 경우

① 두 원소의 위치를 교환하고 

② 인덱스 값을 하나 줄여서

③ j번째 원소와 j-1번째 원소의 크기를 비교하고

④ j-1번째 원소보다 j번째 원소가 크다면 더 이상 인덱스 값을 줄여나가면서 비교하지 않고 다음 루프를 실행한다.

이걸 자바 코드로 풀면

int temp = 0;
int j; 
        
for(int i = 0; i < arr.length -1; i++){
    j = i;
            
    while(arr[j] > arr[j+1]){
        temp = arr[j]; 
        arr[j] = arr[j+1];
        arr[j+1] = temp;

        if(j == 0) break;
        else j--;                
    }
}