Data Structures & Algorithms with Javascript : Sorting Algorithms (Advanced)

2024.07.27 - [🤖 data structures & algorithms] - Data Structures & Algorithms with Javascript : Sorting Algorithms (basic)

Data Structures & Algorithms with Javascript : Sorting Algorithms (basic)

👩🏻‍💻 이전 포스팅에서는 기본 정렬 알고리즘인  버블 정렬, 선택 정렬, 그리고 삽입 정렬에 대해 알아봤다.
🍀 이번에는 많은 데이터가 있을 때 효율적으로 정렬할 수 있는 좀 더 심화된 정렬 알고리즘들에 대해 알아보자.

☑️ 오늘 살펴볼 알고리즘 : Shellsort, Mergesort, Quicksort

The Shellsort Algorithm

 

Shellsort는 개발한 Donald Shell에서 따온 이름이다. 이전 살펴본 삽입 정렬을 개선한 버전이다. 

Shellsort는 인접한 엘리먼트를 먼저 살펴보는 대신 가장 먼 엘리먼트들을 비교한다. 

가장 먼 엘리먼트들의 gap을 점점 줄여가는데, 이 gap 시퀀스는  Marcin Ciura의 논문(“Best Increments for the Average Case of Shell Sort”, 2001)에서 Shellsort의 평균 gap 시퀀스인 701, 301, 132, 57, 23, 10, 4, 1으로 정의한 것을 활용할 것이다.

 

다음은 gap 시퀀스를 각각 3,2,1로 설정했을 경우를 보여준다.

gap 시퀀스 = 3인 경우 shellSort 예시를 살펴보자. 

61 85 19 88 68 8 70 29 (시작)
61 85 19 88 68 8 70 29 
61 8 19 88 68 85 70 29
61 8 19 88 68 85 70 29
61 8 19 29 68 85 70 88 (gap = 1 로 줄이기)
8 19 61 29 68 85 70 88
8 19 29 61 68 85 70 88
8 19 29 61 68 70 85  88 (완료)

 

구현

 

위의 예시에서 살펴봤듯이 정해진 gap(간격)만큼 배열 전체를 순회하면서 gap 내부의 값들을 비교해서 정렬한다.

점점 gap을 줄이면서 작은 값이 오른쪽에 오도록 자리를 바꿔주다 보면 정렬이 된다.

gap이 1일 경우 삽입 정렬과 동일한 매커니즘으로 정렬을 해주고 있다.

 

shellSort 매서드를 구현해 보자.

외부 for 루프를 돌면서 gap을 순회한다. 위의 예시에서는 gap 배열이 [3,1]로 이루어진 경우다.

내부 for 루프에서는 정렬하고자하는 배열의 첫 요소와 gap 만큼의 떨어진 인덱스에 위치한 요소의 대소를 비교하여 값이 작은 거를 배열 앞에 오도록 자리를 바꿔준다. 

예를 들어, 현재 gap이 3일 때 모든 배열 원소 0과 3, 1과 4, 2와 5... 대소 비교를 해서 자리를 바꿔준다. 모든 자리바꿈이 끝난 뒤, gap이 1일 때, 모든 배열 원소 0과 1, 1과 2, 2와 3... 대소 비교를 해서 자리를 바꿔주면 정렬을 완료한다.

 shellSort(){
    for (let g = 0; g < this.gaps.length; ++g) {
        for (let i = this.gaps[g]; i < this.dataStore.length; ++i) { 
            let temp = this.dataStore[i];
            for (let j = i; j >= this.gaps[g] && this.dataStore[j-this.gaps[g]] > temp; j -= this.gaps[g]) {
                this.dataStore[j] = this.dataStore[j - this.gaps[g]]; 
            }
            this.dataStore[g] = temp; 
        }
    }
}

 

단순 삽입 정렬보다 gap을 줄여가면서 비교를 하기 때문에 더 효율적인 알고리즘이다.

다시 말해, 삽입 정렬은  정렬이 완료될 때까지 모든 요소들을 비교해야 하므로 배열의 끝까지 순회를 반복해야한다.

하지만 gap=5인 경우 모든 배열요소들을 순회하는 것이 아니라 배열 길이 -5 만큼 순회하고, 그다음에는 gap =3 인 경우에는 q배열 길이 -3, 그 다음 gap=1인 경우에는 이미 정렬이 많이 된 배열 길이를 돌기 때문에 효율적이다.

