[이것이 코딩 테스트다 with Python]_22_삽입정렬

220208 작성

<본 블로그는 『이것이 취업을 위한 코딩 테스트다』 의 youtube를 참고해서 공부하며 작성하였습니다>

https://www.youtube.com/watch?v=DRkL5EBZ7KY&list=PLVsNizTWUw7H9_of5YCB0FmsSc-K44y81&index=22 

 

 

 

 

 

 

1. 삽입 정렬

: 처리되지 않은 데이터를 하나씩 골라 적절한 위치에 삽입

: 선택 정렬에 비해 구현 난이도가 높지만 효율적

 

1) 첫 번째 수를 기준으로 두 번째 수가 앞으로 갈지, 뒤로 갈지 판단

2) 그다음 세 번째 수가 앞 두 개의 수에서 어디로 갈지 판단

3) 그다음 네 번째 수가 앞 세 개의 수에서 어디로 갈지 판단

....

이런 과정 반복

 

• python

array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]

for i in range(1, len(array)) :
    for j in range(i, 0, -1) :  # 인덱스 0으로 거꾸로 가기!
        if array[j] < array[j-1] : # 작으면 왼쪽!
            array[j], array[j-1] = array[j-1], array[j]
        else :
            break # 순서가 맞다면 멈추기
print(array)

• c++

#include <bits/stdc++.h>

using namespace std;

int n = 10;
int arr[10] = {7, 5, 9, 0, 3, 1, 6, 2, 4, 8};

int main(void) {
    for (int i = 1; i < n; i++) {
        // 인덱스 i부터 1까지 감소하며 반복하는 문법
        for (int j = i; j > 0; j--) {
            // 한 칸씩 왼쪽으로 이동
            if (arr[j] < arr[j - 1]) {
                swap(arr[j], arr[j - 1]);
            }
            // 자기보다 작은 데이터를 만나면 그 위치에서 멈춤
            else break;
        }
    }
    for(int i = 0; i < n; i++) {
        cout << arr[i] << ' ';
    }
}

• java

import java.util.*;

public class Main {

    public static void main(String[] args) {

        int n = 10;
        int[] arr = {7, 5, 9, 0, 3, 1, 6, 2, 4, 8};

        for (int i = 1; i < n; i++) {
            // 인덱스 i부터 1까지 감소하며 반복하는 문법
            for (int j = i; j > 0; j--) {
                // 한 칸씩 왼쪽으로 이동
                if (arr[j] < arr[j - 1]) {
                    // 스와프(Swap)
                    int temp = arr[j];
                    arr[j] = arr[j - 1];
                    arr[j - 1] = temp;
                }
                // 자기보다 작은 데이터를 만나면 그 위치에서 멈춤
                else break;
            }
        }

        for(int i = 0; i < n; i++) {
            System.out.print(arr[i] + " ");
        }
    }

}

 

 

 

 

 

2. 삽입 정렬 시간 복잡도

: 현재 리스트가 거의 정렬 되어있다면 매우 빠르게 동작

: 최선의 시간 복잡도는 O(N)

=> 반복문 두 번 중첩

=> O(N^2)