배열과 선택 정렬 Selection Sort

배열과 선택 정렬 Selection Sort

맛있는 음식이 여러가지 있을 때 어느 것을 먼저 먹을지 순서를 정하기도 하고,

사람이 여러명 있을 때 키 순서대로 세워보기도 한다.

이렇게 순서를 맞춰주는 것을 정렬 sorting 이라고 부른다.

 

배열의 사용법을 연습해보기 위해서 정렬방법들 중 비교적 간단한 편에 속하는 선택정렬을 배워 보겠다.

먼저 선택정렬이 어떻게 이루어 지는지 살펴보자.

선택 정렬 Selection Sort

선택 정렬은 다음 단계를 수행해서 배열을 오름차순으로 정렬한다.

 

1. 배열 index 0에서 시작하여 배열 전체를 검색해서 가장 작은 값을 찾는다.

2. 배열에서 찾은 가장 작은 값을 index 0의 값과 swap한다.

3. 다음 index에서 1단계와 2단계를 반복한다.

 

즉, 배열에서 찾은 가장 작은 요소를 찾아 첫 번째 위치로 바꾼다.

그 다음으로 가장 작은 요소를 찾아 두 번째 위치로 바꾼다.

이 과정을 요소의 끝에 도달할 때 까지 반복한다.

 

다음은 위 알고리즘을 어떻게 동작하는지 설명하는 예다.

 

먼저 배열을 살펴보자

{ 3, 5, 2, 1, 4 }

 

먼저 index 0부터 시작하여 가장 작은 요소를 찾는다.

{ 3, 5, 2, 1, 4 }

 

그 다음 이 값을 index 0 의 요소와 swap 한다.

{ 1, 5, 2, 3, 4 }

 

이제 첫 번째 요소가 정렬 되었으므로 무시 할 수 있다.

다음 index 1부터 시작해서 가장 작은 요소를 찾는다.

{ 1, 5, 2, 3, 4 }

 

그리고 index 1의 요소와 swap 한다.

{ 1, 2, 5, 3, 4 }

 

이제 처음 두 요소를 무시 할 수 있다.

index 2부터 시작해서 가장 작은 요소를 찾는다.

{ 1, 2, 5, 3, 4 }

 

그리고 index 2의 요소와 swap 한다.

{ 1, 2, 3, 5, 4 }

 

index 3부터 시작해서 가장 작은 요소를 찾는다.

{ 1, 2, 3, 5, 4 }

 

그리고 이것을 index 3의 요소와 swap 한다.

{ 1, 2, 3, 4, 5 }

 

마지막으로 index 4에서 시작하는 가장 작은 요소를 찾는다.

{ 1, 2, 3, 4, 5 }

 

index 4에 있는 요소와 swap 한다. (아무것도 작동하지 않는다.)

{ 1, 2, 3, 4, 5 }

 

정렬이 끝났다.

{ 1, 2, 3, 4, 5 }

 

마지막 비교는 항상  그 자체이기 때문에 생략할 수 있다.

C++에서의 선택 정렬 구현 Selection Sort in C++

c++ 에서 선택 정렬 알고리즘을 구현하는 방법은 다음과 같다.

 

먼저 array 안에 있는 값들을 찍어주는 코드를 작성하고

 

for문으로 array안에 있는 값들을 모두 출력하는 코드

함수로 만든다.

 

array를 함수의 파라미터로 넣는 방법은 앞서 포스팅함.

이 printArray 함수에서는 array를 출력만하지 array값을 바꿔주지 않으니까 실수를 줄이고자 const 붙여줌

 

++ 값 교차시키는 swap 하는 방법

보통 temp를 둔다.

std::swap 함수도 있음.

 

여기서 std::swap 을 쓰려면 #include <algorithm> 해야한다.

이 알고리즘의 가장 혼란스러운 부분은 중첩 루프다.

외부 루프(startIndex) 는 각 요소를 하나씩 반복한다.

각 외부 루프 반복에서 내부 루프(currentIndex)를 사용하여 나머지 배열(startIndex+1에서 시작)에서 값이 가장 작은 요소를 찾는다.

smallestIndex는 내부 루프에 의해 발견된 가장 작은 요소의 인덱스를 저장한다.

그러면 smallestIndex가 startIndex와 swap된다. 

이와 같은 프로세스가 반복된다.

 

헷갈리는 부분 설명

여기서 -1은 마지막엔 더이상 찾을게 없으니까, 마지막 하나는 항상 그 자체이기 때문에 생략 해줌.

std::sort

배열을 정렬하는 것은 매우 흔한 일이므로

C++ 표준 라이브러리인 <algorithm> 헤더에 std::sort 하는 정렬 함수가 포함되어 있다.

#include <algorithm> //for std::sort
#include <iostream>

int main()
{
    const int length = 5;
    int array[length] = { 3, 5, 2, 1, 4 };
    
    std::sort(array,array+length);
    
    for(int i = 0; i < length; ++i)
    std::cout << array[i] << '';
    
    return 0;
}

 

1부터 10까지 선택정렬 연습해보기