[자료구조] by C언어 #07 [insertion sort]

삽입 정렬 알고리즘 (Insertion Sort) :  

앞의 원소부터 차례대로 진행하여

원소 앞의 이미 정렬된 배열에

자신의 위치를 삽입하는 알고리즘

 

시간복잡도 : O(n**2)

 

ㅡㅡㅡㅡㅡ

#include <stdio.h>
#define MAX 8

void print_array(int list[], int n) {
   int i;
   for (i = 0; i < n; ++i) {
      printf("%d ", list[i]);
   }
   printf("\n");
}


void insertion_sort(int list[]) {
   int i; // 정렬될 원소의 인덱스
   int j; // 정렬될 원소 기준 @왼편@에 있는 원소들의 인덱스
   int remember;

   for (i = 1; i < MAX; ++i) {   // i : 1, 2, 3, 4, 5, 6, 7
      remember = list[i];   // 정렬될 원소의  값을 reamember에 저장.
      for (j = i - 1; j >= 0 && list[j] > remember; --j)   // j는 0부터 시작.-> 0/1,0/2,1,0/...  // 마지막에 --j .
            list[j + 1] = list[j];   // j번째 원소값을  오른쪽 원소에 저장.
            list[j + 1] = remember;   // j번째 원소에는 remember에 저장해둔 i번째 원소의 값을 대입.

   }
}

void main() {

int arr[MAX] = { 8,7,4,6,1,3,2,5 };
printf("정렬 전 : ");
print_array(arr, MAX);

insertion_sort(arr); // insertion_sort() 함수 호출. 

printf("정렬 후 : ");
print_array(arr, MAX);
}

ㅡㅡㅡㅡㅡ