By Standing On The Shoulders Of Giants

#include<stdio.h>
#define INF 1000000000
int V, E,
	graph[401][401];
 
int main() {
	scanf("%d %d", &V, &E);
 
	//1. 초기화 1) i->i 로의 가중치 0 , 연결되지 않은 가중치 INF
	for (int i = 1; i <= V; i++) {
		graph[i][i] = 0;
		for (int j = 1; j <= V; j++)
			graph[i][j] = INF;
	}
	for (int e = 0; e < E; e++) {
		int a, b, c;
		scanf("%d %d %d", &a, &b, &c);
		graph[a][b] = c;
	}
 
	//2. 플로이드 와샬 알고리즘
	for(int k = 1; k<=V;k++)
		for(int f = 1; f<=V;f++)
			for (int t = 1; t <= V; t++) {
				int temp = graph[f][k] + graph[k][t];
				if (graph[f][t] > temp)	graph[f][t] = temp;
			}

	return 0;
}

- 재귀(호출 후 동작)

- 시간복잡도는 균일하므로 쓰기 좋음

- 리스트 정렬 시 효과적

코드

int arr[Max + 1];
int temp[Max + 1];
 
void merge(int left, int right) {
 
	int idx1 = left;
	int mid = left + (right - left) / 2;
	int idx2 = mid + 1;
	int idxTemp = 0;
 
	while (idx1 <= mid && idx2 <= right) {
		if (arr[idx1] <= arr[idx2])
			temp[idxTemp++] = arr[idx1++];
		else
			temp[idxTemp++] = arr[idx2++];
	}
 
	while (idx1 <= mid)
		temp[idxTemp++] = arr[idx1++];
 
	while (idx2 <= right)
		temp[idxTemp++] = arr[idx2++];
 
	for (int i = left; i <= right; i++)
		arr[i] = temp[i - left];
}
 
void mergeSort(int left, int right) {
	if (left == right)
		return;
 
	int mid = left + (right - left) / 2;
	mergeSort(left, mid);
	mergeSort(mid + 1, right);
 
	merge(left, right);
}

설명

시간복잡도 : NlogN

logN 회 : 호출 후 동작

N 회 비교 : 배열 [1,2,3] [4,5] 의 merge 과정

관련문제 

수 정렬하기 2 www.acmicpc.net/problem/2751

1. 정렬할 때 가장 적합한 알고리즘은?

A. 빠른 정렬을 할 수있는 알고리즘

이라고 말할 수 있다.

알고리즘은 성능이 중요하기 때문이다.

그렇다면 빅오에 의해 성능이 좋아보이는 Quick Sort나 Merge Sort가 가장 적합한 알고리즘일까?

그렇지 않다.

빠른 정렬을 할 수 있는 알고리즘은

주어진 데이터 상태에 따라 빠르기가 달리지기 때문이다.

1 2 3 4 5 6 7 8 - 정렬

1 3 5 7 2 4 6 8 - 뒤죽박죽

8 7 6 5 4 3 2 1 - 역순

1 1 2 1 1 3 4 5 - 같은 값

2. 정렬할 때 고려할 조건은?

1) 데이터의 정렬 상태

 - 데이터 크기, 정렬, 뒤죽박죽, 역순, 같은 값

2) 메모리 사용

3) 정렬의 안정성

 안정적이다 = 같은 값이라도 같은 값 끼리의 순서를 유지해준다. 

 불안정적이다 = 같은 값끼리의 순서유지가 되지 않는다.

mod 연산의 용도 : 결과값이 큰 수의 연산을 작은 수로 출력하고 싶을 때 유용히 사용

두 수를 연산한 결과가 자료형을 초과할 수 있으므로

mod 연산의 성질을 이용하여

두 수를 줄여서 연산한 결과도 줄인 상태로 계산한다.

#include<stdio.h>
int N, n[5001];
void Q(int S, int E)
{
	if (S < E)
	{
		int L, R, p, t;
		L = S - 1;
		R = E + 1;
		p = n[(S + E) / 2];
		while (L < R)
		{
			while (p > n[++L]);
			while (p < n[--R]);
			if (L >= R)break;
			t = n[L];
			n[L] = n[R];
			n[R] = t;
		}
		Q(S, L -1);
		Q(R+1, E);
	}
}
int main()
{
	scanf("%d", &N);
	for (int i = 0; i < N; i++)
		scanf("%d", &n[i]);
	Q(0,N-1);
	for (int i = 0; i < N; i++)
		printf("%d ", n[i]);
	return 0;
}