[자료구조] 정렬 알고리즘

---

🔴버블정렬

숫자들을 하나 하나 비교해서 정렬해나간다.
사이클을 1번 돌때마다 그 다음으로 가장 큰 수가 가장 뒤로 가게된다.

기본 사이클

1번째 숫자와 2번째 숫자를 비교해서 만약 1번째 숫자가 더 크다면 정렬을 할 필요가 있고 1번째 숫자와 2번째 숫자에 위치를 서로 바꾸어준다. 그 후 2번째는 3번째와 비교, 3번째는 4번째와 비교, 4번째는 5번째 비교를 하여 사이클 당 총 4번의 반복문을 실행한다.

이 반복을 숫자의 갯수만큼 진행해주었다.
그렇기에 큰 for반복문의 틀은 N번 반복 그리고 틀 안에 있는 반복문은 N-1번 반복을 하기에 N(N-1)번 반복을 한다. 만들고 보니 뭔가 이상함을 느꼈는데, 버블 정렬은 한 번 실행될때마다 가장 큰 수가 가장 뒤로 가게 되어 있어 굳이 이미 정렬된 가장 큰 숫자는 정렬할 필요가 없었기에 코드를 조금 수정하여 반복하는 횟수를 조금 줄였다.

성능

버블 정렬의 경우에는 이미 정렬이 된 숫자들에 적용 시에는 최상의 성능을 나타낸다. 하지만 정렬이 되지 않는 숫자에 대해서는 최악에 경우에 (n)(n-1)/2 번 반복을 하는 성능이 나타나는데 이것은 굉장히 비효율적인 정렬 방법이다.

성능면에서는 아쉬운 부분이 분명 있으나 간단하고 손쉽게 구현할 수 있는 점은 장점인 것 같다.

---

실제 구현 코드

#define _CRT_SECURE_NO_WARNINGS 
#include<stdio.h>

#define Max 5

int main()
{
	int Ary[5] = { 7,1,9,5,2 };
	int Temp = 0;

	//<--------------n번 반복--------------->
	for (int j = 0; j < Max; j++)
	{
		//<--------(n-1)/2번 반복-------->
		for (int i = 0; i < Max - (1+j); i++)
		{
			if (Ary[i] > Ary[i + 1])
			{
				Temp = Ary[i];
				Ary[i] = Ary[i + 1];
				Ary[i + 1] = Temp;
			}
		}
	}

	//<-----출력해서 확인----->
	for (int i = 0; i < Max; i++)
	{
		printf("%d | ", Ary[i]);
	}
}

---

🔴삽입정렬

앞에 있는 모든 숫자들(이미 정렬된 숫자들)과 비교해나가며 순서를 바꾼다.

기본 사이클

삽입 정렬은 말 그대로 올바른 위치에 삽입을 시켜주는 정렬이라고 보면 된다. 흐름은 2번째부터 시작을 해서 점점 커지고, 앞에 있는 숫자들 전부와 비교를 시켜준다. 그림을 예시로 들어 4번째 숫자인 1을 그 앞 숫자인 5와 비교를 한다. 1이 5보다 크니까 1이 들어갈 자리는 아님으로 5는 뒤로 밀어준다. 이 떄 뒤로 밀어주는 이유는 올바른 위치에 현재 4번째 숫자 1이 삽입이 됬을 때 공간을 확보해주기 위함이다. 그 후 3번째, 2번째, 1번째 숫자들을 비교해나가며 자신보다 작은 경우를 찾을 때까지 뒤로 밀어준다. 만약에 자신보다 더 작은 숫자가 있다면 그 숫자를 기준으로 +1이 되는 인덱스 위치에 삽입을 시켜준다.

성능

버블 정렬과 같은 장점을 지닌다. 이미 정렬된 배열에 대해서는 좋은 성능을 보인다. 반복문이 두 개가 사용되고 적절한 위치를 찾기까지 숫자들을 뒤로 밀어내야 하기에 시간이 오래 걸릴 수 있다. 또한 내림차순이 되있을 경우에 최악의 성능이 나타날 수 있다.

실제 구현 코드

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

int main()
{
	int Ary[Max] = { 4, 1, 3 ,5 ,2 };
	int temp = 0;
	int Num = 0;
	int Keep = 0;
	int j = 0;

	for (int i = 1; i < Max; i++)
	{
		Num = Ary[i];

		for (j = i - 1; j >= 0; j--)
		{
			if (Ary[j] > Num)
				Ary[j + 1] = Ary[j];
			else
			{
				break;
			}
		}

		Ary[j + 1] = Num;
	}

	for (int i = 0; i < Max; i++)
	{
		printf("%d | ", Ary[i]);
	}
}