코딩 테스트(JS)_정렬

※ 정렬 기초

// 1. 숫자 정렬
let data = [3,5, 2, 1, 4];
console.log('source : ' + data);
 
// data.sort((a,b)=>a-b);
data.sort((a,b)=>{
    if(a<b) return -1;
    if(a>b) return 1;
    if(a==b) return 0;
})
 
console.log('result : ' + data);
 
// 2. 문자 정렬: 대문자의 경우 맨 앞으로 정렬됨
let strData = ['fineapple', 'durian', 'carrot', 'banana', 'apple'];
 
strData.sort((a,b)=>{
    if(a<b) return -1;
    if(a>b) return 1;
    if(a==b) return 0;
})
 
console.log('result : ' + strData);
 
// 3. 문자 정렬: 대소문자 구분 없이 정렬
let strData2 = ['fineapple', 'durian', 'Carrot', 'banana', 'apple'];
 
// 함수의 이름만 기재
strData2.sort(compare);    
 
function compare(a, b){
    let upperA = a.toUpperCase();
    let upperB = b.toLowerCase();
    if(upperA<upperB) return -1;
    if(upperA>upperB) return 1;
    if(upperA==upperB) return 0;
}
 
console.log('result : ' + strData2);
 
// 4. 객체 비교
let objectData = [
    {name : '홍길동', score : 90},
    {name : '김철수', score : 85},
    {name : '박영희', score : 99},
];
 
// 성적에 대한 내림차순으로 정렬하기(성적순)
objectData.sort(compareObject);
 
function compareObject(a, b){
    return b.score - a.score;
}
 
for(man of objectData){
    console.log('result : ' + man.name + ' ' + man.score);
}

 

1. 선택 정렬(Selection)

· 선택정렬은 매 단계에서 가장 작은 값을 앞으로 보내며, 그 값은 더 이상 위치가 변하지 않는다.
· 시간복잡도 O(N^2)로 비효율적 정렬 알고리즘 중 하나.

 

 

let fs = require('fs');
let input = fs.readFileSync('sort_01.txt')
            .toString().split('\n');
 
let data = input[0].split(' ').map(Number);
 
for(let i=0; i<data.length-1; i++){
    // 가장 작은 값의 인덱스를 넣어둘 변수
    let minIndex = i;
    for(let j=i+1; j<data.length; j++){
        if(data[minIndex] > data[j]){
            minIndex = j;
        }
    }
    let temp = data[i];
    data[i] = data[minIndex];
    data[minIndex] = temp;
    console.log((i+1)+'단계 : ' + data);
}

2. 버블 정렬

· 각 단계에서 인접한 두 개의 값을 비교하여, 큰 값을 뒤로 보냄
· 시간복잡도 O(N^2)로 비효율적 정렬 알고리즘 중 하나.

 

 

let fs = require('fs');
let input = fs.readFileSync('sort_02.txt')
            .toString().split('\n');
 
let data = input[0].split(' ').map(Number);
let flag = true;
 
for(let i=0; i<data.length-1; i++){
    // 교환이 일어났는지 확인할 변수 
    for(let j=0; j<data.length-i; j++){
        if(data[j] > data[j+1]){
            // 앞에 값이 클 때 바꿈
            let temp = data[j];
            data[j] = data[j+1];
            data[j+1] = temp;
            // 교환 후 교환 확인 변수 변경
            flag = false;
        }
    }   
    if(flag == false){
        console.log((i+1)+'단계 : ' + data);
    }else break;
}
console.log('정렬 완료');

3. 삽입 정렬(Insertion)

· 각 숫자를 적절한 위치에 삽입하는 정렬 기법
· 시간복잡도 O(N^2)로 비효율적 정렬 알고리즘 중 하나.

 

 

 

 

※ 삽입, 버블 정렬에 비해 빠름

 

 

 

 

let fs = require('fs');
let input = fs.readFileSync('sort_02.txt')
            .toString().split('\n');
 
let data = input[0].split(' ').map(Number);
 
for(let i=1; i<data.length; i++){
    for(let j=i; j>0; j--){
        if(data[j] < data[j-1]){
            let temp = data[j];
            data[j] = data[j-1];
            data[j-1] = temp;
        }else break;
    }
    console.log((i+1)+'단계 : ' + data);
}

 

4. 병합 정렬(Merge Sort)

· 정렬해야 할 리스트가 주어질 때, 분할을 반복하여 최소 단위로 나누어 놓은 뒤 데이터를 비교하여 정렬하여 병합
· 재귀 함수를 이용한 정렬 알고리즘 / 시간 복잡도: N*logN

 

// mergeSort
let data = [8, 4, 6, 1];
// 병합 정렬될 임시 배열
let sorted = [];
 
// mergeSort 호출
mergeSort(data, 0, data.length-1);
// 결과 출력하기
console.log('result : ' + data);
 
// mergeSort 정의
function mergeSort(arr, left, right){
    if(left < right){
        // 중간 인덱스 구하기
        let mid = parseInt((left+right)/2);
        // 배열의 왼쪽 쪼개기
        mergeSort(arr, left, mid);
        // 배열의 오른쪽 조깨기
        mergeSort(arr, mid+1, right);
        // 병합 처리
        merge(arr, left, mid, right);
    }
}
 
// 병합 처리 함수 구현
function merge(arr, left, mid, right){
    let i = left;
    let j = mid + 1;
    // 병합할 배열의 인덱스
    let k = left;
    
    while(i <= mid && j <= right){
        if(arr[i] <= arr[j]){
            // 앞쪽 배열 값이 작은 경우
            sorted[k] = arr[i];
            k++;
            i++;
        }else{
            // 뒤쪽 배열 값이 작은 경우
            sorted[k++] = arr[j++];
            // k++;
            // j++;
        }
    }
 
    // 왼쪽이 끝난 경우
    if(i > mid){
        for(; j<=right; j++){
            sorted[k] = arr[j];
            k++;
        }
    }else{
        // 오른쪽이 끝난 경우
        for(; i<=mid; i++){
            sorted[k] = arr[i];
            k++;
        }
    }
    // 두 개의 배열이 하나로 합쳐짐.(sorted)
    // sorted 배열의 내용을 arr에다가 update
    for(let x=left; x<=right; x++){
        arr[x] = sorted[x];
    }
    console.log('sorted : ' + sorted);
}