자료구조와 알고리즘 5장 정렬 알고리즘(2)

TIL 날짜

2023.12.06

Contents

1. 병합 정렬
2. 퀵 정렬
3. 기수 정렬
4. 정렬 알고리즘의 빅오 표기법

병합 정렬

의미: 분할 정복 알고리즘의 하나이다.

과정

장점

• 안정적인 정렬 방법 (상대적인 순서 변경X)
• 입력 데이터가 무엇이든 시간 동일
• 레코드를 연결 리스트(Linked List)로 구성하면, 데이터의 이동이 작아진다.
• 소규모의 데이터를 정렬할때 효율적

단점

• 배열로 구성되어 있을 경우 임시 배열 필요로 추가적인 메모리 필요하다.
• 대규모의 데이터를 정렬할때는 시간 낭비 발생

함수

function mergeSort(arr){
    if(arr.length <= 1) return arr;
    let mid = Math.floor(arr.length/2);
    let left = mergeSort(arr.slice(0,mid));
    let right = mergeSort(arr.slice(mid));
    return merge(left, sright);
}

mergeSort([10,24,76,73])

 

퀵 정렬

의미: 분할 정복과 재귀방식을 이용한 정렬 알고리즘

과정

장점

• 추가 공간이 필요하지 않는다.
• O(n log n)의 시간 복잡도를 가지므로 다른 정렬 알고리즘보다 빠르다.
• 정렬하고자 하는 배열 안에서 교환하는 방식으로 다른 메모리 공간을 필요로 하지 않는다.

단점

• 불안정 정렬로 데이터가 원하는 값이 안 나올수도 있다.
• 정렬된 배열에 대해서는 Quick sort의 불균형 분할에 의해 오히려 수행시간이 더 걸린다.

함수

function quickSort(arr, left = 0, right = arr.length -1){
    if(left < right){
        let pivotIndex = pivot(arr, left, right) //3
        //left
        quickSort(arr,left,pivotIndex-1);
        //right
        quickSort(arr,pivotIndex+1,right);
      }
     return arr;
} 
           
quickSort([100,-3,2,4,6,9,1,2,5,3,23])

 

기수 정렬

의미: 정수들만 정렬하는 정수 정렬 알고리즘으로 비교를 하지 않는 알고리즘

과정

장점

• 안정적인 정렬: 동일한 키 값을 가진 요소의 상대적인 순서 보존
• 분배 정렬로 자릿수자대로 확인한다.
• 선형 시간 복잡도: 시간 복잡도가 비교 정렬 알고리즘보다 빠를 수 있다.

단점

• 키 값의 자릿수에 따라 메모리 추가 요구
• 정렬 대상의 특성: 정수 및 문자열과 같은 자릿수를 제외한 따른 값일 경우 적합하지 않는다.
• 키 값이 많을수록 성능 저하

함수

function getDigit(num, i) {
  return Math.floor(Math.abs(num) / Math.pow(10, i)) % 10;
}

function digitCount(num){
	if(num === 0) return 1;
    return Math.floor(Math.log10(Math.abs(num)) +1;
}

function mostDigits(nums){
	let maxDigits = 0;
    for(let i=0; i<num.length; i++){
    maxDigits = Math.max(maxDigits, digitCount(nums[i]));
    }
    return maxDigits
}

function radixSort (nums) {
	let maxDigits = mostDigits(nums);
    for(let k = 0; k < maxDigitCount; k++){
        let digitBuckets = Array.from({length: 10}, () => []);
        for(let i = 0; i < nums.length; i++){
            let digit = getDigit(nums[i],k);
            digitBuckets[digit].push(nums[i]);
        }
        nums = [].concat(...digitBuckets);
    }
    return nums;
}

radixSort([23,345,5467,12,2345,9852])

 

정렬 알고리즘의 빅오 표기법

	병합 정렬	퀵 정렬	기수 정렬
최적의 경우	O (n log n)	O (n log n)	O (nk)
평균적인 값	O (n log n)	O (n log n)	O (nk)
최악의 경우	O (n log n)	O (n^2)	O (nk)
공간 복잡도	O (n)	O (log n)	O (n+k)