c++ 선택정렬, 삽입정렬, 버블정렬

 

 

c++ 선택정렬, 삽입정렬, 버블정렬

 

 

- 삽입정렬 

1. 2번째 요소를 선택하고, 2번째보다 작은 요소들(1)과 비교해서 선택한 2번째 요소 값이 들어갈 위치를 찾는다.

2. 3번째 요소를 선택하고, 3번째보다 작은 요소들(2,1)과 비교해서 선택한 3번째 요소 값이 들어갈 위치를 찾는다.

3. 4번째 요소를 선택하고, 4번째보다 작은 요소들(3,2,1)과 비교해서 선택한 4번째 요소 값이 들어갈 위치를 찾는다.

...끝까지

 

- 선택정렬 

1. 모든 배열을 탐색해 제일 작은 값의 위치를 찾고 1번째 자리에 위치시킨다.

2. 1번째 위치를 제외하고 모든 요소를 탐색해, 2번째로 작은 값을 찾고 2번째에 위치시킨다..

3. 1,2번째 위치를 제외하고 모든 요소를 탐색해, 3번재로 작은 값을 찾고 3번째에 위치킨다.. (여기서 위치할땐, 교환임)

...끝까지

 

- 버블정렬 

1. 1,2번째 값 비교, 작은 값을 앞에 위치

2. 2,3번째 값 비교, 작은 값을 앞에 위치

3. 3,4번째 값 비교, 작은 값을 앞에 위치

...끝까지 반복.

 

 

아래는 전체 소스입니다.

 

#include 
#include 
using namespace std;

//삽입정렬
int * insertSort(int array[], int n) {
	for (int i = 1; i < n; i++) {
		int tmp = array[i];
		int j = 0;
		for (j = i - 1; j > -1; j--) {
			if (array[j] > tmp) {
				array[j+1] = array[j];
			}
			else {
				break;
			}
		}
		array[j+1] = tmp;
	}
	return array;
}
//선택정렬
int * selectSort(int array[], int n) {
	for (int i = 0; i < n - 1; i++) {
		int least = i;
		for (int j = i+1; j < n; j++) {
			if (array[least] > array[j]) {
				least = j;
			}
		}
		int tmp = array[i];
		array[i] = array[least];
		array[least] = tmp;
	}
	return array;
}

//버블정렬
int* mergeSort(int array[], int n) {
	for (int i = 0; i < n-1; i++) {
		for (int j = i+1; j < n; j++) {
			if (array[i] > array[j]) {
				int tmp= array[i];
				array[i] = array[j];
				array[j] = tmp;
			}
		}
	}
	return array;
}

int* copyArray(int arr[], int n) {
	int *tmp = new int[n];

	for (int i = 0; i < n; i++) {
		tmp[i] = arr[i];
	}
	return tmp;
}

void printArray(int *a, int n, string title) {
	cout << title+" : ";
	for (int i = 0; i < n; i++) {
		cout << a[i] << " ";
	}
	cout << endl;
}

int main() {

	int a[] = {8,3,6,2,7,1,5,4};
	int n = sizeof(a) / sizeof(int);
	printArray(a, n, "원본배열");
	int *b = new int[n];
	//버블정렬
	b = mergeSort(copyArray(a, n), n);
	printArray(b, n, "버블정렬");
	//선택정렬
	b = selectSort(copyArray(a, n), n);
	printArray(b, n, "선택정렬");
	//삽입정렬
	b = insertSort(copyArray(a, n), n);
	printArray(b, n, "삽입정렬");
	
	return 0;


}