퀵 정렬은 합병 정렬과 비슷한 방식으로 작동한다.재귀를 통해 해결하는 방식이다.👉🏻 기본적으로 데이터를 분할하여 배열에 0개 또는 1개의 항목이 남을 때까지 분할하여 개별적으로 정렬되는 방식 배열에서 하나의 원소를 피벗(pivot) 으로 선택한다.피벗보다 작은 값들은 왼쪽으로, 큰 값들은 오른쪽으로 분할한다.이때 피벗은 이미 정확한 위치에 놓이게 된다.이후 왼쪽 부분 배열과 오른쪽 부분 배열에 대해 같은 과정을 재귀적으로 반복한다.[5, 2, 1, 8, 4, 7, 6, 3]5를 피벗으로 고른다. 피벗 선택첫 번째 원소 5를 피벗으로 고른다. 5보다 작은 값 → [2, 1, 4, 3]5보다 큰 값 → [8, 7, 6]→ 이제 5는 최종 위치에 고정된다. 왼쪽 배열 [3, 2, 1, 4] 정렬피벗 3..

대부분의 합병 정렬을 할때 재귀를 사용한다. 재귀란? (⬇️ 블로그 참고)https://recordoftheday.tistory.com/entry/%EC%95%8C%EC%9E%90 합병 정렬의 목표배열을 계속 반으로 나누기! 하나의 배열을 반으로 어떻게 나눌까?1. slice 사용arr.slice를 작성하고 0에서 중간 배열로 👉🏻 중간 배열에서 0으로 간다. arr.slice(0, mid) → 앞 절반arr.slice(mid) → 뒤 절반 그러면 두 개의 절반이 생긴다. 각각의 절반으로 무엇을 할까?합병 정렬을 다시 호출하고 각각의 절반을 다시 절반으로 쪼갠다. 👈🏻 재귀를 계속하게 되는것 재귀의 기본 케이스가 뭐였는가? 배열 길이가 1보다 작거나 같을때였다. 1이나 0을 의미한다. 그렇게 모..

