선택 정렬 (selection sort)

김경민·2020년 11월 24일
0

Algorithm

목록 보기
2/2

선택 정렬 (selection sort)

  • 최솟값을 찾아 선택한 뒤, 맨 처음으로 보내는 정렬 알고리즘

출처: https://visualgo.net/en/sorting

알고리즘 생각해보기

  • 처음 값을 고정시키고 다음 값부터 끝값까지 모두 비교하는 반복횟수 -> len(data) - 1
  • 최솟값의 인덱스를 찾아 저장해 두었다가 맨 처음 값과 swap
  • 두 번째 값을 고정시키고 똑같이 비교 반복하는 횟수는 위 횟수의 -1
  • 이 반복을 len(data) - 1 만큼 반복 (고정시키는 값이 처음부터 끝값 전까지)

알고리즘 구현

파이썬 코드 구현

import random

def selection_sort(data):
    for stand in range(len(data) - 1):
        lowest = stand
        for index in range(stand + 1, len(data)):
            if data[lowest] > data[index]:
                lowest = index
        data[lowest], data[stand] = data[stand], data[lowest]
    return data
    
data_list = random.sample(range(100), 10)
selection_sort(data_list)

자바 코드 구현

import java.util.Arrays;

public class SelectionSort {

    static void swap(int[] a, int i, int j) {
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }

    static void selectionSort(int[] a) {
        for (int i = 0; i < a.length - 1; i++) {
        	int minIndex = i;
        	for (int j = i + 1; j < a.length; j++ ) {
        		if (a[minIndex] > a[j]) {
        			minIndex = j;
        		}
        	}
            swap(a, i, minIndex);
        }
    }

    public static void main(String[] args) {
        int[] a = { 17, 14, 11, 19, 13, 15, 18, 12, 16, 20 };

        selectionSort(a);
        System.out.println(Arrays.toString(a));
    }
}

수행 시간 분석

  • 반복문이 두 개 O(n2n^2)
    • 실제로 상세하게 계산하면, n(n1)2\frac { n * (n - 1)}{ 2 }
profile
베짱이개발자

0개의 댓글