By Standing On The Shoulders Of Giants

#include<stdio.h>
int N, number, h[5001],cnt=1;
void Insert()
{
	int now = cnt;
	h[cnt++] = number;
	while (now / 2 > 0 && number > h[now/2])
	{
		h[now] = h[now / 2];
		now /= 2;
	}
	h[now] = number;
}
 
void Delete()
{
	int now = 1;
	int result = h[1], bigChild;
	int last = h[--cnt];
	bigChild = h[now * 2] > h[now * 2 + 1] ? now * 2 : now * 2 + 1;
		while (bigChild < cnt && h[bigChild] > last)
		{
			h[now] = h[bigChild];
			now = bigChild;
			bigChild = h[now * 2] > h[now * 2 + 1] ? now * 2 : now * 2 + 1;
		}
	h[now] = last;
	h[cnt] = result;
	printf("[%d] ", h[1]);
	for (int i = 2; i <= N; i++)
		printf("%d ", h[i]);
	printf("\n");
}
 
int main()
{
	int mode;
	scanf("%d", &N);
	for (int i = 0; i < N; i++)
	{
		scanf("%d", &number);
		Insert();
	}
	for (int i = 1; i <= N; i++)
		 Delete();
	return 0;
}
 
//힙은 인덱스 1부터 시작해야한다. 완전이진트리에서 부모-자식간 관계와 index를 1:1 대응하기 위해서
//cnt는 앞으로 넣어질 idx이다. 즉 cnt = 힙의 노드갯수+1
//자식의 갯수를 구분하여 연산할 필요가 없다. 
while (bigChild < cnt && h[bigChild] > last)에서 걸러진다.
자식의 갯수가 하나만 있을 경우 자식노드 : [작은값=음수] [큰값=0] 이어서
bigchild = cnt가 되어도 while 조건에서 ㅁ



자료 구조인 힙을 구성하여
삭제연산을 수행하여 삭제연산의 결과를 
힙의 마지막 위치에 넣고 힙의 범위를 하나 줄인다.

정렬된 값 : 노란색
힙의 범위 : 파란색
8
1 8 7 2 3 6 4 5 

cnt = 9
[8] 5 7 3 2 6 3 1
cnt = 8
[7] 5 6 3 2 1 4 8
cnt = 7
[6] 5 4 3 2 1 7 8
cnt = 6
[5] 3 4 1 2 6 7 8
cnt = 5
[4] 3 2 1 5 6 7 8
cnt = 4
[3] 1 2 4 5 6 7 8
cnt = 3
[2] 1 3 4 5 6 7 8
cnt = 2
[1] 2 3 4 5 6 7 8
cnt = 1
 1  2 3 4 5 6 7 8

#include<stdio.h>
int N, num[5010];
void Shell()
{
	for (int n = N; n > 0; n /= 2)
		for (int i = 0; i < N; i += n)
		{
			int j = i, now = num[i];
			while (num[j - n] > now && j > 0)
			{
				num[j] = num[j - n];
				j -= n;
			}
			num[j] = now;
		}
}
int main()
{
	scanf("%d", &N);
	for (int i = 0; i < N; i++)
		scanf("%d", &num[i]);
	Shell();
	return 0;
}

삽입정렬의 개선으로
삽입될 위치의 간격을 1로 두지 않고
간격의 크기를 점점 줄여나가
나머지 이동할 값의 횟수를 줄인다.

간격 크기 : 파란색
간격 크기에 따른 정렬할 부분 : 노란색
정렬할 값 : 초록색
정렬된 값 : 빨간색
8
7 5 6 1 4 2 3 8

간격크기 : 8
7 5 6 1 4 2 3 8
7 5 6 1 4 2 3 8

간격크기 : 4
7 5 6 1 4 2 3 8
7 5 6 1 4 2 3 8
4 5 6 1 7 2 3 8

간격크기 : 2
4 5 6 1 7 2 3 8
4 5 6 1 7 2 3 8
4 5 6 1 7 2 3 8
4 5 6 1 7 2 3 8
3 5 4 1 6 2 7 8

간격크기 : 1
3 5 4 1 6 2 7 8
3 5 4 1 6 2 7 8
3 5 4 1 6 2 7 8
3 4 5 1 6 2 7 8
1 3 4 5 6 2 7 8
1 3 4 5 6 2 7 8
1 2 3 4 5 6 7 8
1 2 3 4 5 6 7 8
1 2 3 4 5 6 7 8

#include<stdio.h>
int N, n[5001];
 
int main()
{
	scanf("%d", &N);
	for (int i = 0; i < N; i++)
		scanf("%d", &n[i]);
	for (int i = 0; i < N; i++)
	{
		int now = n[i], j = i;
		while (now < n[j - 1] && j > 0)
			n[j] = n[j - 1], j--;
		n[j] = now;
	}
	return 0;
}

//삽입과 동시에 정렬
#include<stdio.h>
int N, n[5001];
 
