c언어 삽입정렬

@ 삽입정렬, insertion sort.

...적다보니 : 삽입정렬, 버블소트, 선택정렬로 이미 정렬된 값들 정렬하기.

 

 

삽입정렬은 어떤 숫자를 적당한 위치에 가져다 놓으며 정렬해 나가는 방식입니다.

a[0]~a[9]배열이 있다고 가정할 때 삽입정렬의 시작은 a[1]에서부터 시작되어 앞(a[0])의 값과 비교 필요하면 값을 삽입하게 됩니다.

그 다음은 a[2]의 값과 a[1], a[0]의 값들을 비교하고 적당한 위치에서 값을 저장하고,

그 다음은 a[3]의 값과 a[2], a[1], a[0].....

...

@ 오름차순

3 1 4 2

이 네 숫자를 이용해 삽입정렬 되는 과정을 살펴보겠습니다.

- 1과 3(a[1] 과 a[0])를 비교합니다. 뒷 자리의 1이 더 작고, 배열의 맨 앞이므로 a[1]과 a[0]의 값이 교환됩니다.

1회 순환 : (1 3 4 2)

 

-- 4와 3(a[2], a[1])을 비교합니다 뒷 자리의 4가 더 큼, 다음 단계로..

2회 순환 : (1 3 4 2)

 

--- 2와 4를 비교합니다. 뒷 자리의 2가 더 작네요. 4를 뒤로 밀어냄

--- 2와 3을 비교 합니다. 뒷 자리의 2가 더 작네요. 3을 뒤로 밀어냄

--- 2와 1을 비교 합니다. 뒷 자리의 2가 더 크네요. 값을 넣음, 정렬완료.

3회 순환 : (1 2 3 4)

 

@ 만약에 1, 2, 3, 4 처럼 이미 정렬 되어져 있는 배열이라면?

- 2와 1을 비교, 뒷자리의 2가 더 큼, 다음 단계로

1회 순환 : (1, 2, 3, 4)

 

-- 3과 2를 비교, 뒷자리의 3이 더 큼, 다음 단계로

2회 순환 : (1, 2 ,3, 4)

 

--- 4와 3을 비교, 뒷자리의 4가 더 큼, 정렬 완료 (1, 2, 3, 4)

 

만약에 선택 정렬로, 1, 2, 3, 4처럼 이미 정렬된 배열을 정렬하려 한다면?

- 1과 2 비교. 1이 더 작으므로 패스

- 1과 3 비교. 1이 더 작으므로 패스

- 1과 4비교. 1이 더 작으므로 패스

- 1회 순환 (1은 정렬완료. 1, 2, 3 ,4)

 

- 2와 3 비교. 2가 더 작으므로 패스

- 2와 4 비교. 2가 더 작으므로 패스

- 2회 순환( 2도 정렬 완료.(1, 2, 3, 4)

 

- 3과 4 비교 3이 더 작으므로 패스

- 3회 순환(정렬 완료 (1, 2, 3, 4)

 

이런 과정으로 흘러 갈 것입니다, 교환 작업은 없지만 비교는 다 해보아야 하지요..

 

말이 나온김에 버블 정렬이라면 어떨까요? (1, 2, 3, 4)

1과 2 비교 1이 더 작으므로 다음 단계로

2과 3 비교2가 더 작으므로 다음 단계로

3과 4 비교3이 더 작으므로 이미 정렬된 배열임을 알 수 있음.

 

삽입정렬에 관한 글 쓰다가 머하는 짓인지;;

아무튼 정렬마다 특징이 있고,

배열의 길이나 이미 정렬되어진 상태(굳이 1, 2, 3, 4가 아니라도 1, 2, 4, 3도 정렬되어진 상태가 좋다고 볼 수 있음)

등등~ 여러가지 요인데 따라 정렬알고리즘들의 효율성이 다르게 나타나기 때문에 어떠한 정렬이 가장 좋은 정렬이다! 라고 말할 수 없습니다.

 

@ 삽입정렬 소스(오름차순)

#include <stdio.h> #define LEN 10 int main() {         int s[LEN] = { 22, 10, 54, 25, 1, 5, 7, 34, 2, 3};          int i,j,temp;          for(i=1;i<LEN;i++)     {         temp = s[i];         j = i-1;         while(j>=0 && s[j] > temp)         {             s[j+1] = s[j];             j=j-1;         }         s[j+1] = temp;     }         for(i=0;i<LEN; i++)     printf("%d ",s[i]);       return 0;   }

 

 

@ 삽입정렬 소스(내림차순)

삽입정렬도 부등호 하나만 방향을 바꾸어주면...오름차순과 내림차순 변경 가능..

#include <stdio.h> #define LEN 10 int main() {         int s[LEN] = { 22, 10, 54, 25, 1, 5, 7, 34, 2, 3};          int i,j,temp;          for(i=1;i<LEN;i++)     {         temp = s[i];         j = i-1;         while(j>=0 && s[j] < temp)         {             s[j+1] = s[j];             j=j-1;         }         s[j+1] = temp;     }         for(i=0;i<LEN; i++)     printf("%d ",s[i]);       return 0;   }

 

 

[Computer/Programing] - c언어 선택정렬

[Computer/Programing] - c언어 버블정렬(버블소트)