[Algorithm] 선택정렬(c/c++)

#. Problem

https://www.inflearn.com/course/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

* The copyright in this matter is in Inflearn

#. Resolution Process

  1. Read and understand problem

  2. Redefine the problem + abstract

  3. Create solution plan (select Algorithm, Data structure)

  4. Prove the plan (check performance time and usage memory)

  5. Carry out the plan

  6. Look back on the plan and find a way to improve it

#. Solve

  1. 선택정렬은 전체 원소들 중 기준 위치에 맞는 원소를 선택하여 자리를 교환하는 방식이다.

     구현은 간단하지만 비효율적인 특징이 있다..

     selection sort 의 시간복잡도는 아래와 같다.

     Best : O(n^2)

     Average : O(n^2)

     Worst : O(n^2)

     13 5 11 7 23 15 를 정렬해야할 때,

     i = 0,

     13, 5보다 크므로 교환,  5 13 11 7 23 15

     5보다 큰 숫자는 없으므로 다음

     i = 1

     13, 11보다 크므로 교환, 5 11 13 7 23 15

     11, 7보다 크므로 교환, 5 7 13 11 23 15

     7보다 큰 숫자는 없으므로 다음

     i = 2

     13, 11보다 크므로 교환, 5 7 11 13 23 15

     11보다 큰 숫자는 없으므로 다음

     i = 3

     13보다 큰 수는 없으므로 다음

     i = 4

     23, 15보다 크므로 교환, 5 7 11 13 15 23

     정렬 완료.!

  2. 1번의 방법보다 교환 횟수를 더 줄여보자..!

     위 방법대로 하면 거의 버블정렬 수준으로 되어버린다...

     13 5 11 7 23 15 를 정렬할 때,

    i = 0, idx = 0

    13, 뒤에 있는 숫자들 중 최솟값의 위치는 1 이다. idx = 1

    i와 idx 위치 원소를 교환, 5 13 11 7 23 15

    i = 1, idx = 1

    13, 뒤에 있는 숫자들 중 최솟값의 위치는 3, idx = 3

    i 와 idx 위치 원소를 교환, 5 7 11 13 23 15

 

    i = 2, idx = 2

    11, 뒤에 있는 숫자들 중 최솟값의 위치는 2, idx = 2

    i 와 idx 위치 원소를 교환(그대로), 5 7 11 13 23 15

    i = 3, idx = 3

    13, 뒤에 있는 숫자들 중 최솟값의 위치는 3, idx = 3

    i 와 idx 위치 원소를 교환(그대로), 5 7 11 13 23 15

    i = 4, idx = 4

    23, 뒤에 있는 숫자들 중 최솟값의 위치는 5, idx = 5

    i 와 idx 위치 원소를 교환(그대로), 5 7 11 13 15 23

#. Code

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38

#include <cstdio> #include <vector> #include <algorithm>   using namespace std;   int main(void) {     freopen("input.txt", "rt", stdin);       int n, i, j, tmp;       scanf("%d", &n);     vector<int> v(n);       for (i = 0; i < n; i++)         scanf("%d", &v[i]);          for (i = 0; i < n - 1; i++)     {         for (j = i + 1; j < n; j++)         {             if (v[i] > v[j])             {                 tmp = v[i];                 v[i] = v[j];                 v[j] = tmp;             }         }     }       for (i = 0; i < n; i++)         printf("%d ", v[i]);       puts("");       return 0; } Colored by Color Scripter

cs

#. Other code

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27

#include<stdio.h>   int main() {     int a[101], n, tmp, idx, i, j;       scanf("%d", &n);       for(i=0; i<n; i++)         scanf("%d", &a[i]);          for(i=0; i<n-1; i++){         idx=i;           for(j=i+1; j<n; j++)             if(a[j]<a[idx]) idx=j;                  tmp=a[i];         a[i]=a[idx];         a[idx]=tmp;     }       for(i=0; i<n; i++)         printf("%d ", a[i]);          return 0; }   Colored by Color Scripter

cs

나는 그냥 현재 idx의 원소보다 작으면 그냥 다 교환해줬었는데..

보니까 가장 작은 수와 교환해주는게 훨씬 가벼운 것 같다. 너무 생각이 짧나..

내가 생각을 너무 짧게 하나 싶다. 딱 봐도 계속 교환하는 것 보다 최소값을 찾아서 그거랑만 교환해주는게 훨씬 좋은데,,

idx 값에 i 뒤에 있는 원소들 중 최솟값의 위치를 저장하고,

i와 idx 위치에 있는 원소를 교환해주면 된다.

#. Result

  - Input --------------------------------------------------------

6

13 5 11 7 23 15

------------------------------------------------------------------

  - Output --------------------------------------------------------

5 7 11 13 15 23

------------------------------------------------------------------