오늘의 포스팅 주제는 컴퓨터 알고리즘 중 '선택정렬'입니다.
안녕하세요!! @wonnieyoon입니다.
<p dir="auto">정렬이란? 특정 기준으로 줄을 세우는것이라 볼수 있습니다.<br />
선택정렬이란?<br />
먼저 정렬 알고리즘 중에 가장 느린 정렬입니다.<br />
순차적으로 가장 작은것을 젤 앞에 보내는 정렬이라고 생각하시면 될듯 합니다.<br />
반대로 가장 큰것을 젤 앞에 보내는 정렬이라고 생각하셔도 됩니다.
<p dir="auto">선택정렬이란 ?<br />
오름차순이라면 제일 작은수를 선택해서 앞으로 보내는 방법,<br />
내림차순이라면 가장 큰수를 선택해서 앞으로 보내는 방법
<p dir="auto">※선택정렬<br />
<소스코드>
<p dir="auto">int main()<br />
{<br />
int data[6] = { 7, 5, 3, 1, 8, 4 };<br />
int position = 0;
<pre><code>for (int i = 0; i < 6; i++)
{
int tempMin = INT_MAX;
for (int j = i; j < 6; j++)
{
if (tempMin > data[j])
{
tempMin = data[j];
position = j;
}
}
int temp = data[i];
data[i] = data[position];
data[position] = temp;
}
for (int i = 0; i < 6; i++)
{
cout << data[i] << "\t";
}
return 0;
<p dir="auto">}<br />
<출력결과><br />
<img src="https://images.hive.blog/768x0/https://cdn.steemitimages.com/DQmYuNqNjTrt21XKZntg4zTgGahG6mFYy4rN6UohQB3c12d/image.png" srcset="https://images.hive.blog/768x0/https://cdn.steemitimages.com/DQmYuNqNjTrt21XKZntg4zTgGahG6mFYy4rN6UohQB3c12d/image.png 1x, https://images.hive.blog/1536x0/https://cdn.steemitimages.com/DQmYuNqNjTrt21XKZntg4zTgGahG6mFYy4rN6UohQB3c12d/image.png 2x" />
<p dir="auto">코드를 보시면 알겠지만 특별히 어렵지는 않습니다.<br />
하지만 데이터가 있다면 모든 데이터를 읽으면서 가장 작은수를 찾기 때문에<br />
만약 데이터가 100개 있다면<br />
처음에는 100개, 두번째는 99개, 세번째는 98, .....마지막은 1개 순으로 검색을 하게 됩니다.
<p dir="auto">등차수열이기 때문에 100 * (100+1) / 2 로 나타낼수 있고<br />
이것은 N * (N + 1) / 2 라고 할수 있습니다.<br />
결국 컴퓨터에서는 +1 , /2 는 수가 커지면 큰 영향을 미치지 않기 때문에<br />
선택 정렬의 시간 복잡도는 O(N^2) 가 됩니다.
<p dir="auto">선택정렬 시간복잡도 : O(N^2)