# 선택 μ •λ ¬(Selection Sort)


# Goal


  • Selection Sort에 λŒ€ν•΄ μ„€λͺ…ν•  수 μžˆλ‹€.
  • Selection Sort 과정에 λŒ€ν•΄ μ„€λͺ…ν•  수 μžˆλ‹€.
  • Selection Sort을 κ΅¬ν˜„ν•  수 μžˆλ‹€.
  • Selection Sort의 μ‹œκ°„λ³΅μž‘λ„μ™€ κ³΅κ°„λ³΅μž‘λ„λ₯Ό 계산할 수 μžˆλ‹€.

# Abstract


Selection SortλŠ” Bubble Sortκ³Ό μœ μ‚¬ν•œ μ•Œκ³ λ¦¬μ¦˜μœΌλ‘œ, ν•΄λ‹Ή μˆœμ„œμ— μ›μ†Œλ₯Ό 넣을 μœ„μΉ˜λŠ” 이미 μ •ν•΄μ Έ 있고, μ–΄λ–€ μ›μ†Œλ₯Ό 넣을지 μ„ νƒν•˜λŠ” μ•Œκ³ λ¦¬μ¦˜μ΄λ‹€.

Selection Sort와 Insertion Sortλ₯Ό ν—·κ°ˆλ €ν•˜λŠ” μ‚¬λžŒλ“€μ΄ μ’…μ’… μžˆλŠ”λ°, Selection SortλŠ” λ°°μ—΄μ—μ„œ ν•΄λ‹Ή 자리λ₯Ό μ„ νƒν•˜κ³  κ·Έ μžλ¦¬μ— μ˜€λŠ” 값을 μ°ΎλŠ” 것이라고 μƒκ°ν•˜λ©΄ νŽΈν•˜λ‹€.


# Process (Ascending)


  1. 주어진 λ°°μ—΄ 쀑에 μ΅œμ†Œκ°’μ„ μ°ΎλŠ”λ‹€.
  2. κ·Έ 값을 맨 μ•žμ— μœ„μΉ˜ν•œ κ°’κ³Ό κ΅μ²΄ν•œλ‹€. (pass)
  3. 맨 처음 μœ„μΉ˜λ₯Ό λΊ€ λ‚˜λ¨Έμ§€ 배열을 같은 λ°©λ²•μœΌλ‘œ κ΅μ²΄ν•œλ‹€.

# Java Code (Ascending)


void selectionSort(int[] arr) {
    int indexMin, temp;
    for (int i = 0; i < arr.length-1; i++) {        // 1.
        indexMin = i;
        for (int j = i + 1; j < arr.length; j++) {  // 2.
            if (arr[j] < arr[indexMin]) {           // 3.
                indexMin = j;
            }
        }
        // 4. swap(arr[indexMin], arr[i])
        temp = arr[indexMin];
        arr[indexMin] = arr[i];
        arr[i] = temp;
  }
  System.out.println(Arrays.toString(arr));
}
  1. μš°μ„ , μœ„μΉ˜(index)λ₯Ό 선택해쀀닀.

  2. i+1번째 μ›μ†ŒλΆ€ν„° μ„ νƒν•œ μœ„μΉ˜(index)의 κ°’κ³Ό 비ꡐλ₯Ό μ‹œμž‘ν•œλ‹€.

  3. μ˜€λ¦„μ°¨μˆœμ΄λ―€λ‘œ ν˜„μž¬ μ„ νƒν•œ μžλ¦¬μ— μžˆλŠ” 값보닀 μˆœνšŒν•˜κ³  μžˆλŠ” 값이 μž‘λ‹€λ©΄, μœ„μΉ˜(index)λ₯Ό κ°±μ‹ ν•΄μ€€λ‹€.

  4. '2'번 반볡문이 λλ‚œ λ’€μ—λŠ” indexMin에 '1'λ²ˆμ—μ„œ μ„ νƒν•œ μœ„μΉ˜(index)에 λ“€μ–΄κ°€μ•Όν•˜λŠ” κ°’μ˜ μœ„μΉ˜(index)λ₯Ό κ°–κ³  μžˆμœΌλ―€λ‘œ μ„œλ‘œ κ΅ν™˜(swap)ν•΄μ€€λ‹€.


