[자료구조] 선택정렬

선택정렬

n ≥ 1개의 서로 다른 정수의 집합을 정렬

정렬되지 않은 정수들 중에서 가장 작은 값을 찾아서 정렬된 리스트 다음 자리에 배치

 void SelectionSort(int *a, const int n) 
 { //n개의 정수 a[0]부터 a[n-1]까지 오름차순으로 정렬
    for (int i = 0; i < n; i++) 
    { 
        int j = i; 
        //a[i]와 a[n-1] 사이에 가장 작은 정수 탐색 
        for (int k = i + 1; k < n; k++) 
            if (a[k] < a[j]) j = k; 
        swap(a[i], a[j]); //swap함수는 두 수의 위치를 교환
    } 
}

 

시간복잡도 - O(n)

//n은 배열 a의 크기