목표처음부터 코드를 외워서 작성하는 것보다, 작동 원리를 이해하고 설명할 수 있게!지금까지의 한계기초 정렬 알고리즘: 버블 정렬, 선택 정렬, 삽입 정렬모두 O(n²) 이므로, 작은 데이터(예: 20개)에는 괜찮지만 큰 데이터(예: 10만 개 이상)에서는 비효율적임이게 바로 한계실제 성능 비교버블 정렬로 10만 개 난수 배열을 정렬 → 약 20초 소요같은 배열을 합병 정렬로 정렬 → 1초도 안 걸림데이터가 많아질수록(100만, 1000만 개) 시간 차이는 더 극적으로 벌어짐시간 복잡도 차이기초 정렬: O(n²) (이차 시간 복잡도 → 데이터가 커질수록 시간 폭발적으로 증가)중급 정렬: O(n log n) (훨씬 효율적)합병 정렬의 역사1948년, 수학자이자 컴퓨터 과학자인 존 폰 노이만(John von ..

Algorithm Best CaseAverage CaseWorst CaseSpaceBubble SortO(n)O(n²)O(n²)O(1)Insertion SortO(n)O(n²)O(n²)O(1)Selection SortO(n²)O(n²)O(n²)O(1)*space Complexity (공간 복잡도) → 추가로 얼마나 메모리를 쓰는가공통점전부 기본 정렬 알고리즘( 2차 정렬 알고리즘 )(Big-O 평균: O(n²))in-place 정렬 → 추가 공간 거의 안 씀 (O(1))소규모 데이터에서는 괜찮지만, 대규모 데이터에서는 비효율적버블 정렬 (Bubble Sort)최선의 경우 (거의 정렬된 데이터): O(n)인접 원소를 교환하면서 정렬.데이터가 거의 정렬된 경우, 교환이 거의 없어서 매우 빠르게 끝남삽입 정렬..

작동 방식배열을 왼쪽부터 차근차근 정렬해 나가는 방식(항상 왼쪽 부분은 이미 정렬되어 있다.라고 생각하기!) 버블 정렬처럼 옆으로 하나하나 바꾸거나, 선택 정렬처럼 제일 작은/큰 걸 한 번에 찾는게 아니고새로운 값을 하나 꺼내서 정렬된 부분 속 "자기 자리"에 꽂아 넣는 방식 배열을 두 덩어리(정렬된 부분+아직 정렬 안 된 부분)로 나눠 놓고, 정렬 안된 부분에서 하나씩 꺼내서 정렬된 부분에 끼워 넣는다! [5, 3, 4, 1, 2] ↑ 첫 번째 값은 그냥 정렬된 부분이라고 가정 1단계: 3 꺼냄3은 5보다 작음 → 5를 뒤로 밀고 3을 앞에 넣어줌[3, 5, 4, 1, 2]↑ 정렬된 부분: [3, 5] 2단계: 4 꺼냄4는 5보다 작고 3보다는 큼 → 3과 5 사이에 넣음[3, 5, 4, 1, 2]↑..

버블 정렬은 큰 값을 배열 끝에 위치시키지만,선택정렬은 작은 값을 한 번에 하나씩 위치에 배열 배열 앞에서부터 하나씩 채워 넣으며 정렬이 진행된다. 작동 방식🔥 (계속해서) 최솟값을 찾아 앞에 놓는다. 배열: [5, 3, 4, 1, 2] 배열: [5, 3, 4, 1, 2]첫 번째 요소(5)부터 시작5와 3 비교 → 더 작은 값은 3 → 임시 최솟값 = 3다음 값 4와 비교3 vs 4 → 여전히 3이 최솟값 유지다음 값 1과 비교3 vs 1 → 새로운 최솟값 = 1 (초록색으로 표시됨)마지막 값 2와 비교1 vs 2 → 최솟값은 그대로 1최솟값 찾기 완료 → 자리 교환(swap)처음 값 5와 최솟값 1 교환결과: [1, 3, 4, 5, 2]

⭐ 정렬이란?컬렉션(collection)의 항목을 재배열하는 과정을 의미ex) 문자열 하나 고른 후 문자열 내의 각 문자를 정렬하는 것숫자 오름차순/내림차순, 알파벳순, 객체의 특정 속성(개봉연도, 수익 등) 기준으로도 가능뭘 어떻게 비교해서 정렬하는지 중요하지 x왜 배우냐?내장 sort()가 내부적으로 어떤 알고리즘을 쓰는지 이해해야 최적의 선택 가능각 알고리즘은 상황에 따라 강점/약점이 다름 → ex) 거의 정렬된 배열은 삽입 정렬이 훨씬 빠름시각화와 비교"Sorting Algorithm Animations" 사이트나 영상으로 여러 정렬을 동시에 비교 가능구글링 하다 찾은 사이트https://anim.ide.sk/sorting_algorithms_1.php Interactive animationsSi..

목차1. 검색 알고리즘이 무엇인가2. 배열에 선형 검색(linear search)를 실시한다3. 배열에서의 이진 검색을 실시한다.4. naive 문자열 검색 알고리즘과 KMP 문자열 검색 알고리즘을 구현한다.선형 검색배열이나 리스트에서 앞에서부터 하나씩 차례대로 검사하여 원하는 값을 찾는 방법데이터가 정렬되어 있지 않을 때 사용 가능한 가장 기본적인 검색 알고리즘👉🏻모든 개별 항목을 순서대로 살펴보며 원하는 값이 있는지 확인한다 배열에서 사용하는 search methods- indexOf- inclues- find- findlndex Linear Search12를 찾아라[5, 8, 1, 100, 12, 3, 12] 0 1 2 3 4 4번째에 12가 있으니 true를 반환한다.Lin..

https://youtu.be/TuABjUV7xGg?si=cKGeRPH3mIZVcc3X