정렬 - 선택정렬(Selection Sort)

선택정렬

- 버블정렬과 비슷한 알고리즘

- 배열 중 최댓값을 선택하여 정렬이 되어있지 않은 제일 마지막 자리(오른쪽)로 옮긴다.

 

 

lastUnsortedIndex = this is the last index of the unsorted partition

비정렬된 마지막 인덱스를 구한다(처음에는 array length -1 ) 

 

i = index used to traverse the array from left to right

i는 1부터 비정렬된 마지막 인덱스까지 1씩 늘어나며 비교한다

 

largest = index of largest element in unsorted partition

largest 는 비정렬된 값중의 최댓값을 가지고 있는 배열의 인덱스

 

 

java 예제

public class Main {
    public static void main(String[] args){

        int[] intArray = {20,13, -22,7,34,1,-20};

        for(int lastUnsortedIndex = intArray.length-1; lastUnsortedIndex >0 ; lastUnsortedIndex--){

            int largest = 0;

            for(int i = 1 ; i <= lastUnsortedIndex; i++){
                if(intArray[i]> intArray[largest]){
                    largest = i;
                }
            }

            swap(intArray, largest, lastUnsortedIndex);

        }

        for(int i = 0; i <intArray.length; i++){
            System.out.println(intArray[i]);
        }

    }

    public static void swap(int[] array, int i, int j){

        if(i == j){
            return;
        }

        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;

    }
}

 

특징

다른 메모리 공간을 필요로하지 않는 in-place알고리즘

시간복잡도 O(n2)

불안정정렬

버블정렬의 비해 교환하는 수가 적다

 

in-place algorithm

O(n2) time complexity - quadratic

unstable algorithm

doesn't require as much swapping as bubble sort

 

 

 

references 

udemy - data structures and algorithm 

https://www.programiz.com/dsa/selection-sort

Selection Sort (With Code in Python/C++/Java/C)