정렬 알고리즘 (삽입/선택/버블) / javascript

선택정렬(Selection Sort)

현재위치에 들어갈 값을 찾아서 정렬하는 방식

1. 정렬되지 않은 배열중에 가장 작은 값을 찾아서 첫번째 (현재) index값과 바꾸어준다.
2. 그리고 나머지 요소들을 비교한 후 가장 작은 값을 두번째 (현재) index 값과 바꾸어준다.
3. 세번째, 네번째 … 위를 반복하면 앞에서부터 순차적으로 정렬이 된다.

for(let i=0; i<arr.length; i++){
    let idx=i;
    for(let j=i+1; j<arr.length; j++){
        if(arr[j]<arr[idx]) idx=j;
    }
    [arr[i], arr[idx]] = [arr[idx], arr[i]];
}

 

버블정렬(Bubble Sort)

연속되어있는 두 개의 값을 비교한 후 작은 값을 앞으로 보내는 방식.
비교 할 때 마다 큰 값은 뒤로 가면서 비교를 반복하기 때문에 가장 큰 값이 맨 뒤로 쌓인다.
즉, 한바퀴 돌고 나면 맨 뒤의 값까지 비교를 할 필요가 없다.


1. 현재 인덱스 값과 현재 인덱스의 뒤의 값을 비교.
(비교할 배열의 요소가 10개면 2묶음씩 비교하기 때문에 한 바퀴 비교 시 9번 비교를 진행한다)
2. 현재 값보다 현재값 뒤의 값이 더 작다면 위치를 바꿔준다.
3. (배열의 요소 수 - 1) + (순환한 바퀴 수) 반복

 

for(let i=0; i<arr.length-1; i++){
    for(let j=0; j<arr.length-i-1; j++){
        if(arr[j]>arr[j+1]){
            [arr[j], arr[j+1]]=[arr[j+1], arr[j]];
        }
    }   
}

 

삽입정렬(Insertion Sort)

현재 위치에서 그 이전의 요소들과 비교하여 삽입하는 방식

1. 두번째 인덱스 값부터 시작하여 현재 인덱스는 변수로 저장하고 
2. 비교인덱스는 현재인덱스의 -1번째값이며 비교 인덱스와 저장한 변수와 비교하여 저장한 변수값이 더 작을경우
비교 인덱스 +1 값에 비교 인덱스 값을 넣어준다.
3. 비교 인덱스 값이 더 클 경우 비교를 중단하고 비교 인덱스 +1값에 변수 값을 넣어준다.

 

for(let i=0; i<arr.length; i++){
    let tmp=arr[i], j;
    for(j=i-1; j>=0; j--){
        if(arr[j]>tmp) arr[j+1]=arr[j];
        else break;
    }
    arr[j+1]=tmp;
}