본문 바로가기

알고리즘 공부

6. 선택 정렬

728x90
반응형
SMALL

출처: https://gmlwjd9405.github.io/images/algorithm-selection-sort/selection-sort.png

선택 정렬 (Selection sort)

선택  정렬을 실행했을 때 나오는 그림.

버블 정렬이 비교하고 바로 바꿔 넣는 걸 반복한다면 이 정렬은 1번째부터 끝까지 훑어서 가장 작은 게 1번째,

2번째부터 끝까지 훑어서 가장 작은 게 2번째……해서 (n-1)번 반복한다.

이 정렬은 인간이 흔히 사용하는 정렬 방식을 가장 많이 닮았다.

어떻게 정렬이 되어 있든 일관성 있게 에 비례하는 시간이 걸린다는 게 특징이다.

또한, 버블 정렬보다 두 배 정도 빠르다.

정렬 알고리즘 시간 복잡도 비교

  • 단순(구현이 간단)하지만 비효율적인 방법

    삽입 정렬, 선택 정렬, 버블 정렬

  • 복잡하지만 효율적인 방법

    퀵 정렬, 힙 정렬, 합병 정렬, 기수 정렬

비슷한 것으로는 이중 선택 정렬(Double Selection Sort)도 있다.

이중 선택 정렬은 끝까지 훑어서 최솟값과 최댓값을 동시에 찾아낸 뒤 최솟값은 1번째와 바꾸고

최댓값은 끝과 바꾼 다음 훑는 범위를 양쪽으로 한 칸씩 줄여서 반복하는 방식이다.

이 방법을 쓰면 반복 횟수가 반으로 줄어든다.

https://youtu.be/Ns4TPTC8whw
이해를 돕기위해. 배속을 하고 봐라!

예제 C코드

# include <stdio.h>
# define SWAP(x, y, temp) ( (temp)=(x), (x)=(y), (y)=(temp) )
# define MAX_SIZE 5

// 선택 정렬
void selection_sort(int list[], int n){
  int i, j, least, temp;

  // 마지막 숫자는 자동으로 정렬되기 때문에 (숫자 개수-1) 만큼 반복한다.
  for(i=0; i<n-1; i++){
    least = i;

    // 최솟값을 탐색한다.
    for(j=i+1; j<n; j++){
      if(list[j]<list[least])
        least = j;
    }

    // 최솟값이 자기 자신이면 자료 이동을 하지 않는다.
    if(i != least){
        SWAP(list[i], list[least], temp);
    }
  }
}

void main(){
  int i;
  int n = MAX_SIZE;
  int list[n] = {9, 6, 7, 3, 5};

  // 선택 정렬 수행
  selection_sort(list, n);

  // 정렬 결과 출력
  for(i=0; i<n; i++){
    printf("%d\n", list[i]);
  }
}

1싸이클
첫 번째 원소 9를 두 번째 원소부터 마지막 원소까지 비교하여 가장 작은 값을 첫 번째 위치에 옮겨 놓는다.

이 과정에서 원소를 4번 비교한다.


2싸이클
두 번째 원소 6을 세 번째 원소로부터 마지막 원소까지와 비교하여 가장 작은 값을 두 번째 위치에 옮겨 놓는다. 

이 과정에서 원소를 3번 비교한다.


3싸이클
세 번째 원소 7을 네 번째 원소로부터 마지막 원소까지와 비교하여 가장 작은 값을 세 번째 위치에 옮겨 놓는다.

이 과정에서 원소를 2번 비교한다.


4싸이클
네 번째 원소 9와 마지막에 있는 원소 7을 비교하여 서로 교환한다.


참조 사이트

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

 

[알고리즘] 선택 정렬(selection sort)이란 - Heee's Development Blog

Step by step goes a long way.

gmlwjd9405.github.io

https://namu.wiki/w/%EC%A0%95%EB%A0%AC%20%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98#fn-13

 

정렬 알고리즘 - 나무위키

대개 계산 시간이 정렬할 자료의 수의 제곱에 비례해서 늘어난다. 즉, 1만 개를 1초에 정렬하면 10만 개를 정렬하는 데에는 100초 정도가 필요하다. 셰이커 정렬(shaker sort)라고도 한다. 홀수 번째 돌 때는 앞부터, 짝수 번째는 뒤부터 훑는 정렬. 당연하겠지만 이 쪽은 마지막과 처음이 번갈아가며 정렬된다. 제일 처음에 하나, 제일 뒤에 하나, 다시 제일 앞에 하나, 또 제일 뒤에 하나를 정렬하면서 마치 정렬하는 과정이 앞뒤로 마구 흔드는게 칵

namu.wiki

https://www.codecogs.com/latex/eqneditor.php

 

Online LaTeX Equation Editor - create, integrate and download

Type your equation in this box

www.codecogs.com

 

반응형
LIST

'알고리즘 공부' 카테고리의 다른 글

8. 퀵정렬  (0) 2019.09.27
7. 삽입 정렬  (0) 2019.09.25
5. 칵테일 정렬  (0) 2019.09.22
4. 버블 정렬  (0) 2019.09.22
3. 계산 복잡도 (시간복잡도,공간복잡도) 정리  (1) 2019.09.21