[알고리즘] 선택정렬(Select sort)

알고리즘

 

선택정렬(Selection sort)

 

 

 

 

간단 요약

 

가정) Array[5]= { 15 ,11 ,1 ,3 ,8 } 을 오름차순으로 정렬한다.

 

1.  0번 부터 4번 데이터 중 최솟값을 찾아 0번 데이터와 스왑한다.

 

2.  1번 부터 4번 데이터 중 최솟값을 1번 데이터와 스왑한다.

 

3.  n번 반복

 

상세 설명

 

가정) Array[5]= { 15 ,11 ,1 ,3 ,8 } 을 오름차순으로 정렬한다.

 

 

 

 

 가장 먼저 전체 인덱스 중 최솟값을 찾는다.

 

 

 

 

최솟값 1을 첫번째 인덱스와 스왑한다.

 

 

 

 

 

그 다음 두번째에서 네번째 데이터 중 최솟값을 찾는다.

최솟값 3을 두번째 데이터 와 스왑한다.

여기까지 하면 두번째 데이터 까지 오름차순 정렬이 완성된다.

 

 

 

 

 

이렇게 n번 반복하면 오름차순 정렬이 완성된다 

 

 

시간복잡도

 

 

 

코드

 

#include <iostream>
#define number 5
 
using namespace std;
 
void Selectsort(int * arr)
{
    for (int i = 0; i < number-1; i++) { //인덱스가 5까지라면 4까지만 가도록 설정
        int min= i;
        for (int j = i + 1; j < number; j++) { 
            if (arr[j] < arr[min]){//j의 인덱스가 최솟값보다 작다면 min=j
                min = j;
            }
        }
        int temp = arr[min]; //min값을 가장 왼쪽으로 보낸다
        arr[min] = arr[i];
        arr[i] = temp;
    }
}
 
 
int main(void)
{
    int arr[5] = { 15, 11, 1, 3, 8 };
    int i;
 
    for (i = 0; i < 5; i++) {
 
        cout << arr[i] << " ";
    }
    cout << "\n\n";
    Selectsort(arr);
    for (i = 0; i < 5; i++) {
        cout << arr[i] << " ";
    }
 
    return 0;
 
}
 

 

 출처 : https://gmlwjd9405.github.io/2018/05/06/algorithm-selection-sort.html

 출처 : https://terms.naver.com/entry.nhn?docId=2270435&cid=51173&categoryId=51173