선택정렬

자료구조: 일차원 배열
시간복잡도: 모든 경우에 O(n^2)

사용 목적: 숫자의 내림차순 or 오름차순 정렬

 

#include <stdio.h>
#include <stdlib.h>
int main(){
    int arr[] = {1,2,3,4,5,6,7,8,9,10};
    int arr_size = sizeof(arr) / sizeof(int);
    
    //mixing
    for(int i = 0; i < arr_size; i++){
        int temp = arr[i];
        int random_num = rand() % arr_size;
        arr[i] = arr[random_num];
        arr[random_num] = temp;
    }



    //sorting
    for(int j=arr_size; j > 0; j--){
        int max_num= arr[0];
        int max_index = 0;
    
        for (int i = 0; i < arr_size; i++)
        {
            if(max_num < arr[i]){
                max_num = arr[i];
                max_index = i;
            }
        }
        int temp = arr[--arr_size];
        arr[arr_size] = arr[max_index];
        arr[max_index] = temp;
    }


    //print result
    arr_size = sizeof(arr) / sizeof(int);
    for (int i = 0; i < arr_size; i++)
        printf("%d ", arr[i]);
    
    return 0;
}

개념 요약: (오름차순 기준) 배열의 처음부터 끝까지를 순환하여 가장 큰 값을 찾고, 맨뒤로 보내기(교환)