[알고 day1] 선택정렬 , 버블정렬, 삽입정렬

정렬(sort)문제를 통해 알고리즘의 효율성과 시간 복잡도 개념에 대한 공부를 하고자 한다. 프로그램 툴은 Dev-C++이고, C언어를 통해서 진행한다. (https://sourceforge.net/projects/orwelldevcpp/)

 

공통문제:

 

"다음 [1 10 5 8 7 6 4 3 2 9] 숫자들을 오름차순으로 정렬하는 프로그램을 작성하세요"

 

 

방법1: 선택정렬(Selection Sort)

가장 작은 것을 제일 앞으로 보내주는 알고리즘. 가장 원시적, 기초적인 방법이다. min 변수에 가장 작은 숫자를 일시적으로 담고, temp는 두 숫자의 위치를 서로 바꾸기 위해서 사용하는 변수이다. 포인트는? 데이터의 갯수가 N개일 때 총 몇번의 비교 연산을 해야하는가이다. 선택정렬은 N*(N+1)/2번 가량의 연산을 수행해야 함. 이를 컴퓨터는 가장 큰 차수인 N^2만 보고 0(N^2)라고 표현함.

즉, 등차수열의 공식으로, 10 * (10+1) /2 = 55이며, 총 10개를 비교하기 위해서 55번의 비교를 해야한다. N * N의 수행 시간을 가지고 있다고 표기한다. (비교표기법: 0(N * N) // 특정한 알고리즘을 수행시간을 가장 간략하게 표기하는 방법!)

  
즉, 처리할 데이터가 많다면, 매우 많은 연산을 처리해야 하기때문에, 피해야할 비효율적인 개념이다. 
[선택 정렬의 시간 복잡도는 0(N^2) 이다] 

 

#include <stdio.h>

int main(void)	{
	int i, j, min, index, temp; 
	int array[10] = {1,10,5,8,7,6,4,3,2,9};
	
	for(i=0;i<10;i++){
		min = 9999; //무작위
		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; //스와핑을 한다 
	}	
	for(i=0;i<10;i++){
		printf("%d", array[i]);
	}
	return 0;
}

 

 

방법2: 버블정렬(Bubble Sort)

'가장 가까이에 있는 두 숫자를 비교해서 당장 더 작은 숫자를 앞으로 보내주는 것을 반복하는 것', 가장 쉽지만 각 싸이클마다 가장 큰 값이 맨 뒤로 보내지게 되며, 컴퓨터 내부적 연산이(많아져) 가장 비효율적으로 일어나게 됨으로 가장 안 좋은 알고리즘이다.  

 

[선택 정렬의 시간 복잡도는 0(N^2) 이다] 

 

#include <stdio.h>

int main(void)	{
	int i, j, temp;
	int array[10] = { 1, 10, 5, 8, 7, 6, 4, 3, 2, 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]);
	}
	
	return 0;
}

 

 

방법3: 삽입정렬(Insertion Sort)

각 숫자를 적절한 위치에 삽입하는 방법. 무조건 위치를 바꾸는 방식이 아닌 삽입 정렬은 '필요할 때만' 위치를 바꾸게 됨. 사입 정렬은 기본적으로 '정렬이 되어 있다고 가정'을 한다는 점에서 특정한 경우에 따라서 굉장히 빠른 속도를 자랑함. 단, 소스코드상 반복문이 두 번 들어가 있다는 점에서 복잡도는 0(N^2)이다. 

#include <stdio.h>

int main(void) {
	int i, j, temp;
	int array[10] = {1 ,10 ,5, 8, 7, 6, 4, 3, 2 ,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;
			j--; //
			//멈출 포인트를 알고 있기때문에 더욱 효율적이다 
		}
		 
	}
	for(i = 0; i < 10; i++){
		printf("%d", array[i]);
	} 
	return 0;
}

 

숫자 [2 3 4 5 6 7 8 9 10 1] 같이 데이터가 이미 거의 정렬된 상태에 한해서는 어떤 알고리즘 보다 빠르다는 특징이 있다. 

 

추가문제

26 5 37 1 61 11 59 15 48 19 이 삽입정렬 방식에 의하여 일일이 수행되는 과정을 출력하시오 

 

힌트: 특정 위치에서 시작해서 왼쪽으로 이도암 자신보다 작은 것을 만날 때 그 위치에 원소를 삽입하면 된다. 

 

 

 

 

출처:

https://www.youtube.com/watch?v=8ZiSzteFRYc //유트브 직강

https://m.blog.naver.com/PostView.nhn?blogId=ndb796&logNo=221226800661&proxyReferer=https%3A%2F%2Fwww.google.com%2F //해설 블로그