알고리즘의 기초(1) - 선택정렬, 버블정렬 그리고 삽입정렬

시간복잡도 O의 개념이해

세가지 정렬법 모두 O(N^2)

 

1) 선택정렬

- 배열을 순회하면서 전체 원소중 가장 작은 것을 앞으로 보냄

int main(void){	
	int i, j ,min, index, temp;
	int array[10] = {1,3,2,4,5,6,8,7,10,9};
	
	
	//배열을 순회 
	for(i=0;i<10;i++){
		min=9999;//배열내 숫자보다 더 큰 숫자 
		 
		//i번째 원소를 가장앞으로 보내기 
		for(j=i;j<10;j++){
			if(min>array[j]){
				min =array[j];
				index = j;
			}
		} 
		temp = array[i];
		array[i] = array[index];
		array[index] = temp;
		//i번째 원소를 가장앞으로 보내기		
	}	
	for(i =0; i<10;i++){
		printf("%d ", array[i]);
	}
	return 0;
}

 

 

 

2) 버블정렬

- 배열을 순회하면서 I 번째의 원소와 그 다음 원소를 비교하여 변경

 

int main(void){
	
	int i, j , temp;
	int array[10] = {1,3,2,4,5,6,8,7,10,9};
	
	for(i=0;i<10;i++){
		for(j=0;j<9-i;j++){
			if(array[j]>array[j+1]){
				temp = array[j];
				array[j] = array[j+1];
				array[j+1] = temp;		
			}
		}
	}
	for(i =0; i<10;i++){
		printf("%d ", array[i]);
	}
}

3) 삽입정렬

- 배열을 순회하면서 I 번째의 원소와 그 앞의 원소에 들어갈 위치를 비교하여 정렬

- 선택정렬, 버블정렬과 달리 배열을 모두 순회할 필요가 없음

- 특수한 경우(이미 정렬이 된 상태에서) 정렬할 경우 연산 속도가 매우 빨라짐;

int main(void){
	int i, j ,temp;
	int array[10] = {1,3,2,4,5,6,8,7,10,9};

	for(i=0;i<9;i++){
		j = i;
		while(array[j]>array[j+1]){
			temp = array[j];
			array[j] = array[j+1];
			array[j+1] = temp;
		}
	} 
	for(i = 0; i<10;i++){
		printf("%d ", array[i]);
	}
	return 0; 

}