[이것이 코딩 테스트다 with Python]_21_선택정렬

220208 작성

<본 블로그는 『이것이 취업을 위한 코딩 테스트다』 의 youtube를 참고해서 공부하며 작성하였습니다>

https://www.youtube.com/watch?v=jpyslMwprao&list=PLVsNizTWUw7H9_of5YCB0FmsSc-K44y81&index=21 

 

 

 

 

 

 

1. 정렬 

: 데이터를 특정한 기준에 따라 순서대로 나열하는 것

 

 

 

 

 

2. 선택 정렬

: 처리되지 않은 데이터 중에서 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸는 것

 

1) 가장 작은 0 선택해 가장 앞의 숫자와 바꾸기 

2) 그다음 작은 1 선택해 가장 앞에서 두번째 숫자와 바꾸기

....

이런 과정 반복

 

• python

array = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8]

for i in range(len(array)) :
    min_index = i
    for j in range(i+1, len(array)) :
        if array[min_index] > array[j] :
            min_index = j
    
    array[i], array[min_index] = array[min_index], array[i]

print(array)

• c++

#include <bits/stdc++.h>

using namespace std;

int n = 10;
int arr[10] = {7, 5, 9, 0, 3, 1, 6, 2, 4, 8};

int main(void) {
    for (int i = 0; i < n; i++) {
        int min_index = i; // 가장 작은 원소의 인덱스 
        for (int j = i + 1; j < n; j++) {
            if (arr[min_index] > arr[j]) {
                min_index = j;
            }
        }
        swap(arr[i], arr[min_index]); // 스와프
    }
    for(int i = 0; i < n; i++) {
        cout << arr[i] << ' ';
    }
}

• java

import java.util.*;

public class Main {

    public static void main(String[] args) {

        int n = 10;
        int[] arr = {7, 5, 9, 0, 3, 1, 6, 2, 4, 8};

        for (int i = 0; i < n; i++) {
            int min_index = i; // 가장 작은 원소의 인덱스 
            for (int j = i + 1; j < n; j++) {
                if (arr[min_index] > arr[j]) {
                    min_index = j;
                }
            }
            // 스와프
            int temp = arr[i];
            arr[i] = arr[min_index];
            arr[min_index] = temp;
        }

        for(int i = 0; i < n; i++) {
            System.out.print(arr[i] + " ");
        }
    }

}

 

 

 

 

 

3. 선택 정렬 시간 복잡도

: N 번 만큼 가장 작은 수를 찾아서 맨 앞으로 보내야함

: N + (N-1) + (N-2) + (N-3) ... + 2

=> (N^2 + N - 2) / 2

=> O(N^2)