[알고리즘] ch 8. 정렬(1) - 버블 정렬, 삽입 정렬

8.1 정렬 알고리즘의 개요 

 

정렬(Sorting)

- 정해진 기준에 따라 데이터를 순서대로, 그리고 체계적으로 정리하는 알고리즘

- 정렬의 목적은 '탐색'

 

 

8.2 버블 정렬 

 

- 자료 구조를 순회하면서 이웃한 요소들끼리 데이터를 교환하며 정렬 수행

- 버블 정렬은 이웃 요소끼리 데이터를 교환하므로 교환 전에 먼저 이웃끼리 비교하여 바른 순서로 위치해 있는지 확인해야 함

- 왼쪽에 있는 요소가 오른쪽에 있는 요소보다 작아야 함

 

ex)

- 제일 왼쪽에 있는 요소부터 오른쪽에 이웃한 요소와 데이터를 비교해나감

- 왼쪽이 5, 오른쪽이 1이므로 두 이웃 요소 간 데이터를 교환 

- 5, 6은 정렬되어 있으니까 넘어감

- 왼쪽이 4, 오른쪽이 6이므로 교환 

- 제일 큰 수인 6을 제외한 나머지 요소들은 여전히 정려되지 않은 상태로 남아 있음

- 마지막 요소를 제외한 나머지 요소에 대해 처음부터 버블 정렬 수행

- 5까지 정렬 완료

 

 

8.2.1 버블 정렬의 성능 측정 

 

- 버블 정렬은 자료구조를 한 번 순회할 때 마다 정렬해야 하는 자료구조의 범위가 하나씩 줄어들기 때문에 자료구조의 범위가 n이라면 n-1만큼 순회를 반복해야 정렬이 마무리 됨

 

- 버블 정렬을 처음 수행할 때는 정렬 대상의 범위가 6개이므로 다섯 번을 비교 

- 정렬 대상 범위가 5개일 때는 네 번, 4개일 때는 세번, 그리고 남은 요소가 2개일 때는 한 번만 비교 수행 

- 총 비교 휫수 15(5+4+3+2+1)

 

(n-1)+(n-2)+(n-3) + ... +3+2+1 = (n-1) * (n/2) = n(n-1) /2

 

 

8.2.2 버블 정렬 예제 프로그램

 

#include <stdio.h>

void BubbleSort(int DataSet[], int Length)
{
	int i = 0;
	int j = 0;
	int temp = 0;
	int flag; //정렬 여부를 확인하기 위한 변수 

	//바깥에 있는 for루프는 자료구조의 크기만큼 내부에 있는 for 루프를 실행
	for (i = 0; i < Length - 1; i++)
	{
		flag = 0; //정렬 여부 초기화
		//내부에 있는 for 루프는 바깥에 있는 for루프가 한 번 실행될 때마다 그 반복 횟수가 줄어듬
		for (j = 0; j < Length - (i + 1); j++)
		{
			if (DataSet[j] > DataSet[j + 1]) {
				temp = DataSet[j + 1];
				DataSet[j + 1] = DataSet[j];
				DataSet[j] = temp;
				flag = 1; //요소 간 교환이 발생했으므로 정렬 여부를 갱신
			}

		}
		if (flag == 0) {
			//교환 없이 루프가 종료된 경우, 이미 정렬된 배열임을 의미 
			break;
		}
	}

}

int main(void)
{
	int DataSet[] = { 6,4,2,3,1,5 };
	int Length = sizeof DataSet / sizeof DataSet[0];
	int i = 0;

	printf("정렬 전\n");

	for (i = 0; i < Length; i++)
	{
		printf("%2d", DataSet[i]);
	}
	printf("\n");
	BubbleSort(DataSet, Length);

	printf("정렬 후\n");

	//정렬된 자료 구조 출력
	for (i = 0; i < Length; i++)
	{
		printf("%2d", DataSet[i]);
	}

	printf("\n");

	return 0;
}

 

 

 

 

