728x90 알고리즘/정렬 알고리즘3 정렬 알고리즘(C++) / 삽입 정렬(Insertion Sort) 삽입 정렬(Insertion Sort) 삽입 정렬은 자료 배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여 자신의 위치를 찾아 삽입하는 알고리즘이다. k번째 반복 후의 결과 배열은 앞쪽 k+1 항목이 정렬된 상태이다. 두번째 인덱스부터 시작하여 원소를 뒤로 옮기고 지정된 자리에 자료를 삽입하여 정렬하는 알고리즘이다. 선택 정렬과 유사하지만 더 효율적인 정렬 알고리즘이다. 시간 복잡도 & 공간 복잡도 시간 복잡도 : O(n^2) 공간 복잡도 : O(n) 최선의 경우 O(n)이라는 시간 복잡도를 가지지만 최악의 기준으로는 O(n^2)의 복잡도를 가진다. 최선의 경우는 대부분의 원소가 이미 정렬되어 있는 경우를 말한다. 안정 정렬이다. 버블 정렬이나 선택 정렬과 같은 시간 복잡도를 가지.. 2021. 10. 22. 정렬알고리즘(C++) / 버블 정렬(Bubble Sort) 버블 정렬(Bubble Sort) 버블정렬은 가장 쉽고 코드가 단순한 정렬 알고리즘이다. 두 값을 비교하여 정렬하며 이동한다. 하지만 시간복잡도가 느려 실제로는 잘 사용되지 않는다. 원소의 이동이 거품이 수면으로 올라오는 듯한 모습을 보이기 때문에 버블 정렬이란 이름이 붙여졌다. 양방향으로 번갈아 수행하면 칵테일 정렬이다. 시간 복잡도 & 공간 복잡도 시간 복잡도 : O(n^2) 공간 복잡도 : O(n) 코드(C++) - 백준 2750 /2750 버블정렬 #include using namespace std; int main() { //입력 int N; cin >> N; int arr[1001]; int num; for (int i = 0; i > num; arr[i] = n.. 2021. 10. 22. 정렬알고리즘(C++) / 선택정렬(Selection Sort) 선택 정렬(Selection Sort) 선택 정렬은 현재 위치에 들어갈 값을 찾아 정렬하는 배열이다. 해당 순서 뒤에 주어진 리스트 중에 최솟값을 찾아 해당 해당 순서에 위치한 값과 교체한다. 애니메이션으로 선택 정렬 알고리즘을 쉽게 이해할 수 있다. 시간 복잡도 & 공간 복잡도 시간 복잡도 : O(n^2) 공간 복잡도 : O(n) 장점 버블 정렬(bubble sort)과 마찬가지로 알고리즘이 단순하다. 정렬을 위한 비교 횟수는 많지만, 버블 정렬에 비해 실제로 교환하는 횟수가 적으므로 버블 정렬보다 항상 우수하다. 배열 안에서 교환하는 방식으로 다른 메모리 공간을 필요로 하지 않는다. 제자리 정렬이다. 단점 탐색 횟수가 많고 시간 복잡도가 크다. 불안정 정렬이다. (불안정 정렬 : 정렬 후 원래의 순서.. 2021. 10. 22. 이전 1 다음