int main()
{
	scanf("%d", &N);
	for (int i = 0; i < N; i++)
	{
		scanf("%d", &n[i]);
		int now = n[i],j;
		for ( j = i; j > 0 && n[j - 1] >= now; j--)
			n[j] = n[j - 1];
		n[j] = now;
	}
	for (int i = 0; i < N; i++)
		printf("%d ", n[i]);
	return 0;
}

현재 인덱스의 값을
정렬이 되어있는 현재 인덱스 전의 영역에 정렬되도록 적절한 위치에 '삽입'

8
7 5 6 1 4 2 3 8
[1]
7 / 5 6 1 4 2 3 8
7 / 5 6 1 4 2 3 8
[2]
7 5 / 6 1 4 2 3 8
5 7 / 6 1 4 2 3 8
[3]
5 7 6 / 1 4 2 3 8
5 6 7 / 1 4 2 3 8
[4]
5 6 7 1 / 4 2 3 8
1 5 6 7 / 4 2 3 8
[5]
1 5 6 7 4 / 2 3 8
1 4 5 6 7 / 2 3 8
[6]
1 4 5 6 7 2 / 3 8
1 2 4 5 6 7 / 3 8
[7]
1 2 4 5 6 7 3 / 8
1 2 3 4 5 6 7 / 8
[8]
1 2 3 4 5 6 7 8
1 2 3 4 5 6 7 8

#include<stdio.h>
int n[5001],N;
 
int main()
{
	scanf("%d", &N);
	for (int i = 0; i < N; i++)
		scanf("%d", &n[i]);
	for (int i = 0; i < N; i++)
	{
		int pick = i, t;
		for (int j = i + 1; j < N; j++)
			if (n[pick] > n[j])
				pick = j;
		t = n[i];
		n[i] = n[pick];
		n[pick] = t;
	}
	for (int p = 0; p < N; p++)
		printf("%d ", n[p]);
	printf("\n");
	return 0;
}

정렬되지 않은 남은 것 내에서 가장 앞의 값과 최솟값을 '선택'하여 교환

정렬되지 않은 남은 것 중 가장 앞의 값 : 파란색
정렬되지 않은 남은 것 중 최솟값 : [ 빨간색 ]
8
8 7 6 5 4 3 2 1
/ 8 7 6 5 4 3 2 [ 1 ]
1 / 7 6 5 4 3 [ 2 ] 8
1 2 / 6 5 4 [ 3 ] 7 8
1 2 3 / 5 [ 4 ] 6 7 8
1 2 3 4 / [ 5 ] 6 7 8
1 2 3 4 5 / [ 6 ] 7 8
1 2 3 4 5 6 / [ 7 ] 8
1 2 3 4 5 6 7 / [ 8 ]
1 2 3 4 5 6 7 8

Merge Sort

#include<stdio.h>
int N, num[5010],c[5010];
void Merge(int start, int end)
{
	if (start == end)
		return;
	int mid = (start+end)/2;
	Merge(start,mid);
	Merge(mid+1, end);
 
	int i1=start, i2=mid+1,cnt= start;
 
	while (i1 <= mid && i2 <= end)
	{
		if (num[i1] > num[i2])
			c[cnt] = num[i2++];
		else
			c[cnt] = num[i1++];
		cnt++;
	}
 
	if (i1 > mid)
		while (i2 <= end)
			c[cnt++] = num[i2++];
	if (i2 > end)
		while (i1 <= mid)
			c[cnt++] = num[i1++];
 
	for (int i = start; i <= end; i++)
		printf("%d ",num[i] = c[i]);
	printf("\n");
}
 

시작과 끝을 반으로 나누고 나눠진 '두 개'를 정렬하여 합친다.

int main()
{
	scanf("%d", &N);
	for (int i = 0; i < N; i++)
		scanf("%d", &num[i]);
	Merge(0,N-1);
	for (int i = 0; i < N; i++)
		printf("%d ", num[i]);
	return 0;
}

인덱스를 0부터 시작해서 

인덱스 0 1 2 3 4 5 6 의 반은 3. [4/3] 으로 나눠짐
인덱스 1 2 3 4 5 6 7 의 반은 4. [4/3] 으로 나눠짐 

7
7 6 5 4 3 2 1
[1]
< 7 6 > 5 4 3 2 1
< 6 7 > 5 4 3 2 1

[2]
6 7 < 5 4 > 3 2 1
6 7 < 4 5 > 3 2 1

[3]
< 6 7 4 5 > 3 2 1
< 4 5 6 7 > 3 2 1

[4]
4 5 6 7 < 3 2 > 1
4 5 6 7 < 2 3 > 1

[5]
4 5 6 7 < 2 3 1 >
4 5 6 7 < 1 2 3 >

[6]
< 4 5 6 7 1 2 3 >
< 1 2 3 4 5 6 7 >

상향식은 n에서 시작

즉 호출을 base까지 한 후 base 부터 차곡차곡 올라간다.

하향식은 base부터차곡차곡 올라간다.

그래서 초깃값을 설정해주는 경우가 많다.