선택정렬

• 배열의 각 셀을 왼쪽부터 오른쪽 방향으로 확인하면서 어떤 값이 최솟값인지 결정하는 정렬이다.

[5, 3, 6, 1, 4]

• 위 배열을 선택정렬 방식으로 정렬해 보겠다.

[5, 3, 6, 1, 4]

• 우선 인덱스 0에 들어 있는 값을 확인하며 시작한다. 현재 본 유일한 값은 5이기 때문에 인덱스에 저장한다.
• 3과 비교한다. 3은 5보다 작기 때문에 최솟값이 된다.
• 3을 6과 비교하면 여전히 최솟값이 된다.
• 3을 1과 비교하면 1이 작기 때문에 최솟값이 1로 변경된다.
• 1은 4보다 작기 때문에 최솟값을 유지한다.
• 배열에서 최솟값이 1이기 때문에 인덱스 0값과 자리를 바꾼다.
  [1, 3, 6, 5, 4]
• 인덱스 0의 값이 정해졌으니 인덱스 1의 최솟값을 찾기 위해 위 과정을 반복한다.

이러한 정렬과정을 선택정렬이라고 한다.

삽입정렬

• 각 값이 배열의 어떤 위치에 들어갈지 찾는 정렬이다.

[5, 3, 6, 1, 4]

• 위 배열을 삽입정렬 방식으로 정렬해 보겠다.

[5, 3, 6, 1, 4]

• 인데스 1번부터 시작하면 3이 들어갈 자리를 찾아야한다.
• 3은 5보다 작기 때문에 5가 인덱스 1번 자리고 가고 3은 인덱스 0번 자리에 들어가게 된다.
  [3, 5, 6, 1, 4]
• 6이 들어갈 자리를 찾으면 된다. 6은 인덱스 0,1번보다 크기 때문에 자리변동은 없다.
  [3, 5, 6, 1, 4]
• 1이 들어갈 자리를 찾는다. 1은 인덱스 0,1,2번 값보다 모두 작기 때문에 인덱스 0번 자리에 들어가게 되고 나머지 값들은 뒤로 한칸씩 옮긴다.
  [1, 3, 5, 6, 4]
• 4가 들어갈 자리를 찾는다. 4는 5보다 작기 때문에 인덱스 2번 자리에 들어가고 5와6은 뒤로 한칸씩 옮긴다.
  [1, 3, 4, 5, 6]

이러한 정렬과정을 삽입정렬이라고 한다.