선택 정렬 해당 순서에 원소를 넣을 위치는 이미 정해져 있고, 어떤 원소를 넣을지 선택하는 알고리즘 최소값을 찾아 정렬하는 방식 평균과 최악 모두 수행 시간 복잡도는 O(n2) Process (Ascending) 주어진 배열 중에 최소값을 찾음 그 값을 맨 앞에 위치한 값과 교체 (pass) 맨 처음 위치를 뺀 나머지 배열을 같은 방법으로 교체 void selectionSort(int[] arr) { int indexMin, temp; for (int i = 0; i < arr.length-1; i++) { // 1. indexMin = i; for (int j = i + 1; j < arr.length; j++) { // 2. if (arr[j] < arr[indexMin]) { // 3. indexM..

버블 정렬 서로 인접한 두 원소의 대소를 비교하고, 조건에 맞지 않다면 자리를 교환하며 정렬하는 알고리즘 인접한 두 개의 레코드 키 값을 비교하여 서로 교환하며 정렬하는 방식 평균과 최악 모두 수행 시간 복잡도는 O(n2) Process (Ascending) 1회전에 첫 번째 원소와 두 번째 원소를, 두 번째 원소와 세 번째 원소를, 세 번째 원소와 네 번째 원소를 이런 식으로 (마지막-1)번째 원소와 마지막 원소를 비교하여 조건에 맞지 않는다면 서로 교환 1회전을 수행하고 나면 가장 큰 원소가 맨 뒤로 이동하므로 2회전에서는 맨 끝에 있는 원소는 정렬에서 제외되고, 2회전을 수행하고 나면 끝에서 두 번째 원소까지는 정렬에서 제외됨 이렇게 정렬을 1회전 수행할 때마다 정렬에서 제외되는 데이터가 하나씩 늘..

퀵 정렬 문제를 작은 2개의 문제로 분리하고 각각을 해결한 다음, 결과를 모아서 원래의 문제를 해결하는 전략 스택 필요 분할과 정복을 통해 자료를 정렬 평균 수행 시간 복잡도는 O(nlog2n), 최악의 수행 시간 복잡도는 O(n2) Process (Ascending) 배열 가운데서 하나의 원소를 고름 이렇게 고른 원소를 피벗(pivot) 이라고 함 피벗 앞에는 피벗보다 값이 작은 모든 원소들이 오고, 피벗 뒤에는 피벗보다 값이 큰 모든 원소들이 오도록 피벗을 기준으로 배열을 둘로 나눔 이렇게 배열을 둘로 나누는 것을 분할(Divide) 이라고 함. 분할을 마친 뒤에 피벗은 더 이상 움직이지 않음 분할된 두 개의 작은 배열에 대해 재귀(Recursion)적으로 이 과정을 반복 재귀 호출이 한번 진행될 때..

완전 이진 트리란? 삽입할 때 왼쪽부터 차례대로 추가하는 이진 트리 힙 정렬 완전이진 트리를 이용한 정렬 방식 평균과 최악 모두 시간 복잡도는 O(nlog2n) 과정 최대 힙을 구성 현재 힙 루트는 가장 큰 값이 존재함. 루트의 값을 마지막 요소와 바꾼 후, 힙의 사이즈 하나 줄임 힙의 사이즈가 1보다 크면 위 과정 반복 루트를 마지막 노드로 대체 (11 → 4), 다시 최대 힙 구성 이와 같은 방식으로 최대 값을 하나씩 뽑아내면서 정렬하는 것이 힙 소트 public void heapSort(int[] array) { int n = array.length; // max heap 초기화 for (int i = n/2-1; i>=0; i--){ heapify(array, n, i); // 1 } // ext..

삽입 정렬 2번째 원소부터 시작하여 그 앞(왼쪽)의 원소들과 비교하여 삽입할 위치를 지정한 후, 원소를 뒤로 옮기고 지정된 자리에 자료를 삽입 하여 정렬하는 알고리즘 순서에 맞게 삽입 시키는 정렬 평균과 최악 모두 수행 시간 복잡도는 O(n2) Process (Ascending) 정렬은 2번째 위치(index)의 값을 temp에 저장 temp와 이전에 있는 원소들과 비교하며 삽입 '1'번으로 돌아가 다음 위치(index)의 값을 temp에 저장하고, 반복 void insertionSort(int[] arr) { for(int index = 1 ; index < arr.length ; index++){ // 1. int temp = arr[index]; int prev = index - 1; while( ..

알고리즘의 복잡도를 판단하는 척도는 시간 복잡도와 공간 복잡도가 있음 그 중 시간 복잡도는 알고리즘 내 연산의 횟수와 밀접한 관계가 있음 시간 복잡도 표기법 Big-O(빅 오) 표기법 알고리즘 최악의 실행 시간을 표기 가장 많이 사용하는 표기법 최소한 보장되는 성능을 표기 Big-Ω(빅 오메가) 표기법 알고리즘의 최상의 실행 시간을 표기 Big-θ(빅 세타) 표기법 알고리즘 평균 실행 시간을 표기 실행 속도 O(1) -> O(log N) -> O(N) -> O(N log N) -> O(N^2) -> O(2^N) 빅오 표기법의 특징 상수항(영향력 없는 항) 무시 : O(N + 1) -> O(N)으로 표기 계수 무시 : O(2N) -> O(N)으로 표기 최고차항만 표기 : O(3N^3 + 2N^2 + N +..