숫자 정렬(버블 정렬, 삽입 정렬) - 바로 실행해보면서 배우는 C언어

두 변수의 값 바꾸기

#include <stdio.h>

int main() {
	int a;
	int b;
	int temp;
	
	scanf("%d %d", &a, &b);
	
	temp = a;
	a = b;
	b = temp;
	
	printf("%d %d", a, b);

  return 0;
}

 

 

버블 정렬

가장 간단한 정렬 알고리즘. 서로 이웃한 값들을 비교해 큰 값을 뒤로 넘기며 정렬한다.

최종적으로는 작은 값 → 큰 값 순서대로 정렬된다.

값 비교 과정 때문에 다른 정렬에 비해 속도가 느리지만, 구현하기가 매우 간단하다.

 

버블 정렬로 배열 내림차순 정렬하기

#include <stdio.h>

int main() {
  int arr[10] = { 9, 17, 5, 6, 124, 112, 1, 3, 87, 55 };
  int temp; // 두 값을 바꿀 때 사용할 변수
  
	for(int j=0; j<9; j++) {
		for(int i=0; i<9; i++) {
			if(arr[i] < arr[i+1]) {
				temp = arr[i];
				arr[i] = arr[i+1];
				arr[i+1] = temp;
			}
		}
	}
	
	for(int j=0; j<10; j++) {
		printf("%d ", arr[j]);
	}
	
  return 0;
}

바깥쪽 for문의 종결조건이 j<9인 이유 : 
가장 큰 수가 배열의 맨 끝(arr[10])에 있는 경우(=자리를 가장 여러 번 바꿔야 하는 경우의 수), 
맨 앞으로 오기 위해 9번 이동해야(자리를 바꿔야) 함. 

 

삽입 정렬

선택된 원소를 앞에 있는 원소들과 비교하여 넣어줄 위치를 찾고 삽입한다.

선택된 원소의 앞에 있는 원소들은 이미 정렬이 되어있는 상태이기 때문에,

선택된 원소가 앞에 있는 원소들보다 크다면 앞의 원소들과 비교할 필요가 없으므로 바로 다음 원소를 선택한다. → 쓸모없는 비교를 줄이기 때문에 버블 정렬보다 빠르다.

배열이 길어질수록 효율이 떨어지고, 버블 정렬과 마찬가지로 구현이 단순한 편이다. (버블 정렬보다는 조금 더 복잡함.)

 

삽입 정렬로 배열 내림차순 정렬하기

#include <stdio.h>

int main() {
  
  int arr[10] = { 9, 17, 5, 6, 124, 112, 1, 3, 87, 55 };
  int temp; // 두 값을 바꿀 때 사용할 변수
  int length = sizeof(arr) / sizeof(int);
	int j;
	
	for(int i=0; i<length; i++) {
		temp = arr[i];
		j = i - 1;
		while(j>=0 && arr[j] < temp) {
			arr[j+1] = arr[j];
			j--;
		}
		arr[j+1] = temp;
	}
	
	for(int i=0; i<length; i++) {
		printf("%d ", arr[i]);
	}
	

  return 0;
}

 

 

*

오름차순 : 작은 값 -> 큰 값 순서대로 정렬 (값이 올라감)

내림차순 : 큰 값 -> 작은 값 순서대로 정렬 (값이 내려감)

 

이 글에서 삽입 정렬, 버블 정렬 설명은 오름차순 기준이고 예제 코드는 내림차순 기준입니다.

 

---

※ 출처 : 바로 실행해보면서 배우는 C언어, 구름edu