[자료구조] - 정렬 /선택정렬/삽입정렬/버블정렬

정렬 : 물건을 크기순으로 오름차순, 내림차순으로 나열하는 것을 의미

ex)

• 책 제목순, 저자순, 발간연도수
• 사람 나이, 키, 이름
• 인터넷 제품 가격, 인기순 등등

보통 정렬시켜아 될 대상은 레코드(필드들을 합친것)

하나의 레코드 = 이름 + 학번 + 주소 + 연락처
여기서 레코드를 식별해주는 역할을 하는 필드를 키(key)라고 함
학생의 경우 키는 학번
결국 정렬은 레코드들을 키 값의 순서로 재배열하는것

• 단순하지만 비효율적인 방법 - 삽입 정렬, 선택 정렬, 버블 정렬
• 복잡하지만 효율적인 방법 - 퀵 정렬, 히프 정렬, 합병 정렬, 기수 정렬

선택 정렬

제일 작은것을 선택해서 앞으로 보넨다.

• 배열 2개 구현 -> 메모리 낭비
• 배열 1개 구현 -> 제자리 정렬

장점 : 자료 이동 횟수가 미리 결정된다는 점
3(n-1) : 한번 교환하기 위하여 3번의 이동이 필요(Swap매크로의 작업)
그러나 3(n-1)은 이동 횟수로 상당히 큰 편....
전체 비교 횟수 for문 2번 -> O($N^2$)

#define SWAP(x, y, t) ( (t)=(x), (x)=(y), (y)=(t) )

void selection_sort(int list[], int n)
{
	int i, j, least, temp;
	for (i = 0; i < n - 1; i++) {
		least = i;
		for (j = i + 1; j < n; j++) 	// 최소값 탐색
			if (list[j] < list[least]) least = j;
		SWAP(list[i], list[least], temp);
	}
}

자신보다 작은 data를 찾아서 서로 위치를 바꿈

삽입정렬

앞의 부분이 이미 정렬되 있다고 가정하고 필요한 만큼만 이동해 적절한 위치에 삽입한다./
거의 정렬된 상태라면 외부 루프는 n-1, 비교횟수는 n-1 이므로 총 2(n-1) -> O(N)이다.
최악의 복잡도는 입력 자료가 역순일 경우인다 외부 for문과 내부 for문 으로 O($N^2$)이다.

즉 비교적 많은 이동을 포함하기에 레코드 양과 크기가 크면 적합하지 않지만 레코드의 수가 적고 크기가 적으면 알고리즘 자체가 매우 간단하므로 다른 정렬방법보다 유리!

// 삽입정렬
void insertion_sort(int list[], int n)
{
	int i, j, key;
	for (i = 1; i<n; i++) {
		key = list[i];
		for (j = i - 1; j >= 0 && list[j]>key; j--)
			list[j + 1] = list[j]; /* 레코드의 오른쪽 이동 */
		list[j + 1] = key;
	}
}

버블 정렬

옆에 있는 값과 비교해서 더 작은 값을 앞으로 보네자.

큰 단점 : 순서에 맞지 않은 요소를 인접한 요소와 교환한다는것
최악의 경우든, 최선의 경우든 시간복잡도는 O($N^2$)

#define SWAP(x, y, t) ( (t)=(x), (x)=(y), (y)=(t) )
void bubble_sort(int list[], int n)
{
	int i, j, temp;
	for (i = n - 1; i>0; i--) {
		for (j = 0; j<i; j++)
			/* 앞뒤의 레코드를 비교한 후 교체 */
			if (list[j]>list[j + 1])
				SWAP(list[j], list[j + 1], temp);
	}
}