삽입정렬(InsertSort) & 버블정렬(BubbleSort)

1. 삽입정렬 ( InsertSort )

원리 : 선택한 요소가 들어갈 있는 자리를 찾아서 삽입시킨다.

< 소스코드 >

#include<stdio.h>

void insert_sort ( int arr[] , int end ) {

int i = 0 , j = 0 , temp = 0 ;    

for( int i = 0 ; i <= end ; i++){         

temp = arr [ i ] ;

j = i ;

while( arr[ j-1 ] > temp && j > 0 ){   

arr [ j ] = arr [ j-1 ];

j--;

}

arr [ j ] = temp ;

}

}

int main ( void ){

int arr[] = { 5 , 4 , 2 , 3 , 1 };

int i = 0 ;

insert_sort( arr , 4 );

for ( i = 0 ; i < 5 ; i++){

printf("%d " , arr[i] );

}

}

< 과정 >

i , j = 0    :    5 4 2 3 1

i , j = 1    :    5 5 2 3 1 -> 4 5 2 3 1

i , j = 2    :    -> 4 5 5 3 1 -> 4 4 5 3 1 -> 2 4 5 3 1

i , j = 3    :    -> 2 4 5 5 1 -> 2 4 4 5 1 -> 2 3 4 5 1 

i , j = 4    :    -> 2 3 4 5 5 -> 2 3 4 4 5 -> 2 3 3 4 5 -> 2 2 3 4 5 -> 1 2 3 4 5 .

---------

2. 버블정렬 ( BubbleSort )

원리    : 요소두개를 계속 비교해서 뒤로 값을 보낸다.

<소스코드>

#include<stdio.h>

void bubble_sort( int arr[] , int end ){

int i = 0 , j = 0 , temp = 0 ;

for( i = end ; i > 0 ; i--){

for( j = 1 ; j <= i ; j++){                // 맨끝에 값은 비교할 필요가 없다

if( arr [ j -1 ] > arr [ j ] ){

temp = arr [ j ] ;

arr [ j ] = arr [ j-1 ] ;

arr [ j-1 ] = temp ;

}

}

}

}

int main( void ) {

int arr[] = { 5 , 2 , 3 , 1 , 4 };

int i = 0 ;

bubble_sort( arr , 4 );

for ( i = 0 ; i < 4 ; i++){

printf("%d " , arr[i] ) ;

}

return 0 ;

}

< 과정 >

i = 4    :    2 5 3 1 4 -> 2 3 5 1 4 -> 2 3 1 5 4 -> 2 3 1 4 5

i = 3    :    2 3 1 4 5 -> 2 1 3 4 5 

i = 2    :    1 2 3 4 5