👇 전체 코드

class CustomArray{
	constructor(numElements){
    	this.dataStore = [];
        this.pos = 0;
        this.numElements = numElements;
        
        for (let i = 0; i < numElements; ++i) { 
        	this.dataStore[i] = i;
		}
        
        /////////////////////////// 💖 추가 ///////////////////////////
        this.gaps = [5,3,1];
        /////////////////////////// 💖 추가 ///////////////////////////
    }
    
    // 삽입
    insert(element){
    	this.dataStore[this.pos++] = element;
    }

	// 출력 포멧해주기 위한 헬퍼함수
    toString(){
    	let retstr = "";
		for (let i = 0; i < this.dataStore.length; ++i) {
			retstr += this.dataStore[i] + " "; 
            if (i > 0 && i % 10 == 0) {
         		retstr += "\n";
      		}
		}
		return retstr;
    }
    
    // 제거
    clear(){
    	for (let i = 0; i < this.dataStore.length; ++i) {
			this.dataStore[i] = 0; 
        }
    }
    
    // 랜덤 데이터 생성
    setData(){
    	for (let i = 0; i < this.numElements; ++i) {
			this.dataStore[i] = Math.floor(Math.random() * (this.numElements+1));
		}
    }
    
    // index1 과 index2의 자리 변경
    swap(arr, index1, index2){
    	let temp = arr[index1];
        arr[index1] = arr[index2];
        arr[index2] = temp;
    }
    
  
    bubbleSort(){
    	let numElements = this.dataStore.length;
        let temp;
        for(let outer = numElements; outer >=2; --outer){
        	for(let inner = 0; inner <= outer-1; ++inner){
            	if(this.dataStore[inner] > this.dataStore[inner+1]){
                	this.swap(this.dataStore, inner, inner+1);
                }
            }
        }
    
    }
    
    
    selectionSort(){
        let min,temp;
        for(let outer = 0; outer <= this.dataStore.length-2; ++outer){
            min = outer;
            for(let inner = outer+1; inner <= this.dataStore.length-1; ++inner){
                if(this.dataStore[inner] < this.dataStore[min]){
                   min = inner;
                }
                this.swap(this.dataStore, outer, min);
            }
        }
	}
     
    insertionSort(){
        let temp, inner;
        for(let outer = 1; outer <= this.dataStore.length-1; ++outer){
            temp = this.dataStore[outer];
            inner = outer;
            while(inner > 0 && (this.dataStore[inner-1] >= temp)){
                this.dataStore[inner] = this.dataStore[inner-1];
                --inner;
            }
            this.dataStore[inner] = temp;
        }
	}
    /////////////////////////// 💖 추가 ///////////////////////////
    setGaps(arr){
    	this.gaps = arr;
    }
    
      shellSort() {
        for (let g = 0; g < this.gaps.length; ++g) {
          for (let i = this.gaps[g]; i < this.dataStore.length; ++i) {
            let temp = this.dataStore[i];
            let j;
            for (j = i; j >= this.gaps[g] && this.dataStore[j - this.gaps[g]] > temp; j -= this.gaps[g]) {
              this.dataStore[j] = this.dataStore[j - this.gaps[g]];
            }
            this.dataStore[j] = temp;
          }
        }
      }
    /////////////////////////// 💖 추가 ///////////////////////////

}

const print = item => console.log(item);

let numElements = 10;
let myNums = new CustomArray(numElements);
myNums.setData();
print(myNums.toString());
myNums.shellSort();
print('정렬 후:');
print(myNums.toString());

/**
9 6 9 10 7 5 9 7 3 7 
정렬 후:
3 5 6 7 7 7 9 9 9 10 
*/

 

논문에서 정한 gap 시퀀스가 정말 제일 효율적일까? 

이번에는 gap 시퀀스를 동적으로 계산하는 경우를 한번 살펴보자.

다음은 Robert Sedgewick이 구안한 gap 시퀀스를 동적으로 계산할 수 있는 코드다.

let N = this.dataStore.length; 
let h = 1;
while (h < N/3) {
	h = 3 * h + 1; 
    }

 

