목록C/C++ (3)

Lavine's Dev Site

[알고리즘 개념] 정렬 알고리즘 - 버블 정렬 (Bubble Sort)

버블 정렬 (Bubble Sort) 정렬 순서 (오름차순 정렬 기준) 인접한 원소 두 개((arr[0], arr[1]), (arr[1], arr[2]) ~ (arr[n-2], arr[n-1]))를 쌍으로 지어 앞에 위치한 원소가 뒤의 원소보다 크다면 swap한다. 1회전을 끝내게 되면 배열 내의 가장 큰 원소가 가장 마지막에 배치된다. (뒤에서부터 정렬이 완료된다.) 따라서 1~2과정을 정렬되지 않은 원소가 1개가 될때까지 반복한다. 예시 장점 구현이 쉽고 이해하기 쉽다. In-place Sorting Algorithm 주어진 배열 내에서 이루어지기 때문에 공간복잡도 O(n) 안정 정렬 (Stable Sorting) 중복 값이 입력 순서와 동일하게 정렬 됨 단점 O(n2)의 시간복잡도 정렬을 위해 swa..
Algorithm/알고리즘 개념 2022. 9. 30. 00:19
[알고리즘 개념] 정렬 알고리즘 - 선택 정렬 (Selection Sort)

선택 정렬 (Selection Sort) 정렬 순서 (오름차순 정렬 기준) 주어진 리스트에서 최소 값을 찾는다. 최소 값을 유효 범위 내에서 맨 앞의 값과 swap한다. swap된 위치를 제외 한 나머지 공간이 1개가 될때까지 1 ~ 2를 반복한다. 예시 장점 구현이 쉽고 이해하기 쉽다. In-place Sorting Algorithm 주어진 배열 내에서 이루어지기 때문에 공간복잡도 O(n) 단점 O(n2)의 시간복잡도 불안정 정렬 (Unstable sorting) 중복 값 순서 보장 못함 시간 복잡도 외부 루프: (n-1)번 반복 최솟값 탐색: n-1, n-2, n-3, ... ,2, 1 T(n) = 1 + 2 + ... + (n-2) + (n-1) = n(n-1)/2 ∈ O(n2) Code (C/C+..
Algorithm/알고리즘 개념 2022. 9. 26. 01:09
[알고리즘 개념] 정렬 알고리즘 - 삽입 정렬 (Insertion Sort)

정렬 알고리즘(Sorting Algorithm) 정렬 알고리즘이란 n개로 이루어진 배열이 주어져있을 때, 이를 번호순 혹은 사전 순 같이 일정 순서대로 열거를 해주는 알고리즘을 의미한다. 데이터를 정렬하는 이유는 탐색 및 데이터 편집 시 시간을 절약하기 위해서이다. 예를 들어 정렬이 안되어 있는 데이터를 탐색하려면 데이터를 순차적으로 조사해야 하지만 정렬이 되어있을 경우 이진탐색과 같은 알고리즘을 사용하여 탐색시간을 효율적으로 줄일 수 있기 때문이다. 삽입 정렬 (Insertion Sort) 정렬 순서 비교 대상이 되는 원소를 잡고 앞에 있는 원소들과 비교를 한다. 비교대상이 되는 원소가 이전 위치의 원소보다 작다면 swap 마지막 인덱스 원소까지 1~2를 반복한다. 예시 장점 구현이 쉽고 이해하기 쉽다..
Algorithm/알고리즘 개념 2022. 9. 25. 14:20
이전 Prev 1 Next 다음