힙정렬이란? 완전 이진 트리를 기본으로 하는 힙 자료구조를 기반으로 한 정렬방식 최댓값, 최솟값을 추출할 수 있는 자료구조 불안정 정렬 내림차순 정렬 => 최대 힙 / 오름차순 정렬 => 최소 힙 시간복잡도가 좋은편 가장 큰 값 몇개만 필요할 때 가장 효율적으로 사용 가능 완전 이진 트리란? [삽입할 때 왼쪽부터 차례대로 추가하는 이진 트리] 힙 정렬 과정 최대 힙을 구성(내림차순 정렬 기준) 힙에서 한개씩 요소를 꺼내 배열 뒤에 저장 최대값부터 삭제하며 감소되는 순서로 정렬 시간 복잡도 최악 평균 최선 O(nlog₂n) O(nlog₂n) O(nlog₂n) [참고 자료] 링크
Quick Sort란? 분할 정복 방법을 통해 주어진 배열을 정렬 불안정 정렬 배열을 비균등하게 분할 / 정렬된 배열일수록 수행시간이 오래 걸림 매우 빠른 속도 분할 정복 방법이란? [문제를 작은 2개의 문제로 나눠 각각 해결한 후 결과를 모아서 원래의 문제를 해결하는 전략 Quick Sort 과정 배열에서 하나의 원소를 고른다. 이 원소를 피벗(pivot)이라 한다. 피벗의 기준을 2개로 나눈다.( 피벗보다 작은 건 앞으로, 큰 건 뒤로) => 이 과정을 분할이라 하며 분할 후 피벗은 고정한다. 분할된 두 개의 작은 배열에 대해 재귀적으로 이 과정을 반복한다. 정복 -> 분할 -> 결합 순으로 이루어진다. 시간 복잡도 최선의 경우 => n -> n/2 -> n/4 ->... -> 1 = O(nlog₂n..
Insertion Sort란? 2번째 원소부터 시작하여 앞의 원소들과 크기 비교 후 삽입할 위치를 선정하고 원소를 뒤로 옮기면서 정렬하는 알고리즘 안전정렬이다 선택,버블 정렬보다 상대적으로 빠름 배열이 길어질수록 비효율 Insertion Sort 과정 2번째에 위치한 원소를 temp로 저장 temp와 이전 원소를 비교하여 삽입 1-2 반복 Insertion Sort Code public void insertionSort(int[]arr){ for(int i=1; i=0) && (arr[pre]>temp)){ //이전위치의 값이 더 클 경우 arr[pre+1]=arr[pre]; //값을 교환 pre--; } arr[pre+1]=temp; } } 시간 복잡도 최악의 경우(역으로 정렬되어 있을 경우) => O..
Selection Sort란? BubbleSort와 유사한 알고리즘으로 원소를 넣을 위치는 이미 정해져있고, 어떤 원소를 넣을지 선택하는 알고리즘 원소 중 가장 작은 값을 선택하여 앞으로 이동 정렬하고자 하는 배열 안에서 교환하는 방식으로 다른 메모리 공간을 필요로 하지 않는다. => 제자리 정렬 BubbleSort에 비해 교환 횟수가 적기 때문에 많은 교환이 일어나는 자료상태에서는 비교적 효율적이다. 불안정 정렬이다. Selection Sort 과정 배열에서 최소값을 찾는다. 찾은 값을 맨 앞의 원소와 비교한 후 교체 맨 앞의 원소를 제외하고 1-2 반복 Selection Sort Code void selectionSort(int[] arr){ int min,temp; for(int i=0; i
🫧Bubble Sort란? 서로 인접한 두 원소의 크기를 비교하고, 조건에 맞도록 자리를 교환하며 정렬하는 알고리즘 코드가 직관적이고 간단하지만 매우 비효율적인 정렬 🫧Bubble Sort 과정 1회 차 : 첫 번째 원소와 두 번째 원소를, 두 번째 원소와 세 번째 원소를... (N-1) 번째 원소와 N번째 원소를 비교하여 큰 수를 뒤로 이동 1회 차 후 가장 큰 수는 맨 뒤로 이동되므로 2회 차에서는 마지막 원소 제외(조건에 맞기 때문에) 다시 반복 회차를 반복 할 수록 제외되는 원소가 늘어나고 모든 원소가 조건에 맞게 정렬될 때까지 반복한다. 🫧Bubble Sort Code void bubbleSort(int[] arr){ int temp=0; for(int i=0;i n(n+1)/2 2개의 원소를 ..