gap 값이 결정되면 이전 방식대로 shellsort이 동작한다. 다만 차이점은 외부 for 루프로 돌아가기 전에 새로운 gap 값을 계산한다. 

 dynamicGapShellSort(){
 	let N = this.dataStore.length; 
    let h = 1;
    while (h < N/3) {
        h = 3 * h + 1; 
    }
    while(h >= 1){
    	for(let i = h; i < N; i++){
        	for(let j =i; j>=h && this.dataStore[j] < this.dataStore[j-h]; j -= h){
            	this.swap(this.dataStore,j,j-h);
            }
        }
        h = (h-1)/3;
    }
  	
}

👇 전체 코드

class CustomArray{
	constructor(numElements){
    	this.dataStore = [];
        this.pos = 0;
        this.numElements = numElements;
        
        for (let i = 0; i < numElements; ++i) { 
        	this.dataStore[i] = i;
		}
        
        this.gaps = [5,3,1];
    }
    
    // 삽입
    insert(element){
    	this.dataStore[this.pos++] = element;
    }

	// 출력 포멧해주기 위한 헬퍼함수
    toString(){
    	let retstr = "";
		for (let i = 0; i < this.dataStore.length; ++i) {
			retstr += this.dataStore[i] + " "; 
            if (i > 0 && i % 10 == 0) {
         		retstr += "\n";
      		}
		}
		return retstr;
    }
    
    // 제거
    clear(){
    	for (let i = 0; i < this.dataStore.length; ++i) {
			this.dataStore[i] = 0; 
        }
    }
    
    // 랜덤 데이터 생성
    setData(){
    	for (let i = 0; i < this.numElements; ++i) {
			this.dataStore[i] = Math.floor(Math.random() * (this.numElements+1));
		}
    }
    
    // index1 과 index2의 자리 변경
    swap(arr, index1, index2){
    	let temp = arr[index1];
        arr[index1] = arr[index2];
        arr[index2] = temp;
    }
    
  
    bubbleSort(){
    	let numElements = this.dataStore.length;
        let temp;
        for(let outer = numElements; outer >=2; --outer){
        	for(let inner = 0; inner <= outer-1; ++inner){
            	if(this.dataStore[inner] > this.dataStore[inner+1]){
                	this.swap(this.dataStore, inner, inner+1);
                }
            }
        }
    
    }
    
    
    selectionSort(){
        let min,temp;
        for(let outer = 0; outer <= this.dataStore.length-2; ++outer){
            min = outer;
            for(let inner = outer+1; inner <= this.dataStore.length-1; ++inner){
                if(this.dataStore[inner] < this.dataStore[min]){
                   min = inner;
                }
                this.swap(this.dataStore, outer, min);
            }
        }
	}
     
    insertionSort(){
        let temp, inner;
        for(let outer = 1; outer <= this.dataStore.length-1; ++outer){
            temp = this.dataStore[outer];
            inner = outer;
            while(inner > 0 && (this.dataStore[inner-1] >= temp)){
                this.dataStore[inner] = this.dataStore[inner-1];
                --inner;
            }
            this.dataStore[inner] = temp;
        }
	}
    
    setGaps(arr){
    	this.gaps = arr;
    }
    
      shellSort() {
        for (let g = 0; g < this.gaps.length; ++g) {
          for (let i = this.gaps[g]; i < this.dataStore.length; ++i) {
            let temp = this.dataStore[i];
            let j;
            for (j = i; j >= this.gaps[g] && this.dataStore[j - this.gaps[g]] > temp; j -= this.gaps[g]) {
              this.dataStore[j] = this.dataStore[j - this.gaps[g]];
            }
            this.dataStore[j] = temp;
          }
        }
      }
    /////////////////////////// 💖 추가 ///////////////////////////
    
    dynamicGapShellSort(){
        let N = this.dataStore.length; 
        let h = 1;
        while (h < N/3) {
            h = 3 * h + 1; 
        }
        while(h >= 1){
            for(let i = h; i < N; i++){
                for(let j =i; j>=h && this.dataStore[j] < this.dataStore[j-h]; j -= h){
                    this.swap(this.dataStore,j,j-h);
                }
            }
			 h = (h-1)/3;
        }
       
    }
    /////////////////////////// 💖 추가 ///////////////////////////

}

const print = item => console.log(item);

let numElements = 10;
let myNums = new CustomArray(numElements);
myNums.setData();
print(myNums.toString());
myNums.dynamicGapShellSort();
print('정렬 후:');
print(myNums.toString());

/**
0 3 6 4 4 1 7 3 7 5
정렬 후:
0 1 3 3 4 4 5 6 7 7 
*/

