Basic Concept3 (삽입 정렬).py

'''
• < 삽입 정렬 > (insertion sort) : <--- 방향으로 삽입
  • 처리되지 않은 데이터를 하니씩 골라 적절한 위치에 삽입
  • swap을 하는데, 모든 인덱스에 대해 실행하는 것이 아니라 '자신의 위치'를 찾기만 하면 ok (버블 정렬과 다름)
  • 선택 정렬에 비해 구현 난이도가 높은 편이지만, 일반적으로 더 효율적으로 작동

  
• 첫 번째 데이터는 그 자체로 정렬이 되어 있다고 판단
  • 두 번째 데이터는 첫 번째 데이터의 오른쪽 / 왼쪽 중 어느쪽으로 들어갈지 판단
  • 세 번째 데이터는 * 1 * 2 * 와 같이 3개의 * 중에 어느쪽으로 들어갈지 판단
  • n 번째 데이터는 가능한 위치가 n가지로 가능함
  
• 시간복잡도는 O(N^2) : 이중 for문 사용
  • 이중 for문 안에서 단순 비교 연산 & 스와핑 연산 -> 제곱 시간 (반복문 안에 별도의 함수가 추가로 호출되는 등의 경우 고려)
  • 현재 리스트의 데이터가 거의 정렬되어 있는 상태라면 매우 빠르게 작동 -> 최선의 경우 O(N)의 시간 복잡도
  
• 삽입 정렬 vs 선택 정렬
  • 삽입 정렬 : 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여 자신의 위치를 찾아 삽입
  • 선택 정렬 : 배열에서 해당 자리를 이미 선택하고 그 자리에 오는 값을 찾는 것
  
• 장점
  • 알고리즘이 단순
  • 대부분의 원소가 거의 정렬되어 있는 경우 매우 효율적일 수 있음
  • 정렬하고자 하는 배열 안에서 교환하는 방식이므로, 다른 메모리 공간을 필요로 하지 않음 (제자리 정렬)
  • 안정 정렬
  • 버블 정렬 < 선택 정렬 < 삽입 정렬 순으로 속도가 빠름
  
• 단점
  • 평균과 최악의 시간복잡도가 O(N^2)으로 비효율적
  • 선택 정렬, 버블 정렬과 마찬가지로 배열의 길이가 길어질수록 비효율적임


'''

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

for i in range(1, len(array)) : # 2번째 원소부터 왼쪽으로 이동(1번 인덱스)
    for j in range(i,0,-1) : # 인덱스 i부터 1까지 1씩 감소하며 반복하는 문법
        if array[j] < array[j-1] : # 한 칸씩 왼쪽으로 이동,  j : 삽입하고자 하는 원소의 인덱스
            array[j], array[j-1] = array[j-1], array[j] 
        else:  # 자기보다 작은 데이터를 만나면 그 위치에서 멈춤
            break
        
print(array)