Insertion Sort 2번째 원소부터 시작하여 i-1(왼쪽)의 원소들과 비교하여 삽입할 위치를 지정한 후, 원소를 뒤로 옮기고 지정된 자리에 자료를 삽입하여 정렬하는 알고리즘이다. 최선의 경우 O(N)이라는 엄청나게 빠른 효율성을 가지고 있어, 다른 정렬 알고리즘의 일부로 사용될 만큼 좋은 정렬 알고리즘이다. 예제 1 public int[] solution(int[] arr) { if (arr == null) return null; int temp; for (int i = 1; i = 0; k--) { if (temp >= arr[k]) { break; } arr[k + 1] = arr[k..

Bubble Sort N개의 원소를 가진 배열을 정리할 때, 서로 인접한 두 개의 데이터를 비교하고, 조건에 맞춰 자리를 교환하며 정리하는 알고리즘입니다. 시간 복잡도가 O(n^{2})로 상당히 느리지만, 코드가 단순하기 때문에 자주 사용되며. 원소의 이동이 거품이 수면으로 올라오는 듯한 모습을 보이기 때문에 지어진 이름입니다. 예시 1 void bubbleSort(int[] arr) { int temp = 0; for(int i = 0; i arr[j]) { // 3. // swap(arr[j-1], arr[j]) temp = arr[j-1]; ar..

Big O notation (대문자 O 표기법) Big - O 케이스 O(1): Constant - 데이터의 수(N)와 관계없이 항상 같은 시간에 계산을 끝내는 알고리즘. ex) 연결 리스트의 맨 앞에 값 추가, Array의 Push(), Pop() 등.. O(log N): Logarthmic - N의 크기가 제곱이 되면 시간이 배가 된다. 문제를 해결하는데 필요한 단계의 수가 연산마다 점차 줄어드는 알고리즘. ex) 이진 탐색, 재귀가 순기능으로 이뤄지는 경우 O(N): Linear - N의 크기가 증가하는만큼 비례하여 처리시간이 증가하는 알고리즘. ex) 선형 탐색(연결 리스트에서의 탐색 등..), Stack, Queue 등에서의 access. O(N log N): Linear-Logarithmic ..