다음 정렬 알고리즘들을 살펴보기 전에 두 gap 시퀀스의 러닝 타임을 비교해 보자! 

두 방법 모두 효율성은 같다는 걸 확인할 수 있다.

let nums = new CustomArray(10000);
nums.setData();
let start = new Date().getTime();
nums.shellSort();
let stop = new Date().getTime();
let elapsed = stop - start;
print("Shellsort with hard-coded gap sequence: " + elapsed + " ms."); 
nums.clear();
nums.setData();
start = new Date().getTime();
nums.dynamicGapShellSort();
stop = new Date().getTime();
print("Shellsort with dynamic gap sequence: " + elapsed + " ms.");

/**
Shellsort with hard-coded gap sequence: 16 ms.
Shellsort with dynamic gap sequence: 16 ms.

Shellsort with hard-coded gap sequence: 27 ms.
Shellsort with dynamic gap sequence: 27 ms.

Shellsort with hard-coded gap sequence: 29 ms.
Shellsort with dynamic gap sequence: 29 ms.
*/

 

The  Mergesort Algorithm

Mergesort은 정렬된 sublist들을 merge(합병)해서 완전하게 정렬된 리스트를 만든다는 점에서 이름을 지었다.

이론적으로 mergesort 알고리즘은 구현하기 어렵지 않다.

두 개의 정렬된 부분 배열들과 이 두 배열들의 대소 관계를 비교하여 합친 세 번째 배열만 있으면 된다.

하지만 실제로 구현하고자 할 때는 엄청 많은 데이터들을 다뤄야 한다면 두 배열들을 합칠 공간을 마련해야 하기 때문에 메모리 측면에서는 효율성이 떨어질 수 있다.

Top-down vs. Bottom-up Mergesort

필수 요소는 아니지만 mergesort를 재귀 알고리즘을 활용해  다음과 같이 구현할 수 있다.

하지만 CustomArray의 메서드로 추가하려고 하면 재귀 깊이가 너무 깊어져서 활용할 수 없다.

// Function to merge two halves into a sorted array
function merge(left, right) {
    let result = [];
    let leftIndex = 0;
    let rightIndex = 0;

    // Concatenate values into the result array in sorted order
    while (leftIndex < left.length && rightIndex < right.length) {
        if (left[leftIndex] < right[rightIndex]) {
            result.push(left[leftIndex]);
            leftIndex++;
        } else {
            result.push(right[rightIndex]);
            rightIndex++;
        }
    }

    // Concatenate remaining elements of left and right arrays
    return result.concat(left.slice(leftIndex)).concat(right.slice(rightIndex));
}

// Function to perform top-down merge sort
function mergeSort(array) {
    // Base case: single element or empty array
    if (array.length <= 1) {
        return array;
    }

    // Find the middle index to split the array into two halves
    const middleIndex = Math.floor(array.length / 2);

    // Recursively sort the left and right halves
    const left = mergeSort(array.slice(0, middleIndex));
    const right = mergeSort(array.slice(middleIndex));

    // Merge the sorted halves
    return merge(left, right);
}

// Example usage
const array = [38, 27, 43, 3, 9, 82, 10];
console.log('Unsorted array:', array);
const sortedArray = mergeSort(array);
console.log('Sorted array:', sortedArray);
/**
	Unsorted array: (7) [38, 27, 43, 3, 9, 82, 10]
	Sorted array: (7) [3, 9, 10, 27, 38, 43, 82]
*/

 

하지만 자바스크립트로는 재귀 깊이가 너무 깊어서 불가능하다.

 

대신 비재귀적인 bottom-up Mergesort를  살펴보자.

 

 

먼저 정렬하고자 하는 데이터를 모두 하나의 배열로 쪼개준다.

그 뒤 각 배열 요소들보다 무조건 큰 값인 infinity를 오른쪽에 배치하여 짝을 지어주고 각 짝을 왼쪽과 오른쪽 부분 배열로 지정한다. 이때 infinity(무한)은 sentinel(감시자) 값으로 쓰인다고 하는데, 왼쪽이나 오른쪽 부분 배열의 끝을 나타내기 위해 쓰인다. 왼쪽과 오른쪽 부분 배열들을 가져와 정렬해 준 새로운 배열로 합쳐주고, 마지막에 부분 배열들이 더 이상 없을 때까지 반복해 주면 정렬이 완성된다.

구현

