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

2024.07.26 - [🪲 debug] - Data Structures & Algorithms with Javascript : Graphs and Graph Algorithms

Data Structures & Algorithms with Javascript : Graphs and Graph Algorithms

2024.07.25 - [🤖 data structures & algorithms] - Data Structures & Algorithms with Javascript : Binary Trees and Binary Search Trees Data Structures & Algorithms with Javascript : Binary Trees and Binary Search Trees2024.07.24 - [🤖 data structures &

pyotato-dev.tistory.com

데이터 연산 중 가장 자주 사용하는 건 정렬이랑 검색이다.
이번 장에서는 배열 기본/ 심화 정렬 알고리즘들을 살펴보자.

- 기본 정렬 알고리즘들 : Bubble sort, Selection sort, Insertion sort
- 심화 정렬 알고리즘들 : shellsort, mergesort, quicksort algorithm

‼ 예제는 책의 구현을 참고하여 클래스로 재구성했습니다!!

비교를 위한 커스텀 Array 클래스

각 정렬 알고리즘들을 비교하기 위해 사용할 기본 커스텀 Array 클래스를 만들어보자.

이미 자바스크립트에는 Array가 있기 때문에 클래스 이름을 CustomArray로 했다.

Array의 기본 연산인 삽입, 삭제와 추가적으로 배열 요소 교환, 출력을 위한 포매팅 메서드를 구현해 보자.

class CustomArray{
	constructor(numElements){
    	this.dataStore = [];
        this.pos = 0;
        this.numElements = numElements;
        
        for (let i = 0; i < numElements; ++i) { 
        	this.dataStore[i] = i;
		}
    }
    
    // 삽입
    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;
    }
}

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

let numElements = 100;
let myNums = new CustomArray(numElements);
myNums.setData();
print(myNums.toString());

/**

51 57 18 32 12 28 91 77 57 94 94 87 
71 76 57 44 37 14 12 3 88 47 
68 70 65 65 85 20 55 36 15 94 
52 79 98 40 42 81 16 0 56 66 
84 62 6 67 74 34 16 15 80 90 
26 88 0 8 49 30 70 47 62 47 
69 51 27 97 99 40 41 57 22 2 
47 86 32 6 88 43 36 52 64 59 
72 46 50 94 75 40 27 25 12 9 
42 25 52 10 24 63 26 62 88 

*/

기본 정렬 알고리즘

Bubble Sort

버블 정렬은 가장 느린 정렬 알고리즘 중 하나지만 그만큼 구현하기도 쉬운 알고리즘이다.

데이터를 정렬할 때 마치 거품이 한 방향으로 쏠리는 모양과 비슷해서 버블 정렬이라고 한다.

위의 이미지는 버블 정렬을 하는 첫 단계들을 나타내고 있다.

이번에는 알파벳들을 소문자부터 정렬하는 예를 한번 살펴보자.

시작 : E A B D H
정렬 : A E B D H (A와 E 자리 바꿔주기)
정렬 : A B E D H (B와 E 자리 바꿔주기)
정렬 : A B D E H (D와 E 자리 바꿔주기)

숫자들을 오름차순으로 정렬하는 예를 살펴보자.

작은 값들은 왼쪽으로 몰리고 큰 값들은 다 오른쪽으로 몰린다.

72 54 59 30 31 78 2 77 82 72 (정렬 시작!)
72 54 59 30 31 78 2 77 72 82
72 54 59 30 31 78 2 72 77 82
72 54 59 30 31 2 78 77 82 72
72 54 59 30 2 31 78 77 82 72
72 54 59 2 30 31 78 72 77 82
72 54 2 59 30 31 78 72 77 82
72 2 54 59 30 31 78 72 77 82
2 72 54 59 30 31 78 72 77 82
2 72 54 59 30 31 72 78 77 82
2 72 54 59 30 31 72 77 78 82
2 72 54 30 59 31 72 77 78 82
2 72 54 30 31 59 72 77 78 82
2 72 30 54 31 59 72 77 78 82
2 72 30 31 54 59 72 77 78 82
2 30 72 31 54 59 72 77 78 82
2 30 31 72 54 59 72 77 78 82
2 30 31 54 72 59 72 77 78 82
2 30 31 54 59 72 72 77 78 82 (정렬 완료!)

구현

위의 예시에서 살펴봤듯이 버블 정렬은 작은 값을 왼쪽으로 모두 몰아넣으면 된다.

작은 값이 왼쪽의 값보다 작으면 둘의 자리를 바꿔주는 걸 반복하고, 더 이상 바꿔줄 값들이 없다면 정렬을 마칠 수 있다.

다음과 같이 outer 루프에서는 현재 값부터 비교할 값들이 있을 때까지 반복해서 검색한다.

inner 루프에서는 배열의 첫 요소부터 현재값을 비교하여, 비교값이 더 크다면 현재값과 자리를 바꿔준다.

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);
            }
        }
    }
}

👇 전체 코드

class CustomArray{
	constructor(numElements){
    	this.dataStore = [];
        this.pos = 0;
        this.numElements = numElements;
        
        for (let i = 0; i < numElements; ++i) { 
        	this.dataStore[i] = i;
		}
    }
    
    // 삽입
    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);
                }
            }
        }
    
    }
    /////////////////////////// 💖 추가 ///////////////////////////
}

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

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

/**
2 2 5 8 5 10 2 1 1 10 
정렬 후:
1 1 2 2 2 5 5 8 10 10 
*/

Selection Sort

선택 정렬은 배열의 처음에서 시작해서 첫 엘리먼트를 나머지 엘리먼트들과 비교하면서 정렬을 한다.

모든 엘리먼트를 살펴보면 가장 작은 엘리먼트가 배열의 맨 앞으로 이동시키고,

