선택 정렬(Selection Sort) - fora22/CodingTest GitHub Wiki

선택 정렬은 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸는 것을 반복하는 알고리즘이다.

image

C++ 구현 코드는 다음과 같다.

#include <iostream>
#include <vector>
#include <string>

using namespace std;

int SequentialSearch(vector<int> inputArray, const int arraySize, const int findData);

int main(void) {
	vector<int> v{ 1, 3, 4, 7, 8, 13, 17 };

	int result;
	result = SequentialSearch(v, v.size(), 8);
	cout << result << endl;
	

	return 0;
}

int SequentialSearch(vector<int> inputArray, const int arraySize, const int findData) {
	// argument (vector, vector Å©±â, ã´Â µ¥ÀÌÅÍ)
	int middleIndex = -1;
	
    for (int i = 0; i < arraySize; i++) {
        if (findData == inputArray[i]) {
            middleIndex = i;
            break;
        }
    }

    return middleIndex;
}

선택 정렬의 시간복잡도

  • 선택 정렬은 N번 만큼 가장 작은 수를 찾아서 맨 앞으로 보내야 한다.
  • 전체 연산 횟수는 N + (N - 1) + (N - 2) + ... + 2
  • 이는 (N^2 + N - 2)로 표기할 수 있고 빅오 표기법에 따라 O(N^2)이다.

Reference

⚠️ **GitHub.com Fallback** ⚠️