fullfish의 개발자 도전기

위의 gif는 실수로 아래쪽 임시 배열부분을 빠트렸다... 그런데 배열의 데이터를 직접 지정못해줘서 아래 예시도 함께 들겠다 (모든 정렬방법의 데이터가 같은 상태) 병합 정렬이란? 재귀적으로 분할해서 정렬한후 merge하는 방법 시간복잡도 시간 복잡도 최악 O(n log n) 평균 O(n log n) 최상 O(n log n) 공간 복잡도 전체 O(n) 특징 안정 정렬(Stable Sort) 분할 정복 알고리즘 임시 배열 필요 배열의 크기가 크면 이동 횟수가 많아짐 시작 복잡도가 일정하다 (데이터 분포에 영향을 덜 받음) 로직 재귀. 배열을 반으로 쪼갠다 배열의 길이가 1이하가 될때 까지 재귀적으로 반복한다 병합하면서 정렬한다 코드 function main(arr) { mergeSort(arr, 0, ar..

셸 정렬이란? 삽입정렬을 보완한 정렬 시간복잡도 시간 복잡도 시간 복잡도 최악 O(n^2) (worst known worst case gap sequence) O(n log^2 n) (best known worst case gap sequence) 평균 depends on gap sequence 최상 O(n log n) (most gap sequences) O(n log^2 n) (best known worst case gap sequence) 공간 복잡도 전체 O(n), 보조 O(1) 특징 삽입정렬은 거의 정렬된 경우 빠르다 삽입 정렬은 삽입될 위치가 멀 경우 이동을 많이 해야하며 한 번에 한 요소의 위치만 결정됨 이러한 삽입 정렬의 장점을 살리고 단점을 보완한것이 셸 정렬이다 로직 gap만큼씩 떨어진..

삽입 정렬이란? 이미 정렬된 부분에서 새로운 요소가 들어갈 위치를 찾아 넣음 시간복잡도 시간 복잡도 (comparisons) 시간 복잡도 (swaps) 최악 O(n^2) O(n^2) 평균 O(n^2) O(n^2) 최상 O(n) O(1) 공간 복잡도 전체 O(n), 보조 O(1) 특징 안정 정렬(Stable Sort) 제자리 정렬(In-place Sort). 추가메모리 x 대부분 정렬된 상태일때는 빠름(요소가 적을때도 빠른편) 반대로 요소가 많을 경우 느려짐 로직 이중 for문으로 순회 index 1부터 실행. 해당 index의 왼쪽 부분의 배열에서 본인이 들어갈 위치를 찾아 넣음 예시 (오름차순의 경우) [3,5,1,2] 일 때 index 1인 5가 왼쪽의 3 보다 큰 수이므로 그대로 둔다 -> [3,5..

선택 정렬이란? 제자리 정렬 알고리즘 원소 넣을 위치는 정해져있고 무슨 원소를 넣을지 선택하는 알고리즘 시간복잡도 시간 복잡도 (comparisons) 시간 복잡도 (swaps) 최악 O(n^2) O(n) 평균 O(n^2) O(n) 최상 O(n^2) O(n) 공간 복잡도 전체 O(n), 보조 O(1) 특징 이동 횟수 미리 결정됨 크기가 같은 요소의 상대적 위치가 변경될 수 있음. 불안정 정렬(Unstable Sort) 비교횟수는 많지만 교환 횟수가 적음 제자리 정렬(In-place Sort). 추가메모리 x 로직 1. 주어진 요소 중에 최소값을 찾음 2. 그 값을 맨 앞에 위치한 값과 교체 3. 맨 처음 위치를 제외하고 반복 즉, 처음 순회때 가장 작은 요소가 0번째에 들어가며 두번째 순회때 두번째로 작..

버블 정렬이란? 인접한 요소의 크기를 비교하는것을 반복 비교정렬 추가 메모리 x 시간복잡도 시간 복잡도 (comparisons) 시간 복잡도 (swaps) 최악 O(n^2) O(n^2) 평균 O(n^2) O(n^2) 최상 O(n) O(1) 최악의 경우 공간 복잡도 전체 O(n), 보조 O(1) 특징 구현 간단함 가장 왼쪽에서 오른쪽으로 이동시 모든 요소와 교환 요소가 최종위치에 이미 있더라도 교환이 일어날 수 있다 비효율적이라 잘 안씀 로직 이중 for문으로 인접요소 크기 비교해서 큰수를 뒤로 보냄 즉, 처음 순회때 가장 큰 수가 맨 뒤로 가며 두번째 순회때 두번째로 큰 수가 뒤에서 두번째로 간다 (오름차순의 경우) 코드 function bubbleSort(arr) { for (let i = 0; i <..