2750

2750

거품 정렬과 삽입 정렬에 대한 대략적인 알고리즘을 확인한 후 스스로 구현해 보았다.참고 2750번 문제

버블 정렬 구현

버블 정렬(Bubble sort)은 이웃한 두 개의 원소를 비교하여 순서가 서로 다르면 원소의 자리를 서로 바꾸고, 그렇지 않으면 그 위치를 유지하는 정렬이다

#include 

int main(void) {
	int i, j, temp, arr[1000] = {0, }, n; // i : 반복할 인덱스, j : 비교에 사용할 인덱스, arr : 입력 받은 원소들을 받을 배열, n : 숫자의 개수

	scanf("%d", &n);
	for (i = 0; i < n; i++)
		scanf("%d", &arr[i]);

	for (i = 0; i < n-1; i++) { //  반복
		for (j = 0; j < n-1-i; j++) { // 그 배열 상태에서 제일 큰 수를 가장 오른쪽에 놓기
			if (arr[j] > arr[j + 1]) { 
				temp = arr[j];
				arr[j] = arr[j + 1];
				arr[j + 1] = temp;
			}
		}
	}

	for (i = 0; i < n; i++)
		printf("%d\n", arr[i]);
}

이웃한 두 개의 원소를 비교하여 순서가 다를 경우에는 원소의 자리를 바꾸기 때문에 한 번 실행하고 나면 가장 큰 수가 제일 끝에 위치하게 된다. 이걸 모든 원소가 정렬될 때까지 반복하고자 하였다.

삽입 정렬 구현

삽입 정렬(Insertion sort)은 기존에 정렬된 배열에서 새로운 원소를 위치에 맞게 삽입하는 정렬이다

#include 

int main(void) {
	int i, j, temp, arr[1000] = { 0, }, n, a; // i : 기존 정렬에서 새로 삽입할 원소의 인덱스, j : 새로운 원소와 비교할 기존 원소들, a : 정렬하는 과정에서 쓰이는 인덱스

	scanf("%d", &n);
	for (i = 0; i < n; i++)
		scanf("%d", &arr[i]);

	for (i = 1; i < n; i++) // 새로 삽입할 원소의 인덱스
		for (j = 0; j < i; j++) { // 새로 삽입할 원소와 비교할 기존 원소들
			if (arr[i] < arr[j]) { // 만약 새로 삽입할 원소가 기존 원소보다 작을 경우
				a = i;
				temp = arr[i]; // 새로 삽입할 원소를 보관
				while (a > j) // 새로 삽입할 원소보다 큰 원소들은 한 칸씩 오른쪽으로 밀려난다
					arr[a--] = arr[a - 1]; // i 인덱스부터 한 칸씩 밀려난다
				arr[j] = temp; // 새로 삽입할 원소를 기존 원소의 인덱스로 위치시킨다
			}
		}
	
	for (i = 0; i < n; i++)
		printf("%d\n", arr[i]);
}

새로 삽입하는 원소가 그 기존에 정렬된 배열에서 가장 오른쪽에서 있다고 가정했을 때, 새로운 원소를 위치에 맞게 삽입하기 위해 일부 큰 원소들을 하나씩 오른쪽으로 미뤄지도록 하였다. 이걸 정렬되지 않은 원소가 없어질 때까지 반복하였다

결과