정렬 알고리즘[1] -- 선택 정렬 알고리즘

선택 정렬 알고리즘이란?

 

배열의 값들중  가장작은 값을 구한후 앞쪽으로 이동시키는 방법!

 

만약

3 4 5 1 2 라는 배열이 있다면

 

1 4 5 3 2   --가장 작은 1과 앞자리 3을 변경

1 2 5 3 4   --그 다음 작은 2과 앞자리 4을 변경

1 2 3 5 4   --그 다음작은 3과 앞자리 5을 변경

1 2 3 4 5    --그 다음작은 4과 앞자리 5을 변경

 

이런식으로 swap을 통해 작은 순서대로 정렬시키는 알고리즘입니다.

 

이런식으로 구성하기 위해 코드에서 필요한 부분을 적어보면

1. 가장작은 숫자 탐색

2. count로 어디까지 정렬되었는지 표시

3. 두 위치를 swap을 통해 위치변경

 

이렇게 3단계로 이루워 질것 같습니다.

 

코드 시작!

 

코드 1

#include <iostream>
#include <string>
using namespace std;

void swap(int (&arr)[5],int i,int j){//함수
    int temp=0;
    temp=arr[i];
    arr[i]=arr[j];
    arr[j]=temp;
}


int main()
{
  int a[5]={1,4,5,3,2};
  int index=0;
  int minnum=10000;
  int minindex=0;
  
  while(index!=4){
      minnum=10000;
        for(int i=index;i<5;i++){//가장작은 지점찾기
            if(minnum>a[i]){
                minnum=a[i];
                minindex=i;
            }
        }
        cout<<"-----------"<<endl;
        swap(a,minindex,index);//스왑해주기
        index+=1;
        
        for(int i=0;i<5;i++){//출력
            cout<<a[i]<<"|";
        }
        cout<<endl;
      }
    return 0;
}

간단한 swap함수를 만들어주고

 

minnum인 10000과 비교하여 작으면 minindex를 최신화 --- 이 작업을 계속 반복하여 최솟값을 찾아줍시다.

(여기서 for문은 이미 정렬된 0~ index까지는 제외 한 후에 돌려야됩니다!)

 

코드2

#include <iostream>
#include <vector>

using namespace std;


int main(){
    int num[101];
    
    int count;

    cin>>count;
    int n;

    for(int i=0;i<count;i++){
        cin>>n;
        num[i]=n;
    }


    int idx;
    int temp;

    for(int i=0;i<count;i++){
        idx=i;
        for(int j=i+1;j<count;j++){
            
            if(num[idx]>num[j]){//젤작은거
               idx=j;
            }
        }

        temp=num[idx];
        num[idx]=num[i];
        num[i]=temp;
    }



    for(int i=0;i<count;i++){
        cout<<num[i]<<",";
    }
    cout<<endl;



    return 0;

}

 

만들고 보니 계속해서 최솟값을 찾는 비효율적인 부분이 아쉽네요

 

장점 : 구현하기 쉽다

단점 : 비효율적이다....

 

 

 

틀린점이 있다면 댓 달아주세요!