선택 정렬(Selection Sort)이란? 값이 가장 작은 숫자를 찾아 가장 왼쪽에 있는 데이터부터 순서대로 데이터를 교환하여 정렬하는 처리를 반복한다. 선택 정렬 살펴보기 우선 정렬하고자 하는 데이터 안에서 값을 하나 골라 임시 최솟값으로 정한다. 데이터 전부를 임시 최솟값과 비교한다. 임시 최솟값보다 값이 작은 데이터가 있다면, 값이 가장 작은 데이터의 위치와 임시 최솟값의 위치를 바꾼다. 계산량 확인해보기 데이터의 총 개수를 n이라고 하면 선택 정렬의 비교 횟수는 처음에 n-1 번, 그 다음은 n-2, n-3 번 ... 이다. 반복 횟수는 (n-1) + (n-2) + (n-3) + ... + 1 이므로 (n²-n)/2이다. 즉 선택 정렬의 오더는 O(n²)이 된다. 오더가 버블 정렬과 같지만, 버..
시간 복잡성이란? 계산의 복잡성, 계산이 복잡해지는 만큼 처리하는 스텝의 개수가 늘어나므로 실행 시간이 오래 걸린다는 뜻이다. 스텝 : CPU가 실행하는 명령 O 표기법 알고리즘의 계산량이 얼마나 될지 대략적으로 표현한 지표. 구체적인 실행 시간이나 명령의 개수는 알려주지 않는다. 같은 프로그램을 실행해도 컴퓨터의 처리 성능에 따라 실행 시간이 달라지기 때문에, 입력된 데이터 n의 크기에 따라 시간 계산량이 어느 정도의 비율로 늘어나는지를 O(n 식)의 형태로 표현하는 것이다. O(n) : 입력한 데이터의 크기(개수나 자릿수 등)을 n이라고 했을 때 알고리즘을 최대 n번 실행하면 처리가 완료된다는 뜻이다.(반드시 n번만에 완료된다는 것이 아니라 알고리즘의 최대 실행 횟수가 n번이라는 뜻이다.) 1. O ..
퀵 정렬(Quick Sort)이란? 데이터의 범위를 반으로 나눈 다음, 그 범위를 다시 반으로 나누어 정렬하는 처리를 반복한다. 퀵 정렬 살펴보기 우선 피봇(기준 값)을 정한다. 피봇으로 정할 데이터는 어떤 데이터든 상관없다. 정렬한 데이터의 크기가 피봇보다 큰 그룹과 작은 그룹으로 분할한다. 나눈 그룹 안에서도 똑같이 피붓을 정한 후 위와 같은 방식으로 분할한다. 이처럼 분할을 반복해 정렬하는 알고리즘을 분할 정복 알고리즘이라고 한다 계산량 확인해보기 퀵 정렬은 피봇을 기준으로 한 데이터의 크기에 따라 전체 데이터를 균형 있게 절반씩 분할해 나가며, 그 결과로 log₂n단 만들어진다. 오더는 O(nlogn)이다. 하지만 데이터를 나열한 순서가 좋지 않으면 효율이 나빠지고, 최악의 경우에는 오더가 O(n..
