알고리즘 노팅 - 정렬 종류와 구현(삽입정렬)

1. ToDo

- 그냥 문득 내용을 공부하면서 정리하고 싶어진 정렬 알고리즘

2. 종류

• 선택 정렬

• 삽입 정렬

• 버블 정렬

• 합병 정렬

• 퀵 정렬

3. 개념설명

• 글로 끄적..
  
  평균 시간 복잡도가 모두 O(n^2), 즉 삽입 정렬과 같이 데이터 수에 따라 정렬 속도가 급격히 차이 난다. 선택 정렬과는 다르게 첫 번째가 아니라 두 번째 대상부터 비교를 시작한다. 비교 후 타겟이 비교 대상보다 작은 경우 왼쪽으로 이동하게 된다. 이때 타켓은 고정이고 타겟이 비교 대상보다 클 경우가 나올 때까지 계속된다.
  

• 그림으로 쓱삭..
  
  아래와 같은 그림으로 진행되고 (배열의 수 - 1)만큼 반복한다.(아래 그림은 최솟값 기준이고 최댓값도 동일하게 작용한다.)
  
  
  
  

4. 코드로 투닥투닥.. (C#)

int[] array = { 7, 5, 4, 3, 8, 9, 10, 2, 6, 1 };
int temp = 0;

for (int i = 1; i < array.Length; i++)
{
	for (int j = 0; j < i + 1; j++)
	{
		if (array[i] < array[j])
		{
			temp = array[i];
			array[i] = array[j];
			array[j] = temp;
		}
	}
}

for (int i = 0; i < array.Length; i++)
{
	Console.Write(array[i] + " ");
}