[알고리즘] insertion sort - 작동원리

(2021.10.06)

알고리즘 수업들으면서 정리하기 1탄

2주차 내용

 

---

insertion sort (삽입정렬) - 작동원리

input: sequence of numbers
output: permutation (오름차순)

 

 

pseudocode

Insertion_sort(A,n)
  for j<-2 to n
    do key<-A[j]
       i<- j-1
    while i>0 and A[j]>key
      do A[i+1]<-A[i]
         i<- i-1
    A[i+1]=key

- 입력받은 리스트의 2번째 요소부터 n번째 요소까지 차례대로 key 값으로 설정된다.

- 각 단계에서는 key값 바로 앞부터 한 칸씩 앞으로 가면서 해당 값을 key값과 비교한다. 이때 해당 값이 key값보다 크면 그 값을 뒤에 복사하고, 해당값이 key값보다 작을 때까지 반복한다.

- 해당값이 key값보다 작으면, 그 값 뒤에 key값을 삽입한다. 

 

하나의 for 문이 끝나고 나면, key 값의 왼쪽은 정렬된다.

(교수님께서 배열의 첫번째 인덱스를 0부터 시작하지않으시고 1부터 시작하셔서 약간 헷갈렸다)