sorting insertionBubbleSelection_01
1. Internal Sorting
?? Internal Sorting : 내부 정렬은 컴퓨터 메모리 내에서 작동하는 프로세스이다.
- Insertion sort : 앞에서 부터 찾아 작은게 있으면 앞으로 보내거나 알맞은 자리가 있으면 끼워 넣는다.
- Bubble sort : sorting을 한 번 하면 물방울이 위로 떠오르듯이 가장크거나 작은 것이 뒤로 간다.
- Selection sort : 가장 작은거 가져오고, 그다음 작은거 차례대로 가져온다.
- Quick sort
- Heap sort : Heap을 사용
- Merge sort : record를 작게 나눈다음 합쳐서 sort한다.
- Radix sort : 데이터를 구성한는 기본요소(Radix)를 이용해서 sort 한다.
2. Insertion Sort(1)
Insertion Sort의 전제 조건은 내가 sort할 대상이 list[j]라고 하면 list[0], …, list[j-1]까지 정렬되어 있다. 따라서 2를 끼워 넣는다고 할 때 자기보다 작은 수를 만나면 바로 뒤에 insertion한다.
-> insert list[j] into already sorted subfile list[0], …, list[j-1]
3. Codes for Insertion Sort
#include <stdio.h>
typedef struct element {
int key;
}element;
void insertion(element e, element a[], int i);
void insertionSort(element a[], int n);
int main()
{
element a[] = { {0}, {5}, {2}, {9}, {1}, {7} };
int n = sizeof(a) / sizeof(a[0]);
insertionSort(a, n - 1);
for (int i = 1; i < n; i++) {
printf("%d ", a[i].key);
}
return 0;
}
void insertion(element e, element a[], int i)
{
a[0] = e;
while (e.key < a[i].key) {
a[i + 1] = a[i];
i--;
}
a[i + 1] = e;
}
void insertionSort(element a[], int n)
{
int j;
for (j = 2; j <= n; j++) {
element temp = a[j];
insertion(temp, a, j - 1);
}
}element[0]은 비워 있다고 가정해야 insertion을 해서 끼워 넣을 수 있다. 한 자리가 무조건 비어있어야 한다.
element a[] = { {}, {5}, {2}, {9}, {1}, {7} };위와 같이 a[0]에 아무것도 할당하지 않으면 에러 발생한다.
void insertionSort(element a[], int n)
{
int j;
for (j = 2; j <= n; j++) {
element temp = a[j];
insertion(temp, a, j - 1);
}
}2번부터 자리를 비교하는 이유는 0이 자리가 없고, insertion을 하기 위해서는 앞에 무언가가 있어야 하므로 j = 2를 기준으로 j -1인 즉 index 1까지 비교한다. ( j = 2 일경우 index 1까지 비교한다는 말)
void insertion(element e, element a[], int i)
{
a[0] = e;
while (e.key < a[i].key) {
a[i + 1] = a[i];
i--;
}
a[i + 1] = e;
}매개변수 element e는 insertion할 대상이고, element a[ ]는 끼워넣을 배열이다. int i는 j-1이 들어가는데 비교할 대상이 j 앞에까지만 비교한다. 그리고 이 값이 감소하면서 들어갈 자리를 찾는다.
이때, 비교하는 a[i].key가 작거나 같으면 그때 i가 들어가는게 아니라 i다음인 i+1에 들어가서 a[i+1] = e;가 되어야 한다.
3. Inserion Sort(2)
#include <stdio.h>
typedef struct element {
int key;
} element;
void insertionSort(element a[], int n);
int main()
{
element a[] = { {5}, {2}, {9}, {1}, {7} };
int n = sizeof(a) / sizeof(a[0]);
insertionSort(a, n);
for (int i = 0; i < n; i++) {
printf("%d ", a[i].key);
}
return 0;
}
void insertionSort(element a[], int n) {
for (int i = 1; i < n; i++) {
element current = a[i];
int j = i - 1; // i의 앞 요소부터 왼쪽으로 비교 시작
while (j >= 0 && current.key < a[j].key) {
a[j + 1] = a[j];
j--;
}
a[j + 1] = current;
}
}위 코드는 배열의 index 0 요소 a[0]이 반드시 비어 있어야 하므로, 실제 데이터는 index 1부터 시작해야 한다. 이에 따라 비교 시작 지점이 j = 2부터 되어 코드가 직관적이지 않다. 따라서 index 0부터 데이터를 넣는 보편적인 방식으로 수정하였다.