자료구조 선택정렬, 버블정렬, 삽입정렬

---

참고자료

https://jung-story.tistory.com/5

자료구조 (Linked list) - 알고리즘 & 자료구조 C언어

 

---

선택정렬

 

• 선택정렬의 제자리 정렬 알고리즘의 하나 이며 입력 배열 이외에 다른 추가 메모리를 요구하지 않는 정렬 방법입니다.
• 선택 정렬은 첫 번째 자료를 두 번째 자료부터 마지막 자료까지 차례대로 비교하여 가장 작은 값을 찾아 첫 번째에 놓고, 두 번째 자료를 세 번째 자료부터 마지막 자료까지와 차례대로 비교하여 그 중 가장 작은 값을 찾아 두 번째 위치에 놓는 과정을 반복하며 정렬을 수행합니다.

 

#include <stdio.h>

int size;
void SelectSort(int arr[], int size) {
	int i, j, t, key;
	int temp;
	for (i = 0; i < size - 1; i++) {
		key = i;	// 최솟값을 임의로 첫번쨰로 키를 잡는다.
		for (j = i + 1; j < size; j++) {//첫번째가 키니까 그 뒤에서부터 size까지 반복을 실행한다.
			if (arr[j] < arr[key]) key = j;	//찾은값이 키값보다 작으면 키값에는 그 작은값을 넣어준다.
		}
		temp = arr[i];	// 값을 바꿔주는 형태
		arr[i] = arr[key];
		arr[key] = temp;
	}
	for (t = 0; t < size; t++) {
		printf("%2d,", arr[t]);
	}
}

int main() {
	int arr[8] = { 1,10,54,875,12,487,14,56 };
	size = 8;
	SelectSort(arr, size);

}

 

---

선택정렬 결과

출력 화면

 

---

버블정렬

 

• 버블정렬은 서로 인접한 두 원소를 검사하여 정렬하는 알고리즘입니다.
• 인접한 2개의 레코드를 비교하여 크기가 순서대로 되어 있지 않으면 서로 교환하면서 정렬하는 방식입니다.

 

#include <stdio.h>

int size;
void SelectSort(int arr[], int size) {
	int i, j, t, key;
	int temp;
	for (i = size-1; i > 0; i--) {
		key = i;	
		for (j = 0; j < i; j++) {
			if (arr[j] > arr[j + 1]) {
				temp = arr[j];	
				arr[j] = arr[j+1];
				arr[j+1] = temp;
			}
		}
	}
	for (t = 0; t < size; t++) {
		printf("%2d,", arr[t]);
	}
}

int main() {
	int arr[8] = { 1,10,54,875,12,487,14,56 };
	size = 8;
	SelectSort(arr, size);
	
}

 

---

버블정렬 결과

출력 화면

 

---

삽입정렬

 

• 삽입정렬은 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열과 비교하여 자신의 위치를 찾아 삽입함으로써 정렬을 완성하는 알고리즘 입니다.

#include <stdio.h>
#define size 10

void insertSort(int arr[]) {
	int i, j, t, tmp;

	for (i = 1; i < size; i++) {
		tmp = arr[i];

		for (j = i; (j > 0) && arr[j - 1] > tmp; j--) {
			arr[j] = arr[j - 1];

		}
		arr[j] = tmp;
		printf("\n%d 단계 :", i);
		for (t = 0; t < size; t++) {
			printf("%3d,", arr[t]);
		}
	}


}

int main() {
	int arr[size] = { 2,8,7,10,15,23,54,75,33,45 };
	insertSort(arr);

}

 

---

삽입정렬 결과

 

출력 코드

 

---

끝마치며..

 

이상으로 선택정렬,버블정렬,삽입정렬에 대해서 알아보았으며

다음에는 병합정렬,삽입정렬에 대해서 알아보겠습니다.

 

---