이제 두 번째 엘리먼트를 남은 엘리먼트들과 비교하면서 두 번째로 작은 엘리먼트를 배열의 맨 앞에서 두 번째에 이동시킨다.

배열의 모든 요소를 살펴볼 때까지 반복하여 정렬을 완성한다.

알파벳들이 선택 정렬이 되는 예시를 살펴보자.

시작: E A D H B (알파벳 순서 A를 배열 맨 앞으로)
정렬: A E D H B (두 번째 순서 B를 배열 두 번째 요소로)
정렬: A B D H E (네 번째 순서 D를 배열 세 번째 요소로)
정렬: A B D E H (다섯 번쩨 순서 E를 배열 네 번째 요소로)

이번에는 숫자들을 오름차순으로 선택 정렬하는 예시를 살펴보자.

72 54 59 30 31 78 2 77 82 72 (정렬 시작!)
2 72 54 59 30 31 78 77 82 72
2 30 72 54 59 31 78 77 82 72
2 30 31 72 54 59 78 77 82 72
2 30 31 54 72 59 78 77 82 72
2 30 31 54 59 72 78 77 82 72
2 30 31 54 59 72 72 78 77 82
2 30 31 54 59 72 72 77 78 82
2 30 31 54 59 72 72 77 78 82 (정렬 완료!)

구현

위에서 살펴보면 배열의 요소들을 맨 앞에서부터 가장 낮은 숫자를 맨 앞으로 이동시키기를 반복한다.

구현은 다음과 같이 할 수 있다.

배열의 첫 번째 요소를 최솟값으로 하고 그다음 요소가 현재 요소보다 작다면 최솟값으로 설정하고, 이 둘의 위치를 바꿔주면 된다.

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);
        }
    }
}

👇 전체 코드

class CustomArray{
	constructor(numElements){
    	this.dataStore = [];
        this.pos = 0;
        this.numElements = numElements;
        
        for (let i = 0; i < numElements; ++i) { 
        	this.dataStore[i] = i;
		}
    }
    
    // 삽입
    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);
            }
        }
	}
    /////////////////////////// 💖 추가 /////////////////////////// 

}

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

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

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

Insertion Sort

삽입 정렬은 사람들이 숫자나 알파벳을 정렬할 때 사용하는 방식과 비슷하다.

다음과 같이 학생 이름이 적힌 카드들을 삽입 정렬한다고 하자.

카드 더미에서 하나를 꺼냈는데 "Smith"가 나오면 책상 왼쪽 가장자리에 둔다.

[Smith]

다음 카드가 "Brown"이면 Smith가 적힌 카드를 오른쪽으로 밀어서 Smith의 자리에 두고,

[Smith] [Brown]

다음 카드가 "Williams"면 다른 카드들은 그대로 두고 책상의 오른쪽 맨 끝으로 이동시키면 된다.

[Smith] [Brown] [Williams]

그다음 카드가 "Acklin"이면 카드들을 하나씩 옮겨서 맨 앞에 자리를 하나 만들어준 뒤,

그 자리에 Acklin이 적힌 카드를 두면 된다.

[Acklin] [Smith] [Brown] [Williams]

구현

위의 예시에서 살펴봤듯이, 값이 제일 작으면 맨 앞으로 위치시키고,

크다면 자리를 하나 만들어주고 하나씩 이동시켜 주면 된다. 이전에 살펴봤던 정렬 방식들은 두 값의 위치를 바꿔줬었더, 삽입 정렬은 현재 데이터 값의 자리를 만들어주고 그만큼 하나씩 밀어내는 방식이다.

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;
    }
}

👇 전체 코드

class CustomArray{
	constructor(numElements){
    	this.dataStore = [];
        this.pos = 0;
        this.numElements = numElements;
        
        for (let i = 0; i < numElements; ++i) { 
        	this.dataStore[i] = i;
		}
    }
    
    // 삽입
    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;
        }
	}
    /////////////////////////// 💖 추가 ///////////////////////////

}

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

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

/**
6 10 9 8 4 1 7 8 10 6 
정렬 후:
1 4 6 6 7 8 8 9 10 10
*/

🍀 마치면서

👇 생각보다 글이 길어져서 2탄은 심화 정렬 알고리즘에 대해 다룹니다.

[다음글] 2024.07.28 - [🤖 data structures & algorithms] - Data Structures & Algorithms with Javascript : Sorting Algorithms (Advanced)

📚 Reference

'🤖 data structures & algorithms' 카테고리의 다른 글

Data Structures & Algorithms with Javascript : Searching Algorithms (0)	2024.07.29
Data Structures & Algorithms with Javascript : Sorting Algorithms (Advanced) (0)	2024.07.28
Data Structures & Algorithms with Javascript : 중간(?) 점검 🍪 (0)	2024.07.25
Data Structures & Algorithms with Javascript : Binary Trees and Binary Search Trees (0)	2024.07.25
Data Structures & Algorithms with Javascript : Sets (2)	2024.07.24

🥕 pyotato's dev farm

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

비교를 위한 커스텀 Array 클래스

기본 정렬 알고리즘

Bubble Sort

구현

Selection Sort

구현

Insertion Sort

구현

🍀 마치면서

📚 Reference

'🤖 data structures & algorithms' 카테고리의 다른 글

티스토리툴바

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

비교를 위한 커스텀 Array 클래스

기본 정렬 알고리즘

Bubble Sort

구현

Selection Sort

구현

Insertion Sort

구현

🍀 마치면서

📚 Reference

'🤖 data structures & algorithms' 카테고리의 다른 글

'🤖 data structures & algorithms' Related Articles

티스토리툴바

Selection Sort

Insertion Sort