지식공유

안녕하세요.

오늘은 삽입 정렬 알고리즘에 대해 알아보도록 하겠습니다.

삽입 정렬 알고리즘

데이터를 정렬 위치에 맞게 삽입하면서 정렬하는 알고리즘

구현 방법

오름차순 기준으로 설명하겠습니다.
두 번째 데이터부터 첫 번째 데이터랑 비교 후 두 번째 데이터가 작다면, 두 값을 스왑 하고,
세 번째 데이터를 첫 번째, 두 번째와 비교 후 세 번째 데이터보다 큰 값이 있다면 값이 하나씩 뒤로 밀리게 됩니다.
이것을 반복합니다.

예제

배열 arrData에 100, 20, 10, 12, 5 값이 있다면, 다음과 같이 정렬이 되게 됩니다.

첫 번째 회전
두번째 데이터 arrData[1](20)를 임시 변수에 저장합니다.
임시 변수와 첫 번째 데이터와 비교하면, 임시 변수 데이터인 20이 첫 번째 데이터인 arrData[0](100)보다 작기 때문에 arrData[0]을 arrData[1]로 이동합니다.
그리고 임시 변수에 저장한 값을 arrData[0]에 저장합니다. (20, 100, 10, 12, 5)

두 번째 회전
세 번째 데이터 arrData[2](10)를 임시 변수에 저장합니다.
임시 변수와 두 번째 데이터와 비교하면, 임시변수 데이터인 10이 두 번째 데이터인 arrData[1](100)보다 작기 때문에 arrData[1]을 arrData[2]로 이동합니다.
임시 변수와 첫 번째 데이터와 비교하면, 임시 변수 데이터인 10이 두 번째 데이터인 arrData[0](20)보다 작기 때문에 arrData[0]을 arrData[1]로 이동합니다.
그리고 임시 변수에 저장한 값을 arrData[0]에 저장합니다. (10, 20, 100, 12, 5)

세 번째 회전
네 번째 데이터 arrData[3](12)를 임시 변수에 저장합니다.
임시 변수와 세 번째 데이터와 비교하면, 임시 변수 데이터인 12가 세 번째 데이터인 arrData[2](100)보다 작기 때문에 arrData[2]을 arrData[3]로 이동합니다.
임시 변수와 두 번째 데이터와 비교하면, 임시 변수 데이터인 12가 두 번째 데이터인 arrData[1](20)보다 작기 때문에 arrData[1]을 arrData[2]로 이동합니다.
임시 변수와 첫 번째 데이터와 비교하면, 임시 변수 데이터인 12가 첫 번째 데이터인 arrData[0](10)보다 크기 때문에 이동을 멈춥니다.
임시 변수에 저장한 값을 arrData[1]에 저장합니다. (10, 12, 20, 100, 5)

네 번째 회전
다섯 번째 데이터 arrData[4](5)를 임시 변수에 저장합니다.
임시 변수와 네 번째 데이터와 비교하면, 임시 변수 데이터인 5가 네 번째 데이터인 arrData[3](100)보다 작기 때문에 arrData[3]을 arrData[4]로 이동합니다.
임시 변수와 세 번째 데이터와 비교하면, 임시 변수 데이터인 5가 세 번째 데이터인 arrData[2](20)보다 작기 때문에 arrData[2]을 arrData[3]로 이동합니다.
임시 변수와 두 번째 데이터와 비교하면, 임시 변수 데이터인 5가 두 번째 데이터인 arrData[1](12)보다 작기 때문에 arrData[1]을 arrData[2]로 이동합니다.
임시 변수와 첫 번째 데이터와 비교하면, 임시 변수 데이터인 5가 첫 번째 데이터인 arrData[0](10)보다 작기 때문에 arrData[0]을 arrData[1]로 이동합니다.
임시 변수에 저장한 값을 arrData[0]에 저장합니다. (5, 10, 12, 20, 100)

C++ 코드로 구현

안녕하세요.

오늘은 선택 정렬 알고리즘에 대해 알아보도록 하겠습니다.

선택 정렬 알고리즘

배열등 리스트에서 배열 위치에 맞게 오름/내림 정렬하는 알고리즘

구현 방법

오름차순 기준(제일 작은 값이 앞으로, 제일 큰 값이 뒤로 정렬)으로 설명하면,
첫 번째 데이터를 전체 데이터와 비교하여, 첫 번째 데이터와 제일 작은 값을 스왑 합니다.
다음 두 번째 데이터와 첫 번째를 제외한 전체 데이터와 비교하여 두 번째 데이터와 2번째로 작은 값을 스왑 합니다.
이것을 반복합니다.

예제

배열 arrData에 100, 20, 10, 12, 5 값이 있고, 최소값이 저장된 인덱스를 저장하기 위한 변수가 nIndex라면 다음과 같이 정렬됩니다.
nIndex의 초기값은 첫 번째 인덱스인 0입니다.

arrData[nIndex]의 값 100을 두 번째 값 20과 비교했을 때, 20이 더 작기 때문에 1을 nIndex에 저장합니다.
arrData[nIndex]의 값 20을 세 번째 값 10과 비교했을 때, 10이 더 작기 때문에 2를 nIndex에 저장합니다.
arrData[nIndex]의 값 10을 네 번째 값 12과 비교했을 때, 12이 더 크기 때문에 넘깁니다.
arrData[nIndex]의 값 10을 다섯 번째 값 5과 비교했을 때, 5가 더 작기 때문에 4를 nIndex에 저장합니다.
그 후 arrData[0]과 arrData[nIndex(=4)]를 스왑 합니다.(5, 20, 10, 12, 100)

다음으로 nIndex에 1을 넣고 비교를 합니다.
arrData[nIndex]의 값 20을 세 번째 값 10과 비교했을 때, 10이 더 작기 때문에 2를 nIndex에 저장합니다.
arrData[nIndex]의 값 10을 네 번째 값 12과 비교했을 때, 12이 더 크기 때문에 넘깁니다.
arrData[nIndex]의 값 10을 다섯 번째 값 100과 비교했을 때, 100이 더 크기 때문에 넘깁니다.
그 후 arrData[1]과 arrData[nIndex(=2)]를 스왑 합니다.(5, 10, 20, 12, 100)

다음으로 nIndex에 2를 넣고 비교를 합니다.
arrData[nIndex]의 값 20을 네 번째 값 12과 비교했을 때, 12이 더 작기 때문에 3을 nIndex에 저장합니다.
arrData[nIndex]의 값 12를 다섯 번째 값 100과 비교했을 때, 100이 더 크기 때문에 넘깁니다.
그 후 arrData[2]과 arrData[nIndex(=3)]를 스왑 합니다.(5, 10, 12, 20, 100)

다음으로 nIndex에 3을 넣고 비교를 합니다.
arrData[nIndex]의 값 20을 다섯 번째 값 100과 비교했을 때, 100이 더 크기 때문에 넘깁니다.
그 후 arrData[3]과 arrData[nIndex(=3)]를 스왑 하는 건 의미가 없으므로 최종 정렬이 됩니다.

코드