정렬

오늘은 단순한 정렬에 대해 공부한 내용을 정리하려고 한다.
오늘은 단순 정렬 3가지에 대해 알아보자

• 1.버블 정렬
• 2.선택 정렬
• 3.삽입 정렬

1.버블 정렬

그림과 같이 3,1,4,2 순으로 저장된 배열이 있다
이것을 오름차순 으로 정렬 하는 과정을 살펴보자

그림에서 본것처럼 첫 번째 값과 두 번째 값을 비교해서 우선순위에 따라 교환한걸 확인할수있다
그다음 에는 두 번째와 세 번째 그다음 세 번쨰와 네 번쨰를 비교한다

그림은 3번째 비교가 진행이 되고 난후의 배열의 모습을 표현한거다
우리가 알수 있는것은 버블 정렬이 한번 하고나니 배열의 끝에는 최고로 큰수가 와있다는 사실이다
그말은 두번째 진행에서는 더이상 네 번째 요소는 신경쓰지 않고 나머지 세 개만 신경써주면 된다

1-1.버블 정렬 코드

#include <stdio.h>

void BubbleSort(int arr[], int n)
{
	int i, j;
	int temp;

	for(i=0; i<n-1; i++)
	{
		for(j=0; j<(n-i)-1; j++)
		{
			if(arr[j] > arr[j+1])
			{
				temp = arr[j];
				arr[j] = arr[j+1];
				arr[j+1] = temp;
			}
		}
	}
}

코드 단계에서 c기본 문법서에서 많이 봐운 구조로 쉽게 코드를 분석할수 있었다

1-2버블 정렬 성능평가

자료구조에 처음으로 나와있는 내용이 성능평가 였다
성능을 평가하는 두가지 요소는
1.시간 복잡도
2.공간 복잡도

버블정렬 에서 복잡도는 비교의 횟수 와 이동의 횟수 복잡도를 가진다
앞서 우리가 본 그림에서 배열 n개는 몇번의 비교와 이동을 했을까 ?
이동은 경우에 따라 달라지지만 비교의 횟수는 최고의 상황과 최악의 상황에서 같다
(n-1) + (n-2) + (n-3) ........
등차수열의 값을 계산하면 알수있다
결론은 버블 정렬의 빅-오는 항상 n^2을 가진다는 것을 알수있다

2.선택 정렬

그림에서 처럼 배열에 3,1,4,2 순으로 데이터가 있다고 생각하자

첫 번째 값과 나머지 중에 가장작은 값 교환해 준다

그림처럼 1,3이 교환 되었다 그러면 1은 더이상 비교해줄 필요가 없다 버블 정렬에서처럼 나머지 3개에서 두번째와 나머지들중 가장 작은 것과 교환해 주면 된다

2-1.선택 정렬 코드

#include <stdio.h>

void SelSort(int arr[], int n)
{
	int i, j;
	int maxIdx;
	int temp;

	for(i=0; i<n-1; i++)
	{
		maxIdx = i;    // 정렬 순서상 가장 앞서는 데이터의 index

		for(j=i+1; j<n; j++)   // 최소값 탐색
		{
			if(arr[j] < arr[maxIdx])
				maxIdx = j;
		}

		/* 교환 */
		temp = arr[i];
		arr[i] = arr[maxIdx];
		arr[maxIdx] = temp;
	}
}

코드를 분석해 보면 첫번째 for 문에서 int가 1부터 시작함을 알수있다.
저런 이유는 선택 정렬에서 1번째는 비교할 필요가 없기때문이다

3.삽입 정렬

똑같이 3,1,4,2 순으로 배열이 있다고 생각해보자
삽입 정렬에서 배열의 첫번째는 정렬이 완료된 영역으로 생각해보자

두번째 데이터를 정렬 영역에 비교와 동시에 넣어준다

똑같이 나머지 비정렬 영역에 있는 것들도 정렬 영역에 비교와 동시에 삽입 해주면 된다

3-1.삽입 정렬 코드

#include <stdio.h>

void InserSort(int arr[], int n)
{
	int i, j;
	int insData;

	for(i=1; i<n; i++)
	{
		insData = arr[i];   // 정렬 대상을 insData에 저장

		for(j=i-1; j>=0 ; j--)
		{
			if(arr[j] > insData) 
				arr[j+1] = arr[j];    // 비교 대상 한 칸 뒤로 밀기
			else
				break;   // 삽입 위치 찾았으니 탈출!
		}

		arr[j+1] = insData;  // 찾은 위치에 정렬 대상 삽입!
	}
}