# GIF둜 μ΄ν•΄ν•˜λŠ” Selection Sort


img (opens new window)


# μ‹œκ°„λ³΅μž‘λ„


λ°μ΄ν„°μ˜ κ°œμˆ˜κ°€ n개라고 ν–ˆμ„ λ•Œ,

  • 첫 번째 νšŒμ „μ—μ„œμ˜ λΉ„κ΅νšŸμˆ˜ : 1 ~ (n-1) => n-1

  • 두 번째 νšŒμ „μ—μ„œμ˜ λΉ„κ΅νšŸμˆ˜ : 2 ~ (n-1) => n-2

    ...

  • (n-1) + (n-2) + .... + 2 + 1 => n(n-1)/2

λΉ„κ΅ν•˜λŠ” 것이 μƒμˆ˜ μ‹œκ°„μ— μ΄λ£¨μ–΄μ§„λ‹€λŠ” κ°€μ • μ•„λž˜, n개의 주어진 배열을 μ •λ ¬ν•˜λŠ”λ° O(n^2) 만큼의 μ‹œκ°„μ΄ κ±Έλ¦°λ‹€. μ΅œμ„ , 평균, μ΅œμ•…μ˜ 경우 μ‹œκ°„λ³΅μž‘λ„λŠ” O(n^2) 으둜 λ™μΌν•˜λ‹€.


# κ³΅κ°„λ³΅μž‘λ„


주어진 λ°°μ—΄ μ•ˆμ—μ„œ κ΅ν™˜(swap)을 톡해, 정렬이 μˆ˜ν–‰λ˜λ―€λ‘œ O(n) 이닀.


# μž₯점


  • Bubble sort와 λ§ˆμ°¬κ°€μ§€λ‘œ μ•Œκ³ λ¦¬μ¦˜μ΄ λ‹¨μˆœν•˜λ‹€.

  • 정렬을 μœ„ν•œ 비ꡐ νšŸμˆ˜λŠ” λ§Žμ§€λ§Œ, Bubble Sort에 λΉ„ν•΄ μ‹€μ œλ‘œ κ΅ν™˜ν•˜λŠ” νšŸμˆ˜λŠ” 적기 λ•Œλ¬Έμ— λ§Žμ€ κ΅ν™˜μ΄ μΌμ–΄λ‚˜μ•Ό ν•˜λŠ” μžλ£Œμƒνƒœμ—μ„œ 비ꡐ적 νš¨μœ¨μ μ΄λ‹€.

  • Bubble Sort와 λ§ˆμ°¬κ°€μ§€λ‘œ μ •λ ¬ν•˜κ³ μž ν•˜λŠ” λ°°μ—΄ μ•ˆμ—μ„œ κ΅ν™˜ν•˜λŠ” λ°©μ‹μ΄λ―€λ‘œ, λ‹€λ₯Έ λ©”λͺ¨λ¦¬ 곡간을 ν•„μš”λ‘œ ν•˜μ§€ μ•ŠλŠ”λ‹€. => 제자리 μ •λ ¬(in-place sorting)


# 단점


  • μ‹œκ°„λ³΅μž‘λ„κ°€ O(n^2)으둜, λΉ„νš¨μœ¨μ μ΄λ‹€.

  • λΆˆμ•ˆμ • μ •λ ¬(Unstable Sort) 이닀.


# Conclusion


Bubble Sort와 μœ μ‚¬ν•˜μ§€λ§Œ, 쑰금 더 λΉ λ₯Έ Selection Sort에 λŒ€ν•΄ μ•Œμ•„λ΄€λ‹€. 기술 λ©΄μ ‘μ΄λ‚˜ μ‹œν—˜(n번째 νšŒμ „μ— μ •λ ¬ μƒνƒœ)μ—μ„œλ„ μ’…μ’… λ‚˜μ˜€λŠ” μ •λ ¬μ΄λ‹ˆ μ•Œμ•„λ‘λ©΄ μ’‹λ‹€.


# [참고 자료]

μ΅œμ’… μˆ˜μ • : 11/15/2021, 1:31:19 PM