알고리즘 study -3-

<삽입정렬>

-> 원소를 차례대로 정렬된 배열에 삽입

#include <stdio.h>

int main() {

	int n, data[100];  // 원소 수, 배열

	scanf("%d", &n);

	for (int i = 0; i < n; i++) {
		scanf("%d", &data[i]);
	}

	printf("\n");

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

		// 현재 i 인덱스가 가리키고 있는 값을 왼쪽에 삽입시켜야 한다
		// 단, i 왼쪽은 모두 정렬이 되어있다

		for (int j = i ; j >= 1; j--) {  // j 인덱스와 j - 1 인덱스를 비교하므로 j는 1까지만 작아진다
			if (data[j] < data[j - 1]) {
				int temp = data[j - 1];
				data[j - 1] = data[j];
				data[j] = temp;
			}
			else break; // 더 이상 비교 필요 x / 현 상태에서 왼쪽은 이미 정렬되어 있다 
		}

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



	return 0;
}

< 버블정렬 >

-> 인접한 원소를 비교하여 큰 수를 뒤로 보낸다

선택, 삽입정렬과 조금 다르게 오른쪽 부터 정렬이 된다

#include <stdio.h>

int main() {

	int n, data[100];  // 원소 수, 배열

	scanf("%d", &n);

	for (int i = 0; i < n; i++) {
		scanf("%d", &data[i]);
	}

	printf("\n");

	for (int i = 0; i < n; i++) {
		// n번 반복해야 한다 / 원소 수 만큼!

		for (int j = 0; j <=  n - i - 2 ; j++) {  // j 범위 주의!!
				
			if (data[j] > data[j + 1]) {
				int temp = data[j + 1];
				data[j + 1] = data[j];
				data[j] = temp;
			}
		}
		for (int i = 0; i < n; i++) {
			printf("%d ", data[i]);
		}
		printf("\n");
	}



	return 0;
}

오른쪽 부터 큰 값들이 순서대로 정렬되는 것을 볼 수 있다