[JavaSrcipt] 정렬알고리즘 (거품,선택,삽입)

✅ Bubble sort (거품정렬)

배열의 두 인덱스값을 비교하여 큰 값을 오른쪽으로 바꾸며 정렬.

const arr=[5,5,3,2,4,1];
const n=arr.shift();

for(let i=0;i<n-1;i++){
    for(let j=0;j<n-i-1;j++){
        
        if(arr[j]>arr[j+1]){
            let temp=arr[j];
                arr[j]=arr[j+1];
                arr[j+1]=temp;
          }
    }
}
console.log(arr);

아우터루프

전체범위설정 -1  //두개씩 비교하는것이므로 n-1이어도 무방

 

이너루프 

범위를 0부터 n-i-1 // 최종위치가 확정되어있기때문에 확정된자리까지 점검할필요는 없음.

                           즉 i는 현재까지 자리가 확정된 인자들의 갯수

 

❗ 두 값을 비교후 큰값을 오른쪽으로 이동

❗ 아우터루프가 한번 돌때마다 하나의 element의 최종위치가 확정

❗ 시간복잡도   O(n²)

 

 

 

✅ Selection sort (선택정렬)

가장 작은 숫자를 차례로 탐색후 가장 왼쪽자리와 바꿈. //오름차순 내림차순등 의도에따라 변경가능

가장 작은숫자를 선택하는방식

const arr=[5,5,3,2,4,1];
const n=arr.shift();

for(let i=0;i<n-1;i++){
    let minIndex=i;
    for(let j=i+1;j<n;j++){
        if(arr[j]<arr[minIndex]){
            minIndex=j;
        }
    }
    let temp = arr[minIndex];
    arr[minIndex] = arr[i];
    arr[i] = temp;
}
console.log(arr);

minIndex로 임시로 i를 받는다.

이후 i+1이 j이므로 arr[j]의값과 arr[minIndex]의 값을 비교해

arr[minIndex]가 더작다면 minIndex는 j로 설정

 

❗ 첫번째 element를 가장 낮은값으로 가정하고 minIndex로 받아 실행

이미 정렬되어있는 부분은 제외하고 i+1과 minIndex를 비교

 

❗ minIndex는 최소값의 저장장치라고 생각하고, swap은 아우터루프한바퀴당 한번 실행.

❗ 아우터루프가 한번 돌때마다 하나의 element의 최종위치가 확정

❗ 시간복잡도   O(n²)

 

ex) 아우터루프 한바퀴 // 제일작은 끝인덱스값 1을 minIndex로 받아

arr[i] 현재i값은 0이므로 0인덱스에 1이들어감.

5와 1을 바꾸므로 첫바퀴 // 1 3 2 4 5가 됨

 

 

 

✅ Insertion sort (삽입정렬)

정렬된 arr를 유지하며 진행

버블,선택과 달리 한번루프마다 데이터의 위치가 확정되는게 아님

새로운 값이 삽입되면 정렬된arr안에서 자신의 자리를 찾아가며 정렬.

const arr=[5,5,2,4,3,1];
const n=arr.shift();

for(let i=1;i<n;i++){
    let key = arr[i];
    let j = i-1;
    
    while(j>=0 && arr[j]>key){
        arr[j+1]=arr[j];
        j--;
    }
    arr[j+1]=key;
}
console.log(arr);

❗ 정렬된 arr를 유지하며 한칸씩 늘려가며 정렬

❗ 한칸씩 늘어날때 새로 삽입된 데이터를 정렬된 arr에 맞는자리로 위치

❗ 시간복잡도   O(n²)

 

i는 1이며 arr[i]를 key에 담아둔다.

j=i-1 즉 0이된다.

 

while문의 조건이 j>=0 즉 j가 음수가 아닌이상 첫번째조건은 만족

두번째조건 arr[j]>key 까지 만족했다면

arr[j+1]=arr[j]  swap이아닌 덮어씌운뒤 j--

반복하다가 j가 음수가되면 while문을 빠져나와

arr[j+1]에 맨위에서 담아뒀던 arr[i]를 넣는다.

 

첫번째 element는 정렬되어있다고 가정을 해서

i=1부터 시작을 하는것이다.

 

첫번째바퀴

key=arr[1] // 2

let j=i-1 // 0

 

j>=0 (true) && arr[j]>key  //  5>2 true

arr[j+1] = arr[j]  //  2자리를 5로 덮어씌움 5 5 4 3 1

j-- // j=-1

while문 불만족,탈출

arr[j+1] = key;   arr[ -1 +1 ] = 2;

j의 값이 -1이되어 빠져나온것이기때문에

+1을 하면 0 인덱스이다 여기에 처음에 담아뒀던 key값 2를 넣는다.

첫바퀴 // 2 5 4 3 1