mergeSort(){
    if(this.dataStore.length <2){
        return;
    }
    let step = 1;
    let left,right;
    while(step < this.dataStore.length){
        left = 0;
        right = step;
        while(right+step <= this.dataStore.length){
            this.mergeArrays(this.dataStore, left, left+step, right, right+step);
            left = right + step;
            right = left + step;
    	}
        if(right < this.dataStore.length){
        	this.mergeArrays(this.dataStore, left, left+step, right, this.dataStore.length);
    	}
    	step *= 2;
    	}
}

mergeArrays(arr,startLeft, stopLeft, startRight, stopRight){
	let rightArr = new Array(stopRight - startRight + 1);
    let leftArr = new Array(stopLeft - startLeft + 1);
    let k = startRight;
    for(let i = 0; i< (rightArr.length-1); ++i){
    	rightArr[i] = arr[k];
        ++k;
    }
    k = startLeft;
    for(let i=0; i< (leftArr.length-1);++i){
    	leftArr[i] = arr[k];
		++k;
    }
	rightArr[rightArr.length-1] = Infinity;
    leftArr[leftArr.length-1] = Infinity;
	let m = 0;
    let n = 0;
    for (let k = startLeft; k < stopRight; ++k) { 
    	if (leftArr[m] <= rightArr[n]) {
             arr[k] = leftArr[m];
    		m++; 
        } else {
    		arr[k] = rightArr[n]; n++;
    	} 
    }
    this.print("left array - ", leftArr);
    this.print("right array - ", rightArr);

}

👇 전체 코드

class CustomArray{
	constructor(numElements){
    	this.dataStore = [];
        this.pos = 0;
        this.numElements = numElements;
        
        for (let i = 0; i < numElements; ++i) { 
        	this.dataStore[i] = i;
		}
        
        this.gaps = [5,3,1];
    }

    /////////////////////////// 💖 추가 ///////////////////////////
    // 출력 헬퍼 
    print(label,arr,...others){
        console.log(`${label} [${arr}] ${others}`);
    }
    /////////////////////////// 💖 추가 ///////////////////////////
    
    // 삽입
    insert(element){
    	this.dataStore[this.pos++] = element;
    }

	// 출력 포멧해주기 위한 헬퍼함수
    toString(){
    	let retstr = "";
		for (let i = 0; i < this.dataStore.length; ++i) {
			retstr += this.dataStore[i] + " "; 
            if (i > 0 && i % 10 == 0) {
         		retstr += "\n";
      		}
		}
		return retstr;
    }
    
    // 제거
    clear(){
    	for (let i = 0; i < this.dataStore.length; ++i) {
			this.dataStore[i] = 0; 
        }
    }
    
    // 랜덤 데이터 생성
    setData(){
    	for (let i = 0; i < this.numElements; ++i) {
			this.dataStore[i] = Math.floor(Math.random() * (this.numElements+1));
		}
    }
    
    // index1 과 index2의 자리 변경
    swap(arr, index1, index2){
    	let temp = arr[index1];
        arr[index1] = arr[index2];
        arr[index2] = temp;
    }
    
  
    bubbleSort(){
    	let numElements = this.dataStore.length;
        let temp;
        for(let outer = numElements; outer >=2; --outer){
        	for(let inner = 0; inner <= outer-1; ++inner){
            	if(this.dataStore[inner] > this.dataStore[inner+1]){
                	this.swap(this.dataStore, inner, inner+1);
                }
            }
        }
    
    }
    
    
    selectionSort(){
        let min,temp;
        for(let outer = 0; outer <= this.dataStore.length-2; ++outer){
            min = outer;
            for(let inner = outer+1; inner <= this.dataStore.length-1; ++inner){
                if(this.dataStore[inner] < this.dataStore[min]){
                   min = inner;
                }
                this.swap(this.dataStore, outer, min);
            }
        }
	}
     
    insertionSort(){
        let temp, inner;
        for(let outer = 1; outer <= this.dataStore.length-1; ++outer){
            temp = this.dataStore[outer];
            inner = outer;
            while(inner > 0 && (this.dataStore[inner-1] >= temp)){
                this.dataStore[inner] = this.dataStore[inner-1];
                --inner;
            }
            this.dataStore[inner] = temp;
        }
	}
    
    setGaps(arr){
    	this.gaps = arr;
    }
    
