3장-1. 배열 정렬

정렬이란?

• 임의로 정렬된 배열의 객체들을 오름차순으로 재배열하는 법

 

---

삽입 정렬

1. 첫 번째 원소에서 시작한다.
2. 배열의 다음 원소가 첫 번째 값보다 작다면 바꾼다 (1 <-> 2)
3. 세 번째 원소에 대해 비교해보고 작다면 바꾼다.

 

#include <iostream>

using namespace std;


void insertionSort(char* A, int n)
{
	for (int i = 1; i < n; i++)
	{
		char cur = A[i];
		int j = i - 1;// j는 i -1에서 시작해서 0번까지 순회한다.

							// A[i-1] > A[i] = chArr[0] > chArr[1]
		while ((j >= 0) && (A[j] > cur))
		{
			A[j + 1] = A[j];// chArr[1] = chArr[0]
			j--;
		}

		// chArr[1] + chArr[1]
		A[j + 1] = cur;// j가 변하면 그제서야 의미를 가짐
	}

	// A[i]에 있는 값과 A[i-1]을 비교하며 A[i]가 A[i-1]보다 작다면 덮어쓴다
	// while문 내부에 j--을 통해 0으로 향해 가는 여정을 반복하고 (계속 덮어쓰며)
	// 자신의 위치를 찾았으면 맨 처음에 저장해두었던 i번째에 있던 요소를
	// j가 맞는 위치에 (while 탈출 시) A[j + 1]에 집어넣는다.
}

• "zzzzzzza"라는 문자열이 있는 경우,
• 맨 후열의 a를 찾을 때까지 탐색하며, a를 찾은 경우
• a를 cur(A[i])에 저장하고
• while문을 통해 a[i-1]를 비교하여 a를 z로 덮어씌우며 0번 인덱스를 향해 후진한다.
• 1번째 행도 cur보다 클 경우 j--에 의해 j는 -1이 되고 while문을 탈출하며
• A[j+1] = A[0]에 cur('a')을 집어넣게 된다.