8.3 삽입 정렬 

 

- 자료구조를 순차적으로 순회하면서 순서에 어긋나는 요소를 찾고, 그 요소를 올바른 위치에 다시 삽입해나가는 정렬 알고리즘

 

1) 자료구조에서 정렬 대상이 될 범위를 지정. 이 범위는 첫 2개 요소로 시작하며 알고리즘 수행을 반복하면서 1씩 증가하고 최대 '자료구조의 크기 -1'까지 커짐

 

2) 정렬 범위를 선정한 후에는 범위 마지막에 있는 요소가 정렬 범위 안에서 가장 큰 값을 갖고 있는지 점검

 가장 큰 값이 맞으면 그대로 두고 가장 큰 값이 아니면 이 요소를 뽑아내 옮길 위치를 정렬 대상 안에서 찾음

 여기서 '옮길 위치'는 정렬 범위에서 첫 요소와 원래 위치 사이 중 아까 뽑아낸 요소보다 더 작은 요소가 없는 곳을 말함

 

3) 뽑아낸 요소를 옮길 위치를 찾은 후에는 정렬 대상에서 삽입할 값보다 큰 값을 가진 모든 요소를 한 자리씩 뒤로 이동시키고 새로 생긴 빈 자리에 뽑아낸 요소를 삽입 

 

4) 전체 자료구조의 정렬이 완료될 때까지 단계 1)~3)을 반복

 

 

- 다음 반복에서는 정렬 범위가 1 증가해서 3이 됨

- 6은 이미 제자리에 있으므로 이전 요소들은 이미 정렬을 거친 상태 

 

 

8.3.1 삽입 정렬의 성능 측정 

 

- 삽입 정렬의 비교 횟수 

 = 1+2+ ... + (n-2) + (n-1) = n(n-1) /2

 

- 삽입 정렬은 자료구조가 정렬되어 있다면 한 번도 비교를 거치지 않음 

- 데이터가 정렬되어 있는 최선의 경우와 역으로 정렬되어 있는 최악의 경우 삽입 정렬이 수행하는 비교 횟수의 평균을 낸다면 n(n-1)/2 + (n-1) /2 = n^2 + n-2 /2 회 정도가 됨 

 

 

8.3.2 삽입 정렬 예제 프로그램

 

#include <stdio.h>
#include <string.h>

void InsertionSort(int DataSet[], int Length)
{
	int i = 0;
	int j = 0;
	int value = 0;
	
	//인덱스 0은 이미 정렬됨
	for (i = 1; i < Length; i++)
	{
		if (DataSet[i - 1] <= DataSet[i])
			continue;

		//현재 삽입될 숫자인 i번째 정수를 value 변수로 복사 
		value = DataSet[i];

		for (j = 0; j < i; j++)
		{
			if (DataSet[j] > value)
			{
				//메모리의 내용을 이동
				memmove(&DataSet[j + 1], &DataSet[j], sizeof(DataSet[0]) * (i - j));
				DataSet[j] = value; //알맞은 위치에 value 삽입
				break;
			}
		}
	}
}


int main(void)
{
	int DataSet[] = { 6,4,2,3,1,5 };
	int Length = sizeof DataSet / sizeof DataSet[0];
	int i = 0;

	printf("정렬 전\n");

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

	InsertionSort(DataSet, Length);

	printf("정렬 후\n");

	//정렬된 자료 구조 출력
	for (i = 0; i < Length; i++)
	{
		printf("%2d", DataSet[i]);
	}

	printf("\n");

	return 0;
}

 

memmove() 함수 

 

- 메모리의 내용을 이동시키는 기능 

- 배열처럼 연속된 데이터를 단번에 이동시킬 때 아주 유용

- 첫 번째 매개변수는 원본 데이터가 옮겨갈 새로운 메모리의 주소,

- 두 번째 매개변수는 원본 데이터가 있는 주소

- 세 번째 매개변수는 이동시킬 데이터의 양(byte)