      shellSort() {
        for (let g = 0; g < this.gaps.length; ++g) {
          for (let i = this.gaps[g]; i < this.dataStore.length; ++i) {
            let temp = this.dataStore[i];
            let j;
            for (j = i; j >= this.gaps[g] && this.dataStore[j - this.gaps[g]] > temp; j -= this.gaps[g]) {
              this.dataStore[j] = this.dataStore[j - this.gaps[g]];
            }
            this.dataStore[j] = temp;
          }
        }
      }
   
    
    dynamicGapShellSort(){
        let N = this.dataStore.length; 
        let h = 1;
        while (h < N/3) {
            h = 3 * h + 1; 
        }
        while(h >= 1){
            for(let i = h; i < N; i++){
                for(let j =i; j>=h && this.dataStore[j] < this.dataStore[j-h]; j -= h){
                    this.swap(this.dataStore,j,j-h);
                }
            }
			 h = (h-1)/3;
        }
       
    }
    /////////////////////////// 💖 추가 ///////////////////////////
    mergeSort(){
	if(this.dataStore.length <2){
        return;
    }
        let step = 1;
        let left,right;
    	while(step < this.dataStore.length){
        	left = 0;
            right = step;
            while(right+step <= this.dataStore.length){
        	this.mergeArrays(this.dataStore, left, left+step, right, right+step);
            left = right + step;
            right = left + step;
        }
            if(right < this.dataStore.length){
        	this.mergeArrays(this.dataStore, left, left+step, right, this.dataStore.length);
        }
        step *= 2;
        }
       
        
    }


    mergeArrays(arr,startLeft, stopLeft, startRight, stopRight){
        let rightArr = new Array(stopRight - startRight + 1);
        let leftArr = new Array(stopLeft - startLeft + 1);
        let k = startRight;
        for(let i = 0; i< (rightArr.length-1); ++i){
            rightArr[i] = arr[k];
            ++k;
        }
        k = startLeft;
        for(let i=0; i< (leftArr.length-1);++i){
            leftArr[i] = arr[k];
            ++k;
        }
        rightArr[rightArr.length-1] = Infinity;
        leftArr[leftArr.length-1] = Infinity;
        let m = 0;
        let n = 0;
        for (let k = startLeft; k < stopRight; ++k) { 
            if (leftArr[m] <= rightArr[n]) {
                 arr[k] = leftArr[m];
                m++; 
            } else {
                arr[k] = rightArr[n]; n++;
            } 
        }
        this.print("left array - ", leftArr);
        this.print("right array - ", rightArr);

    }
     /////////////////////////// 💖 추가 ///////////////////////////

}

const print = item => console.log(item);

let numElements = 10;
let myNums = new CustomArray(numElements);
myNums.setData();
print(myNums.toString());
myNums.mergeSort();
print('정렬 후:');
print(myNums.toString());

/**
2 8 9 1 3 7 3 9 9 0 
left array -  [2,Infinity] 
right array -  [8,Infinity] 
left array -  [9,Infinity] 
right array -  [1,Infinity] 
left array -  [3,Infinity] 
right array -  [7,Infinity] 
left array -  [3,Infinity] 
right array -  [9,Infinity] 
left array -  [9,Infinity] 
right array -  [0,Infinity] 
left array -  [2,8,Infinity] 
right array -  [1,9,Infinity] 
left array -  [3,7,Infinity] 
right array -  [3,9,Infinity] 
left array -  [1,2,8,9,Infinity] 
right array -  [3,3,7,9,Infinity] 
left array -  [1,2,3,3,7,8,9,9,Infinity] 
right array -  [0,9,Infinity] 
정렬 후:
0 1 2 3 3 7 8 9 9 9 
*/

The  Quicksort Algorithm

Quicksort은 많은 데이터양을 정렬하기 위한 알고리즘 중 가장 빠른 축에 속한다.

분할 정복(divide and conquer)에 의해 재귀적으로 리스트를 더 작은 부분 리스트로 쪼개준다.

리스트를 pivot을 기준으로 부분 리스트로 쪼개주는데, pivot보다 작은 값들은 리스트의 왼쪽(아래)에, 큰 값들은 오른쪽(위)에 배치한다.

 

다음 예시를 살펴보자. pivot은 각 리스트의 마지막 요소로 지정하자.

