지식공유

안녕하세요.

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

삽입 정렬 알고리즘

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

구현 방법

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

예제

배열 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)]를 스왑 하는 건 의미가 없으므로 최종 정렬이 됩니다.

코드

안녕하세요

정렬 알고리즘 중 가장 구현하기 쉬운 버블 정렬 알고리즘에 대해 알아보도록 하겠습니다.

버블 정렬 알고리즘

배열등 리스트에서 인접한 데이터들을 비교하여 정렬하는 알고리즘

구현 방법

오름차순 기준(제일 작은 값이 앞으로, 제일 큰 값이 뒤로 정렬)으로 설명하면,
첫 번째 데이터를 모든 데이터와 비교하면서 첫 번째 데이터가 더 크면 서로 스왑 하고,
다음 두 번째 데이터를 모든 데이터와 비교하면서 두 번째 데이터가 더 크면 서로 스왑 하는 과정을
마지막 데이터-1까지 계속 반복합니다.

예제

배열 arrData에 100, 20, 10, 12, 5 값이 있다면, 이 배열 데이터를 정렬하면 다음과 같이할 수 있습니다.

arrData의 첫번째 값 100을 두 번째 값 20과 비교했을 때, 100이 더 크기 때문에 두 값을 스왑 합니다.(20, 100, 10, 12, 5)
arrData의 두번째 값 100을 세 번째 값 10과 비교했을 때, 100이 더 크기 때문에 두 값을 스왑 합니다.(20, 10, 100, 12, 5)
arrData의 세번째 값 100을 네 번째 값 12과 비교했을 때, 100이 더 크기 때문에 두 값을 스왑 합니다.(20, 10, 12, 100, 5)
arrData의 네번째 값 100을 다섯 번째 값 5과 비교했을 때, 100이 더 크기 때문에 두 값을 스왑 합니다.(20, 10, 12,  5, 100)

arrData의 첫번째 값 20을 두 번째 값 10과 비교했을 때, 20이 더 크기 때문에 두 값을 스왑 합니다.(10, 20, 12,  5, 100)
arrData의 두번째 값 20을 세 번째 값 12과 비교했을 때, 20이 더 크기 때문에 두 값을 스왑 합니다.(10, 12, 20, 5, 100)
arrData의 세번째 값 20을 네 번째 값 5과 비교했을 때, 20이 더 크기 때문에 두 값을 스왑 합니다.(10, 12, 5, 20, 100)

arrData의 첫번째 값 10을 두 번째 값 12과 비교했을 때, 10이 더 작기 때문에 두 값을 스왑 하지 않습니다.(10, 12, 5, 20, 100)
arrData의 두번째 값 12를 세 번째 값 5과 비교했을 때, 12이 더 크기 때문에 두 값을 스왑 합니다.(10, 5, 12, 20, 100)

arrData의 첫번째 값 10을 두 번째 값 5과 비교했을 때, 10이 더 크기 때문에 두 값을 스왑 합니다.(5, 10, 12, 20, 100)

C++로 구현

순차 탐색 알고리즘이란?
순차 탐색 알고리즘(Sequential Search Algorithm)은 단순히 배 열등의 데이터 리스트에서 순차적으로 데이터를 비교하여 원하는 데이터를 찾아내는 알고리즘입니다.
특별히 이진탐색 알고리즘 등과 같이 정렬을 우선해야 하는 번거로움이 없이 사용이 가능하며, 단순하며 구현이 쉬운 장점을 갖고 있습니다.
하지만 데이터가 많은 경우에는 비효율적인 알고리즘입니다.
단방향으로 검색하기 때문에 선형 알고리즘(Linear Search Algorithm)이라고도 합니다.

예시
10개의 데이터를 가진 배열 arr 값이 10, 30, 50, ,80, 100, 120, 150, 180, 220, 250를 가지고 있으며,
찾을 데이터가 180인 경우,
순차적으로 

1번째에는 10과 비교하고, 

2번째는 30과 비교하고,

3번째는 50과 비교하고,

4번째는 80과 비교하고,

5번째는 100과 비교하고,

6번째는 120과 비교하고,

7번째는 150과 비교하고,

180을 가진 8번째 값(배열인덱스는 7)인 값을 찾게 됩니다.

C++ 코드로는 다음과 같습니다.

이진 탐색이란?
이진 탐색(Binary Search)은 데이터로 정렬되어 있는 경우, 정렬된 값의 반에 해당되는 값과 계속 비교를 해서 검색 범위를 줄여, 원하는 값을 빠르게 찾아나가는 알고리즘을 말합니다.


예시
배열인 arr값이 10, 30, 50, ,80, 100, 120, 150, 180, 220, 250으로 배열에 저장되어있고,

여기서 50이 배열 어느 인덱스에 위치하는지 알고자 한다고 합시다.

배열의 최소 인덱스(nLow)는 0이고, 최대 인덱스(nHigh)는 9입니다.

최소 인덱스(nLow)와 최대 인덱스(nHigh)를 더한 후 2로 나눕니다.

그럼 중간값(nMid)이 나오게 됩니다.

입력값과 같은 값이 나올 때까지 이 과정을 반복하게 됩니다.

첫 번째에서는 

nLow = 0, nHigh = 9, nMid = (nLow + nHigh) / 2 = 4

arr[nMid]는 100이 나오게 되는데, 입력값보다 100은 큰 값이므로,

nHigh에 nMid에 1을 뺀 값을 넣습니다.(nHigh = nMid - 1)

두 번째에서는

nLow = 0, nHigh = 3, nMid = (nLow + nHigh) / 2 = 1

arr[nMid]는 30이 나오는데, 입력값보다 30은 작기 때문에

nLow에 nMid에 1 더한 값을 넣습니다.(nLow = nMid + 1)

세 번째에서는

nLow = 2, nHigh = 3, nMid = (nLow + nHigh) / 2 = 2

arr[nMid]는 50이므로, 입력값과 같은 값이 나오게 됩니다.

2번째 인덱스에 50 값을 찾았습니다.

C++ 코드로는 다음과 같습니다.