C - insertion sort

insertion sort는 한 기준점을 중심으로 오른쪽에는 unsorted list, 왼쪽에는 sorted list가 있는 형식입니다.

오른쪽의 정렬되지 않은 element를 하나씩 왼쪽으로 옮기면서 부분적으로 리스트를 정렬하고, 결론적으로 기준점이 맨 끝에 갔을때 (오른쪽에 element가 없을 때) sorting이 완료됩니다.

 

#include <stdio.h>
#include <stdlib.h>
#define max 6

int main() 
{
  // sample input: 5 12 6 80 2 15
  int key, now, temp;
  int A[] = { 5, 12, 6, 80, 2, 15};

  printf("unsorted: ");
  for(int i=0 ; i<max ; i++) {
    printf("%d ", A[i]);
  }
  printf("\n");

  // now는 기준점, temp는 비교하면서 움직이는 애, key는 A[now]를 담고있는 애!
  for(now=1 ; now<max ; now++){
  	// 전체 for문이 한 번 돌때는 오른쪽 원소가 왼쪽으로 넘어오는 과정
  	// A[now]의 값과 A[temp]의 값을 비교하면서,
    temp = now-1;
    key = A[now];
    // while문 안에는 실행 조건이 들어가야 한다는 점 주의!
    // while문의 과정을 통해 오른쪽 원소의 정확한 위치를 찾음
    // A[temp] < key : key값이 A[temp]의 값보다 크면, 더이상 이동할 필요가 없음
    // temp가 0보다 작다는 것은 key값이 A array에서 가장 작은 값임을 의미함
    while(temp>=0 && A[temp] > key) {
      A[temp+1] = A[temp];
      temp--;
    }
    A[temp+1] = key;
  }

  printf("sorted: ");
  for(int i=0 ; i<max ; i++) {
    printf("%d ", A[i]);
  }
  printf("\n");


  return 0;
}