정렬 전: [10, 7, 8, 9, 1, 5]
Partitioning: pivot=5, array= [1, 5, 8, 9, 10, 7]
Partitioning: pivot=7, array= [1, 5, 7, 9, 10, 8]
Partitioning: pivot=8, array= [1, 5, 7, 8, 10, 9]
Partitioning: pivot=9, array= [1, 5, 7, 8, 9, 10]
정렬 후: [1, 5, 7, 8, 9, 10]

 

알고리즘 흐름을 살펴보면,

1. 배열을 두 부분으로 나눌 pivot 요소를 고른다.
2. pivot보다 작은 값들은 전에, 큰 값들은 뒤에 오도록 정렬한다.
3. 오름차순으로 정렬될 때까지 1과 2를 반복한다.

구현

재귀적으로 quickSort를 호출하기 때문에 이전 클래스가 아닌 직접 랜덤 숫자로 배열을 만들어 쓰자. 

function quickSort(arr){
	if(arr.length===0){
    	return [];
    }
    let left = [];
    let right = [];
    let pivot = arr[0]; // 구현은 배열의 첫 요소를 pivot으로 지정
    for(let i = 1; i< arr.length; i++){
    	if(arr[i] < pivot){
        	left.push(arr[i]);
        } else {
        	right.push(arr[i]);
        }
    }
    return quickSort(left).concat(pivot, quickSort(right));
}
const print = item => console.log(item);
let arr = Array.from({length:10},()=>Math.floor((Math.random()*100)+1));

print(arr); // [72, 50, 36, 55, 25, 75, 90, 45, 39, 46]
print();
print(quickSort(arr)); // [25, 36, 39, 45, 46, 50, 55, 72, 75, 90]

 

quickSort는 데이터 수가 많을 때 쓰면 좋다. 데이터 수가 적을수록 성능이 떨어진다.

이번에는 pivot 선택에 따라 어떻게 데이터가 pivot 중심으로 정렬되는지 살펴보자.

const print = item => console.log(item);

function quickSort(arr){
	if(arr.length===0){
    	return [];
    }
    let left = [];
    let right = [];
    let pivot = arr[0]; 
    for(let i = 1; i< arr.length; i++){
		print(`pivot: ${pivot}, current element: ${arr[i]}`); // 💖 로그 추가
    	if(arr[i] < pivot){
			print(`moving ${arr[i]} to the left`); // 💖 로그 추가
        	left.push(arr[i]);
        } else {
			print(`moving ${arr[i]} to the right`); // 💖 로그 추가
        	right.push(arr[i]);    
        }
    }
    return quickSort(left).concat(pivot, quickSort(right));
}

let arr = Array.from({length:10},()=>Math.floor((Math.random()*100)+1));

print(arr);
print();
print(quickSort(arr)); 

/**
[65, 70, 12, 6, 35, 40, 15, 21, 83, 44]
pivot: 65, current element: 70
moving 70 to the right
pivot: 65, current element: 12
moving 12 to the left
pivot: 65, current element: 6
moving 6 to the left
pivot: 65, current element: 35
moving 35 to the left
pivot: 65, current element: 40
moving 40 to the left
pivot: 65, current element: 15
moving 15 to the left
pivot: 65, current element: 21
moving 21 to the left
pivot: 65, current element: 83
moving 83 to the right
pivot: 65, current element: 44
moving 44 to the left
pivot: 12, current element: 6
moving 6 to the left
pivot: 12, current element: 35
moving 35 to the right
pivot: 12, current element: 40
moving 40 to the right
pivot: 12, current element: 15
moving 15 to the right
pivot: 12, current element: 21
moving 21 to the right
pivot: 12, current element: 44
moving 44 to the right
pivot: 35, current element: 40
moving 40 to the right
pivot: 35, current element: 15
moving 15 to the left
pivot: 35, current element: 21
moving 21 to the left
pivot: 35, current element: 44
moving 44 to the right
pivot: 15, current element: 21
moving 21 to the right
pivot: 40, current element: 44
moving 44 to the right
pivot: 70, current element: 83
moving 83 to the right
[6, 12, 15, 21, 35, 40, 44, 65, 70, 83]
*/

---

🍀 마치면서

?? 170쪽에서 Heapsort에 대해서도 알아본다고 했는데 해당 내용이 누락되어 있어서 당황..
🤔 개인적으로 heapsort 공부 후 내용 정리하여 추가해 봐야겠다.

📚 Reference

- Data Structures and Algorithms Using Java‐ Script by Michael McMillian (O’Reilly). Copyright 2014 Michael McMillan, 978-1-449-36493-9