[알고리즘]선택 정렬(Selection sort)

1. 정렬이 안 된 배열에서 가장 작은 원소를 찾는다.

2. 해당 원소를 정렬된 배열에 붙여준다.

3. 정렬이 반복될 때까지 반복한다.

 

플로우차트

 

시간 분석 >> O(N^2)

C

#include <stdio.h>

void swap(int *xp, int *yp){
    int temp = *xp;
    *xp = *yp;
    *yp = temp;
}

void selectionSort(int arr[], int n){
    int i, j, min_idx;
    
    // 정렬되지 않은 배열 부분을 순회한다.
    for(i = 0; i < n-1; i++){
        // 최소값을 찾는다.
        min_idx = i;
        for(j = i+1; j < n; j++)
            if(arr[j] < arr[min_idx])
            min_idx = j;
            
        // 최소값과 i번째 원소를 바꾼다.
        swap(&arr[min_idx], &arr[i]);
    }
}

/* 배열 출력 함수 */
void printArray(int arr[], int size){
    int i;
    for(i = 0; i < size; i++)
        printf("%d ", arr[i]);
    printf("\n");
}

int main()
{
    int arr[] = {2, 4, 7, 5, 3, 1};
    int n = sizeof(arr)/sizeof(arr[0]);
    selectionSort(arr, n);
    printf("Sorted array : \n");
    printArray(arr, n);
    return 0;
}

java

public class Main
{
    // 배열 정렬
    void sort(int arr[]){
        int n = arr.length;
        
        // 정렬되지 않은 배열 부분을 순회한다.
        // n-1인 이유 : i가 n-1이라면 배열의 마지막 원소를 말하는데, 이는 자기 자신과 비교하는 것이기 때문에 필요 없다.
        for(int i = 0; i < n-1; i++){
            // 최소값을 찾는다.
            int min_idx = i;
            for(int j = i+1; j < n; j++)
                if(arr[j] < arr[min_idx])
                    min_idx = j;
                    
            // 정렬되지 않은 부분의 첫 원소와 최소값을 바꿔준다.
            int temp = arr[min_idx];
            arr[min_idx] = arr[i];
            arr[i] = temp;
        }
    }
    
    // 배열 출력
    void printArray(int arr[]){
        int n = arr.length;
        for(int i = 0; i < n; i++)
            System.out.print(arr[i] + " ");
        System.out.println();
    }
    
	public static void main(String[] args) {
		Main ob = new Main();
		int arr[] = {2, 4, 7, 5, 3, 1};
		ob.sort(arr);
		System.out.println("Sorted Array");
		ob.printArray(arr);
	}
}

python

import sys
A = [2, 4, 7, 5, 3, 1];

# 배열의 모든 원소를 taraverse한다.
for i in range(len(A)):
    
    # 가장 작은 원소를 남은 배열에서 찾는다.
    # 정렬 안 된 배열
    min_idx = i
    for j in range(i+1, len(A)):
        if A[min_idx] > A[j]:
            min_idx = j
            
    # i 번째 원소와 min_idx 의 원소를 바꿔준다.
    A[i], A[min_idx] = A[min_idx], A[i]
    
# 출력
print("Sorted array")
for i in range(len(A)):
    print("%d " %A[i]),