제 5장: 정렬과 검색(4)

54. 정렬된 데이터를 비교해 올바른위치에 삽입하는 단순 삽입 정렬

• 단순 삽입 정렬: 데이터열 안의 특정 데이털르 기준으로 해당 데이터보다 앞에 위치하는 데이터들과 차례로 비교해 해당 데이터를 열 안에서의 정렬조건과 일치하는 위치에 삽입해 데이터를 정렬하는 알고리즘

• 정렬 순서

  가정: 단순 삽입 정렬 오름차순 정렬. 배열응ㄹ 정렬된 부분(앞) 및 정렬되지 않은 부분(뒤)로 나누어 처리 시작 시 정렬된 부분은 1번째 데이터 1개, 정렬되지 않은 부분은 2번째 이후의 모든 데이터. 데이터 열(D0, D1, …, Dn)에서 정렬 부분은 D0~Di-1이며, 정렬되지 앙ㄴㅎ은 부분의 1번째 데이터를 Di(1 ≤ i ≤n)

  1단계; k=0으로 만든다

  2단계: k < i 일동안 3~4 단계를 반복

  3단계: Dk > Di일때 반복처리 종료

  4단계: k를 1 증가(다음 데이터와 비교 위함)

  5단계: W에 Di를 임시 저장(6단계에서 Di 값을 덮어쓰므로 임시저장)

  6단계: Dk~Di-1을 하나씩 뒤로 이동

  7단계: Dk에 W를 저장

55. 데이터 열을 일정한 길이의 그룹으로 나눠 정렬하는 셀정렬

• 셀정렬: 일정한 길이만큼 떨어진 데이터들을 하나의 그룹으로 묶고, 그 그룹 안의 데이터를 정렬한다.
• 셀정렬은 단순 교환/삽입 정렬에 비해 복잡하지만 값을 이동시키는 횟수를 적게 만들 수 있기 때문에 실행속도가 빠르다.
• 1열로 나열되고 N개 요소를 데이터 배열을 셀 정렬하는 순서
  • 1단계: 그룹 간격 SPAN을 N/2(몫의 정수 부분)으로 초기화
  • 2단계: SPAN이 1 이상이라면 다음 3~5단계 반복.
  • 3단계: 데이터 열을 SPAN길이만큼 나눔.
  • 4단계: 너뉸 구륩둘울 던순 삽입 정렬로 정렬
  • 5단계: SPAN/2(몫의 정수부분)을 SPAN에 대입