C언어 32차시 정렬, 버블정렬, 오름차순, 내림차순, 버블정렬 도식화

목차

1. 정렬 알고리즘의 중요성

거의 모든 프로그램에 '정렬' 알고리즘이 포함된다고 해도 과언이 아니다.

따라서 프로그램을 공부하는 사람이라면 '정렬' 알고리즘을 정확히 깨우칠 필요가 있다. 

 

 

2. 정렬이란? sort 

현실 세계에는 여러 사물(객체)들이 존재하고, 그 객체마다 고유한 속성이 있다. 

객체: 강아지
속성: 종류, 키, 평균 수명 길이 등 ------> 고유 데이터

 

그러면 지금부터 고유 데이터를 중심으로 강아지를 정렬해보자. 

강아지 종류를 '가나다 순'으로 정렬하면 '이름으로 정렬된 리스트'를 얻을 수 있다. 

강아지 키를 '키가 작은 순'으로 정렬하면 '키 순으로 정렬된 리스트'를 얻을 수 있다.

강아지 평균 수명 길이를 '수명이 높은 순'으로 정렬하면 '평균 수명으로 정렬된 리스트'를 얻을 수 있다. 

 

 

이처럼 특정 개체가 가진 속성을 데이터로 삼아서, 여러 객체를 정렬시키는 처리가 '정렬'이다. 

 

 

3. 정렬 순서

강아지 키를 '키가 작은 순'으로 정렬하면 '키 순으로 정렬된 리스트'를 얻을 수 있다.

---> 오름차순 : 데이터를 작은 순서대로 나열

ex) 1-9, a-z, ㄱ-ㅎ

 

강아지 평균 수명 길이를 '수명이 높은 순'으로 정렬하면 '평균 수명으로 정렬된 리스트'를 얻을 수 있다. 

----> 내림차순 : 데이터를 큰 순서대로 나열

ex) 9-1, z-a, ㅎ-ㄱ

 

 

4. 정렬 알고리즘의 종류

버킷 정렬, 기수 정렬, 단순 선택 정렬, 단순 교환 정렬(버블 정렬), 단순 삽입 정렬, 셸 정렬, 병합 정렬, 퀵 정렬, 힙 정렬 

 

 

5. 버블 정렬

가장 간단한 버블정렬을 살펴보자. 

가장 효과적인 방법이라고 할 수는 없지만, 가장 이해하기 쉽다. 

 

버블 정렬은 단순 교환 정렬이라고도 부른다. 

이웃한 데이터들의 크기를 비교했을 때, 이미 정렬된 순서와 반대인 경우, 앞 뒤 데이터의 순서를 바꾸어 데이터를 정렬하는 알고리즘이다. 

 

출처: C언어 콘서트(이하 생략)

이웃한 데이터들의 크기를 비교하여 제대로 순서를 정렬해주는 과정을 한 번 지나면, 가장 큰 값은 맨 마지막 제 위치에 있다.

출처: C언어 콘서트(이하 생략)

위 과정을 블록의 개수만큼 되풀이하면, 모든 블록이 크기 순으로 정렬된다. 

출처: C언어 콘서트(이하 생략)

 

 

6. 연습문제

6-1. 버블 정렬

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#define SIZE 5

int main(void)
{
	int tmp, i, k;
	int list[SIZE] = { 3, 5, 1, 7, 6 };
	//배열 요소의 개수 만큼 반복
	for (k = 0; k < SIZE; k++) {
		//반복을 줄이기 위해서 SIZE-1-k의 범위를 지정. 
		for (i = 0; i < SIZE-1-k; i++) {
			if (list[i] > list[i + 1]) {
				//임시변수를 만들어줘야 한다. tmp
				tmp = list[i];
				list[i] = list[i + 1];
				list[i + 1] = tmp;
			}
		}
	}
	
	//배열 요소 출력하기
	for (i = 0; i < SIZE; i++) {
		printf("%d ", list[i]);
	}

	return 0;
}

>> 1 3 5 6 7

 

 

6-2 버블정렬 그림으로 표시

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <windows.h>
#define SIZE 5

int main(void)
{
	int tmp, i, k, j, q;
	int list[SIZE] = { 7, 5, 1, 6, 3 };
	//배열 요소의 개수 만큼 반복
	for (k = 0; k < SIZE; k++) {
		//반복을 줄이기 위해서 SIZE-1-k의 범위를 지정. 
		for (i = 0; i < SIZE-1-k; i++) {
			if (list[i] > list[i + 1]) {
				//임시변수를 만들어줘야 한다. tmp
				tmp = list[i];
				list[i] = list[i + 1];
				list[i + 1] = tmp;
			}
		}
		//그림으로 표시해보기
		for (j = 0; j < SIZE; j++) {
			for (q = 0; q < list[j]; q++) {
				printf("*");
			}
			printf("\n");
		}
		printf("\n");
	}
	
	//배열 요소 출력하기
	for (i = 0; i < SIZE; i++) {
		printf("%d ", list[i]);
	}

	return 0;
}